Carmichael lambda function
Carmichael lambda function is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Background
The Carmichael function, or Carmichael lambda function, is a function in number theory. The Carmichael lambda λ(n) of a positive integer n is the smallest positive integer m such that
holds for every integer coprime to n.
The Carmichael lambda function can be iterated, that is, called repeatedly on its result. If this iteration is
performed k times, this is considered the k-iterated Carmichael lambda function. Thus, λ(λ(n))
would be the 2-iterated lambda function. With repeated, sufficiently large but finite k-iterations, the iterated Carmichael function will eventually compute as 1 for all positive integers n.
- Task
- Write a function to obtain the Carmichael lamda of a positive integer. If the function is supplied by a core library of the language, this also may be used.
- Write a function to count the number of iterations k of the k-iterated lambda function needed to get to a value of 1. Show the value of λ(n) and the number of k-iterations for integers from 1 to 25.
- Find the lowest integer for which the value of iterated k is i, for i from 1 to 15.
- Stretch task (an extension of the third task above)
- Find, additionally, for i from 16 to 25, the lowest integer n for which the number of iterations k of the Carmichael lambda function from n to get to 1 is i.
- See also
Mathematica|Wolfram Language
IteratedToOne[i_] := Module[{k = 0, iter = i},
While[iter > 1, iter = CarmichaelLambda[iter];
k++;];
k]
Print["Listing of (n, lambda(n), k for iteration to 1) for integers from 1 to 25:"];
Do[lam = CarmichaelLambda[i];
k = IteratedToOne[i];
If[Mod[i, 5] == 0, Print[{i, lam, k}], Print[{i, lam, k}, " "]], {i, 1, 25}]
upTo = 20;
maxToTest = 100000000000;
firsts = Table[0, {upTo + 1}];
firsts[[1]] = 1;
Print["\nIterations to 1 n lambda(n)\n=================================="];
Print[StringForm["`` `` ``", 0, 1, 1]];
Do[n = IteratedToOne[i];
If[0 < n <= upTo && firsts[[n + 1]] == 0, firsts[[n + 1]] = i;
j = If[n < 1, 0, CarmichaelLambda[i]];
Print[StringForm["`` `` ``", n, i, j]];
If[n >= upTo, Break[]];], {i, 2, maxToTest}]
- Output:
Listing of (n, lambda(n), k for iteration to 1) for integers from 1 to 25:
{1, 1, 0}
{2, 1, 1}
{3, 2, 2}
{4, 2, 2}
{5, 4, 3}
{6, 2, 2}
{7, 6, 3}
{8, 2, 2}
{9, 6, 3}
{10, 4, 3}
{11, 10, 4}
{12, 2, 2}
{13, 12, 3}
{14, 6, 3}
{15, 4, 3}
{16, 4, 3}
{17, 16, 4}
{18, 6, 3}
{19, 18, 4}
{20, 4, 3}
{21, 6, 3}
{22, 10, 4}
{23, 22, 5}
{24, 2, 2}
{25, 20, 4}
Iterations to 1 n lambda(n)
==================================
0 1 1
1 2 1
2 3 2
3 5 4
4 11 10
5 23 22
6 47 46
7 283 282
8 719 718
9 1439 1438
10 2879 2878
11 34549 34548
12 138197 138196
13 531441 354294
14 1594323 1062882
15 4782969 3188646
Phix
with javascript_semantics
function lambda(sequence pk)
integer {p,k} = pk, res = phi(power(p,k))
return iff(p=2 and k>=3 ? res/2 : res)
end function
function reduced_totient(integer n)
sequence p = prime_powers(n)
for i,pk in p do
p[i] = lambda(pk)
end for
return lcm(p)
-- alt: neater but ~2* slower
-- return lcm(apply(prime_powers(n),lambda))
end function
function k_iter(integer i)
return iff(i>1?1+k_iter(reduced_totient(i)):0)
end function
function ident(integer i) return i end function
sequence n = tagset(25)
for i,d in {"n","eulers_totient","reduced_totient","k"} do
sequence r = apply(n,{ident,phi,reduced_totient,k_iter}[i])
printf(1,"%17s: %s\n",{d,join(r," ",fmt:="%2d")})
end for
atom t0 = time()
printf(1,"\n k i lambda(i)\n")
printf(1, "==========================\n")
integer i = 1
for k=0 to iff(platform()=JS?12:15) do -- (keep JS < 3s)
while k_iter(i)!=k do i += 1 end while
printf(1,"%2d %,9d %,9d\n",{k,i,reduced_totient(i)})
end for
?elapsed(time()-t0)
- Output:
n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
eulers_totient: 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20
reduced_totient: 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 20
k: 0 1 2 2 3 2 3 2 3 3 4 2 3 3 3 3 4 3 4 3 3 4 5 2 4
k i lambda(i)
==========================
0 1 1
1 2 1
2 3 2
3 5 4
4 11 10
5 23 22
6 47 46
7 283 282
8 719 718
9 1,439 1,438
10 2,879 2,878
11 34,549 34,548
12 138,197 138,196
13 531,441 354,294
14 1,594,323 1,062,882
15 4,782,969 3,188,646
"2 minutes and 27s"
stretch
16 14,348,907 9,565,938 17 43,046,721 28,697,814
I estimate that took ~47mins, at which point I killed it.
The Python code took 13mins 58 secs to get to 15, on the same box.
Python
Python has the Carmichael function in the SymPy library, where it is called reduced_totient.
from sympy import reduced_totient
def iterated_to_one(i):
""" return k for the k-fold iterated lambda function where k is the first time iteration reaches 1 """
k = 0
while i > 1:
i = reduced_totient(i)
k += 1
return k
if __name__ == "__main__":
print("Listing of (n, lambda(n), k for iteration to 1) for integers from 1 to 25:")
for i in range(1, 26):
lam = reduced_totient(i)
k = iterated_to_one(i)
print(f'({i}, {lam}, {k})', end = '\n' if i % 5 == 0 else ' ')
UP_TO = 20
MAX_TO_TEST = 100_000_000_000
FIRSTS = [0] * (UP_TO + 1)
FIRSTS[0] = 1
print('\nIterations to 1 n lambda(n)\n==================================')
print(' 0 1 1')
for i in range(2, MAX_TO_TEST):
n = iterated_to_one(i)
if 0 < n <= UP_TO and FIRSTS[n] == 0:
FIRSTS[n] = i
j = 0 if n < 1 else int(reduced_totient(i))
print(f"{n:>4}{i:>17}{j:>11}")
if n >= UP_TO:
break
- Output:
Listing of (n, lambda(n), k for iteration to 1) for integers from 1 to 25: (1, 1, 0) (2, 1, 1) (3, 2, 2) (4, 2, 2) (5, 4, 3) (6, 2, 2) (7, 6, 3) (8, 2, 2) (9, 6, 3) (10, 4, 3) (11, 10, 4) (12, 2, 2) (13, 12, 3) (14, 6, 3) (15, 4, 3) (16, 4, 3) (17, 16, 4) (18, 6, 3) (19, 18, 4) (20, 4, 3) (21, 6, 3) (22, 10, 4) (23, 22, 5) (24, 2, 2) (25, 20, 4) Iterations to 1 n lambda(n) ================================== 0 1 1 1 2 1 2 3 2 3 5 4 4 11 10 5 23 22 6 47 46 7 283 282 8 719 718 9 1439 1438 10 2879 2878 11 34549 34548 12 138197 138196 13 531441 354294 14 1594323 1062882 15 4782969 3188646 16 14348907 9565938 17 43046721 28697814 18 86093443 86093442 19 258280327 258280326 20 688747547 688747546
Raku
# 20240228 Raku programming solution
use Prime::Factor;
sub phi(Int $p, Int $r) { return $p**($r - 1) * ($p - 1) }
sub CarmichaelLambda(Int $n) {
state %cache = 1 => 1, 2 => 1, 4 => 2;
sub CarmichaelHelper(Int $p, Int $r) {
my Int $n = $p ** $r;
return %cache{$n} if %cache{$n}:exists;
return %cache{$n} = $p > 2 ?? phi($p, $r) !! phi($p, $r - 1)
}
if $n < 1 { die "'n' must be a positive integer." }
return %cache{$n} if %cache{$n}:exists;
if ( my %pps = prime-factors($n).Bag ).elems == 1 {
my ($p, $r) = %pps.kv>>.Int;
return %cache{$n} = $p > 2 ?? phi($p, $r) !! phi($p, $r - 1)
}
return [lcm] %pps.kv.map: -> $k, $v { CarmichaelHelper($k.Int, $v) }
}
sub iteratedToOne($i is copy) {
my $k = 0;
while $i > 1 { $i = CarmichaelLambda($i) andthen $k++ }
return $k
}
say " n λ k";
say "----------";
for 1..25 -> $n {
printf "%2d %2d %2d\n", $n, CarmichaelLambda($n), iteratedToOne($n)
}
say "\nIterations to 1 i lambda(i)";
say "=====================================";
say " 0 1 1";
my ($maxI, $maxN) = 5e6, 10; # for N=15, takes around 47 minutes with an i5-10500T
my @found = True, |( False xx $maxN );
for 1 .. $maxI -> $i {
unless @found[ my $n = iteratedToOne($i) ] {
printf "%4d %18d %12d\n", $n, $i, CarmichaelLambda($i);
@found[$n] = True andthen ( last if $n == $maxN )
}
}
- Output:
Same as Wren example .. and it is probably 30X times slower 😅
Wren
Takes about 88 seconds on my machine (Core i7) to get up to n = 15 for the third part of the task, so haven't attempted the stretch goal.
import "./math" for Int
import "./fmt" for Fmt
var primePows = Fn.new { |n|
var factPows = []
var pf = Int.primeFactors(n)
var currFact = pf[0]
var count = 1
for (fact in pf.skip(1)) {
if (fact != currFact) {
factPows.add([currFact, count])
currFact = fact
count = 1
} else {
count = count + 1
}
}
factPows.add([currFact, count])
return factPows
}
var phi = Fn.new { |p, r| p.pow(r-1) * (p - 1) }
var cache = { 1: 1, 2: phi.call(2, 1), 4: phi.call(2, 2) }
var CarmichaelHelper = Fn.new { |p, r|
var n = p.pow(r)
if (cache.containsKey(n)) return cache[n]
if (p > 2) return cache[n] = phi.call(p, r)
return cache[n] = phi.call(p, r - 1)
}
var CarmichaelLambda = Fn.new { |n|
if (n < 1) Fiber.abort("'n' must be a positive integer.")
if (cache.containsKey(n)) return cache[n]
var pps = primePows.call(n)
if (pps.count == 1) {
var p = pps[0][0]
var r = pps[0][1]
if (p > 2) return cache[n] = phi.call(p, r)
return cache[n] = phi.call(p, r - 1)
}
var a = []
for (pp in pps) a.add(CarmichaelHelper.call(pp[0], pp[1]))
return cache[n] = Int.lcm(a)
}
var iteratedToOne = Fn.new { |i|
var k = 0
while (i > 1) {
i = CarmichaelLambda.call(i)
k = k + 1
}
return k
}
System.print(" n λ k")
System.print("----------")
for (n in 1..25) {
var lambda = CarmichaelLambda.call(n)
var k = iteratedToOne.call(n)
Fmt.print("$2d $2d $2d", n, lambda, k)
}
System.print("\nIterations to 1 i lambda(i)")
System.print("=====================================")
System.print(" 0 1 1")
var maxI = 5 * 1e6
var maxN = 15
var found = List.filled(maxN + 1, false)
found[0] = true
var i = 1
while (i <= maxI) {
var n = iteratedToOne.call(i)
if (!found[n]) {
found[n] = true
var lambda = CarmichaelLambda.call(i)
Fmt.print("$4d $,18d $,12d", n, i, lambda)
if (n == maxN) break
}
i = i + 1
}
- Output:
n λ k ---------- 1 1 0 2 1 1 3 2 2 4 2 2 5 4 3 6 2 2 7 6 3 8 2 2 9 6 3 10 4 3 11 10 4 12 2 2 13 12 3 14 6 3 15 4 3 16 4 3 17 16 4 18 6 3 19 18 4 20 4 3 21 6 3 22 10 4 23 22 5 24 2 2 25 20 4 Iterations to 1 i lambda(i) ===================================== 0 1 1 1 2 1 2 3 2 3 5 4 4 11 10 5 23 22 6 47 46 7 283 282 8 719 718 9 1,439 1,438 10 2,879 2,878 11 34,549 34,548 12 138,197 138,196 13 531,441 354,294 14 1,594,323 1,062,882 15 4,782,969 3,188,646