1
$\begingroup$

This is a code review or de-clunking request. If it doesn't belong here, I'll withdraw it.

The below toy works and produces the proper output, that is, for numbers to be factored that can be expressed as $a^b-1$, it factors the factors of $a^x-1$, and in doing so renders some numbers factorable in a reasonable time, by producing a list of numbers with exponents < x.

For example, I stopped the still in-progress FactorInteger[10^270-1] after 2 weeks; using below for $10^{270}-1$ takes about 5 seconds. So the issue is that the tbl = Reap ... section (and maybe more) looks like it could use improvement that is currently beyond me.
Much obliged.

The tbl= section prints the symbolic factors of $h^{\rm mu}-1$, then prints for each the corresponding (numeric) factor of $10^{\rm mu}-1$. Then it tries to FactorInteger those numbers. At least, if it stalls, the problem number has already been printed. E.g., try $\rm mu=540$.

The j= section combs through the FactorInts (which are the 4th part of each tbl sublist), grouping by prime factor and summing exponents, that is, reassembling into FactorInteger format w/each prime factor appearing once.

The formula for Carmichael Lambda was lifted from
MathWorld: CarmichaelFunction.html

Clear[tbl, tblFI, b, k, mu, cm, cmL, cmLFI]
mu = 27;
k = Factor[h^mu-1];
b = 10;

Print[h^mu, "-1 = ", k]; Print[" "]

tbl = Reap[     
         Do[    
            {   
                 Print[Sow[k[[i]]]],
                 Print[Sow[k[[i]] /. h->b]],
                 Print[Sow[Apply[Times, Map[(Superscript[#[[1]], #[[2]]]) &, q=FactorInteger[k[[i]]/. h->b]]]];" "],
                 Sow[q]
             },
            {i, Length[k]}  
            ]
            ][[2]]  // Flatten[#, 1]&  // Partition[#, 4]&

Times @@(#[[1]]^#[[2]] & /@ Flatten[ tbl[[All, 4]], 1]) == b^mu-1  (* They'd better == *)  

j = (Total /@ SortBy[GroupBy[Flatten[tbl[[All, 4]], 1], First], First]) [[All, 2]] ; 
tblFI = Partition[Riffle[Keys[j], Values[j]], 2]   
     
cmL = LCM @@ (cm=Map[(#1[[1]]-1)#1[[1]]^(#1[[2]]-1)&, tblFI]); 
Print["cmL[", h^mu, "-1, h\[RightArrow]", b,"] = LCM @@ ", cm, "= ",  cmL]
cmLFI = FactorInteger[cmL]; 
Print[" = ", Apply[Times, Map[(Superscript[#[[1]], #[[2]]]) &, cmLFI]]]; 
Print[""]
Print["FI[", h^mu, "-1, h\[RightArrow]", b,"] = ", Apply[Times, 
Map[(Superscript[#[[1]], #[[2]]]) &, tblFI]]]
$\endgroup$
4
  • 1
    $\begingroup$ CarmichaelLambda has been in Mathematica since 11.3 (2013) $\endgroup$ – flinty Sep 19 '20 at 12:04
  • 1
    $\begingroup$ @flinty According to the document, CarmichaelLambda has been in Mathematica since 4.0 (1999) $\endgroup$ – wuyudi Sep 19 '20 at 12:18
  • $\begingroup$ @wuyudi indeed I stand corrected. It got an update in 2013. $\endgroup$ – flinty Sep 19 '20 at 12:28
  • 1
    $\begingroup$ @flinty But CarmichaelLambda is almost as expensive as FactorInteger, the point being that once you've labored to get FactorInteger, you can recycle that result into a roll-your-own Carmichael Lambda. $\endgroup$ – Christopher Lamb Sep 19 '20 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.