Carmichael lambda function

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

{\displaystyle a^{m}\equiv 1{\pmod {n}}}

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 lambda 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

C++

#include <cmath> #include <cstdint> #include <iomanip> #include <iostream> #include <numeric> #include <vector> struct PrimePower { uint32_t prime; uint32_t power; }; std::vector<PrimePower> prime_powers(const uint32_t& number) { std::vector<PrimePower> powers{}; uint32_t n = number; for ( uint32_t i = 2; i <= std::sqrt(n); ++i ) { if ( n % i == 0 ) { powers.emplace_back(PrimePower(i, 0)); while ( n % i == 0 ) { powers.back().power += 1; n /= i; } } } if ( n > 1 ) { powers.emplace_back(PrimePower(n, 1)); } return powers; } uint32_t carmichael_lambda(const uint32_t& number) { if ( number == 1 ) { return 1; } std::vector<PrimePower> powers = prime_powers(number); uint32_t result = 1; for ( PrimePower primePower : powers ) {  uint32_t car = ( primePower.prime - 1 ) * std::pow(primePower.prime, primePower.power - 1);  if ( primePower.prime == 2 && primePower.power >= 3 ) {  car /= 2;  }  result = std::lcm(result, car); } return result; } uint32_t count_iterations_to_one(const uint32_t& n) { return ( n <= 1 ) ? 0 : count_iterations_to_one(carmichael_lambda(n)) + 1; } int main() { std::cout << " n carmichael(n) iterations(n)" << std::endl; std::cout << "--------------------------------" << std::endl; for ( uint32_t i = 1; i <= 25; ++i ) { std::cout << std::setw(2) << i << std::setw(10) << carmichael_lambda(i)  << std::setw(14) << count_iterations_to_one(i) << std::endl; } std::cout << std::endl; std::cout << "Iterations to 1 n lambda(n)" << std::endl; std::cout << "-----------------------------------" << std::endl; uint32_t n = 1; for ( uint32_t i = 0; i <= 15; ++i ) { while ( count_iterations_to_one(n) != i ) { n += 1; } std::cout << std::setw(2) << i << std::setw(19) << n << std::setw(13) << carmichael_lambda(n) << std::endl; } }

Output:

 n carmichael(n) iterations(n) -------------------------------- 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

FreeBASIC

Translation of: Phix

Type PrimePower  prime As Uinteger  power As Uinteger End Type Function GCD(n As Uinteger, d As Uinteger) As Uinteger  Return Iif(d = 0, n, GCD(d, n Mod d)) End Function Function lcm(n As Uinteger, d As Uinteger) As Uinteger  Return (n * d) \ GCD(n, d) End Function Function getPrimePowers(n As Uinteger, Byref cnt As Uinteger) As PrimePower Ptr  Dim As PrimePower Ptr powers = Callocate(32 * Sizeof(PrimePower))  cnt = 0  Dim As Uinteger num = n    For i As Uinteger = 2 To Sqr(n)  If num Mod i = 0 Then  powers[cnt].prime = i  powers[cnt].power = 0  While (num Mod i = 0)  powers[cnt].power += 1  num \= i  Wend  cnt += 1  End If  Next    If num > 1 Then  powers[cnt].prime = num  powers[cnt].power = 1  cnt += 1  End If    Return powers End Function Function phi(n As Uinteger) As Uinteger  If n = 1 Then Return 1    Dim As Uinteger cnt, result, i, p, k  Dim As PrimePower Ptr powers = getPrimePowers(n, cnt)  result = 1    For i = 0 To cnt - 1  p = powers[i].prime  k = powers[i].power  result *= (p - 1) * (p ^ (k - 1))  Next    Deallocate(powers)  Return result End Function Function lambda(p As Uinteger, k As Uinteger) As Uinteger  Dim As Uinteger res = phi(p ^ k)  Return Iif(p = 2 Andalso k >= 3, res \ 2, res) End Function Function reducedTotient(n As Uinteger) As Uinteger  If n = 1 Then Return 1    Dim As Uinteger cnt, result, i  Dim As PrimePower Ptr powers = getPrimePowers(n, cnt)  result = 1    For i = 0 To cnt - 1  result = lcm(result, lambda(powers[i].prime, powers[i].power))  Next    Deallocate(powers)  Return result End Function Function kIter(n As Uinteger) As Uinteger  Return Iif(n <= 1, 0, 1 + kIter(reducedTotient(n))) End Function ' Main program Dim As Uinteger i, n Print " n lambda(n) k(n)" Print "-----------------" For i = 1 To 25  Print Using "## ## ##"; i; reducedTotient(i); kIter(i) Next Print !"\nIterations to 1 n lambda(n)" Print String(36, "=") Dim As Double t0 = Timer n = 1 For i = 0 To 17 '15  While kIter(n) <> i  n += 1  Wend  Print Using "## ###,###,### ###,###,###"; i; n; reducedTotient(n) Next Dim As Double t1 = Timer - t0 Print Using !"\nTime elapsed: # minutes ##.### seconds"; t1 \ 60; t1 Mod 60 Sleep

Output:

 n lambda(n) k(n) ----------------- 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 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 Time elapsed: 2 minutes 9.137 seconds

stretch

16 14,348,907 9,565,938 17 43,046,721 28,697,814 Time elapsed: 47 minutes 54.000 seconds

Go

Works with: Go version 1.10.2

Translation of: Java

package main  import ( "fmt" "math" )  // PrimePower represents a prime number and its power type PrimePower struct { prime int power int }  func main() { fmt.Println(" n carmichael(n) iterations(n)") fmt.Println("--------------------------------") for i := 1; i <= 25; i++ { fmt.Printf("%2d%10d%14d\n", i, carmichaelLambda(i), countIterationsToOne(i)) } fmt.Println()  fmt.Println("Iterations to 1 n lambda(n)") fmt.Println("-----------------------------------") n := 1 for i := 0; i <= 15; i++ { for countIterationsToOne(n) != i { n++ } fmt.Printf("%2d%19d%13d\n", i, n, carmichaelLambda(n)) } }  func countIterationsToOne(n int) int { if n <= 1 { return 0 } return countIterationsToOne(carmichaelLambda(n)) + 1 }  func carmichaelLambda(number int) int { if number == 1 { return 1 }  powers := primePowers(number) result := 1  for _, primePower := range powers { car := (primePower.prime - 1) * int(math.Pow(float64(primePower.prime), float64(primePower.power-1))) if primePower.prime == 2 && primePower.power >= 3 { car /= 2 } result = lcm(result, car) }  return result }  func primePowers(number int) []PrimePower { var powers []PrimePower  for i := 2; i <= int(math.Sqrt(float64(number))); i++ { if number%i == 0 { powers = append(powers, PrimePower{i, 0}) for number%i == 0 { // Update the last element's power powers[len(powers)-1].power++ number /= i } } }  if number > 1 { powers = append(powers, PrimePower{number, 1}) }  return powers }  func lcm(a, b int) int { return a / gcd(a, b) * b }  func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }

Output:

n carmichael(n) iterations(n) -------------------------------- 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 ...

Java

import java.util.ArrayList; import java.util.List; public final class CarmichaelLambdaFunction { public static void main(String[] args) { System.out.println(" n carmichael(n) iterations(n)"); System.out.println("--------------------------------"); for ( int i = 1; i <= 25; i++ ) {  System.out.println(String.format("%2d%10d%14d", i, carmichaelLambda(i), countIterationsToOne(i))); } System.out.println();  System.out.println("Iterations to 1 n lambda(n)"); System.out.println("-----------------------------------"); int n = 1; for ( int i = 0; i <= 15; i++ ) {  while ( countIterationsToOne(n) != i ) {  n += 1;  }  System.out.println(String.format("%2d%19s%13s", i, n, carmichaelLambda(n))); } }  private static int countIterationsToOne(int n) { return ( n <= 1 ) ? 0 : countIterationsToOne(carmichaelLambda(n)) + 1; }  private static int carmichaelLambda(int number) {  if ( number == 1 ) {  return 1;  }    List<PrimePower> powers = primePowers(number);  int result = 1;   for ( PrimePower primePower : powers ) {  int car = ( primePower.prime - 1 ) * (int) Math.pow(primePower.prime, primePower.power - 1);  if ( primePower.prime == 2 && primePower.power >= 3 ) {  car /= 2;  }   result = lcm(result, car); }   return result; } private static List<PrimePower> primePowers(int number) { List<PrimePower> powers = new ArrayList<PrimePower>();    for ( int i = 2; i <= Math.sqrt(number); i++ ) {  if ( number % i == 0 ) {  powers.addLast( new PrimePower(i, 0) );  while ( number % i == 0 ) {  PrimePower last = powers.removeLast();  powers.addLast( new PrimePower(last.prime, last.power + 1) );  number /= i;  }  }  }    if ( number > 1 ) {  powers.addLast( new PrimePower(number, 1) );  }   return powers; }  private static int lcm(int a, int b) { return a / gcd(a, b) * b; }  private static int gcd(int a, int b) { return ( b == 0 ) ? a : gcd(b, a % b); }  private static record PrimePower(int prime, int power) {} }

Output:

 n carmichael(n) iterations(n) -------------------------------- 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

jq

Adapted from Wren

Works with jq, the C implementation of jq (*)

Works with gojq, the Go implementation of jq (**)

Works with jaq, the Rust implementation of jq (***)

A point of interest in the following implementation is the way in which the filter `iteratedToOne/1` prevents contamination of the input object by encapsulating it using the pattern: `def F: {"global": .} |.... | .global;`

(*) The program seemingly made no progress after i == 12 in the second table and was terminated.

(**) gojq's space requirements for this task beyond i == 10 in the second table are prohibitive.

(***) The program shown below is compatible with jaq except that jaq does not allow arrays to be grown implicitly by assignment; a simple workaround would be to change .cache to be a JSON object. However the space requirements effectively prevent computation of the rows in the second table beyond the row with i == 11.

### Generic functions def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .; def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); # Emit an array of the prime factors of 'n' in order using a wheel with basis [2, 3, 5] # e.g. 44 | primeFactors => [2,2,11] # From https://rosettacode.org/wiki/Product_of_min_and_max_prime_factors#jq def primeFactors: def out($i): until (.n % $i != 0; .factors += [$i] | .n = ((.n/$i)|floor) ); if . < 2 then [] else [4, 2, 4, 2, 4, 6, 2, 6] as $inc | { n: ., factors: [] } | out(2) | out(3) | out(5) | .k = 7 | .i = 0 | until(.k * .k > .n; if .n % .k == 0 then .factors += [.k] | .n = ((.n/.k)|floor) else .k += $inc[.i] | .i = ((.i + 1) % 8) end) | if .n > 1 then .factors += [ .n ] else . end | .factors end; # Define the helper function to take advantage of jq's tail-recursion optimization def lcm($m; $n): def _lcm: # state is [m, n, i] if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + $m]) | _lcm end; [$m, $n, $m] | _lcm; def lcm(stream): reduce stream as $s (1; lcm(.; $s)); ### Carmichael Lambda Function def primePows: . as $n | { factPows: [] } | ($n | primeFactors) as $pf | .currFact = $pf[0] | .count = 1 | reduce $pf[1:][] as $fact (.; if $fact != .currFact then .factPows += [[.currFact, .count]] | .currFact = $fact | .count = 1 else .count += 1 end) | .factPows + [[.currFact, .count]] ; def phi($p; $r): ($p | power($r-1)) * ($p - 1); # Initial cache values def cache: [0, 1, 1, null, 2]; # [_, 1, phi(2; 1), _, phi(2; 2)] # input: {cache} # output: {cache, result} def CarmichaelHelper($p; $r): ($p|power($r)) as $n | .cache[$n] as $cached | if $cached then .result=$cached else if $p > 2 then .cache[$n] = phi($p; $r) else .cache[$n] = phi($p; $r - 1) end | .result = .cache[$n] end; # input: {cache} # output: {cache, result, a} def CarmichaelLambda($n): .cache |= (. // cache) | .result = null | if $n < 1 then "CarmichaelLambda: argument must be a positive integer (vs\($n))" | error else if .cache[$n] then .result = .cache[$n] else ($n|primePows) as $pps | if ($pps|length) == 1 then $pps[0][0] as $p | $pps[0][1] as $r | if $p > 2 then .cache[$n] = phi($p; $r) else .cache[$n] = phi($p; $r - 1) end | .result = .cache[$n] else .a = [] | reduce $pps[] as $pp (.; CarmichaelHelper($pp[0]; $pp[1]) | .a += [ .result ] ) | .cache[$n] = lcm(.a[]) | .result = .cache[$n] end end end ; # input: {cache} # output: {cache, result} def iteratedToOne($j): {global: ., k: 0, $j} | until( .j <= 1; .j as $j | .global |= CarmichaelLambda($j) | .j = .global.result | .k += 1 ) | .global.result = .k | .global; def task1($m): " n λ k", "----------", (foreach range(1; 1+$m) as $n ({}; CarmichaelLambda($n) | .result as $lambda | iteratedToOne($n) | .result as $k | .emit = "\($n|lpad(2)) \($lambda|lpad(2)) \($k|lpad(2))" ) | .emit ) ; def task2($maxI; $maxN): "\nIterations to 1 i lambda(i)", "=====================================", " 0 1 1", ( . // {} | .cache |= (. // cache) | .found = [true, (range(0; $maxN)|false)] | .i=1 | .n=null | while (.i <= $maxI and .n != $maxN; .emit = null | iteratedToOne(.i) | .n = .result | if (.found[.n]|not) then .found[.n] = true | CarmichaelLambda(.i) | .result as $lambda | .emit = "\(.n|lpad(4)) \(.i|lpad(18)) \($lambda|lpad(12))" end | .i += 1 ) | select(.emit).emit ); task1(25), "", task2(5*1e6; 15)

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 1439 1438 10 2879 2878 11 34549 34548 12 138197 138196 [...terminated...]

Julia

using DelimitedFiles using Primes const maxcached = typemax(Int32) const carmicache = zeros(Int32, maxcached) # NB: 8 gigabytes memory used for this size cache const rlock = ReentrantLock() """ Carmichael reduced totient function lambda(n) """ function lambda(n::Integer)  @assert n > 0  n <= maxcached && carmicache[n] > 0 && return Int(carmicache[n])  lam = 1  for (p, e) in factor(n)  if p == 2 && e > 2  lam = lcm(lam, 2^(e - 2))  else  lam = lcm(lam, (p - 1) * p^(e - 1))  end  end  if n <= maxcached  lock(rlock)  carmicache[n] = lam  unlock(rlock)  end  return lam end """  Return k for the k-fold iterated lambda function, where k is count of iterations to 1 """ function iterated_lambdas_to_one(i)  k = 0  while i > 1  i = lambda(i)  k += 1  end  return k end """   Calculate values for the task. Due to a runtime of several days for a sequence length  of 25, the function switches to multithreading for values over about 2 billion. Note  that (empirically) adjacent pairs of values within the sequence above 100000 are less  than a factor of 6 apart, so each next large value is sought within that range. """ function print_iterated_lambdas(upto = 25)  println("Listing of (n, lambda(n), k for iteration to 1) for integers from 1 to 25:")  firsts = zeros(Int, upto)  if isfile("lambdas.txt")  precalc = readdlm("lambdas.txt", Int64)  if length(precalc) == upto  firsts .= precalc # restore work done if resterted (since it takes days)  end  end  for i = 1:25  lam = lambda(i)  k = iterated_lambdas_to_one(i)  print("($i, $lam, $k)", i % 5 == 0 ? "\n" : " ")  end  target = something(findlast(!iszero, firsts), 1)  if firsts[target] < maxcached ÷ 7 # get first ones with single thread  for i = 2:maxcached  n = iterated_lambdas_to_one(i)  if n <= upto && (firsts[n] == 0 || firsts[n] > i)  firsts[n] = i  end  end  end  target = something(findlast(!iszero, firsts), 1) + 1  while target <= upto # multithreaded for larger targets  startval = firsts[target - 1] + 1  for j in startval:startval:startval*6  j += iseven(j) # make odd  @Threads.threads for i in j:2:j+startval-1 # should not be even if i > 2  n = iterated_lambdas_to_one(i)  if n == target  if firsts[n] == 0 || firsts[n] > i  try  lock(rlock)  firsts[n] = i  writedlm("lambdas.txt", firsts) # save work done for restarts  unlock(rlock)  catch y  unlock(rlock)  @warn y  rethrow()  end  end  break  end  firsts[target] > 0 && firsts[target] < i && break  end  end  target += 1  end  println("\nIterations to 1 n lambda(n)\n=====================================")  println(" 0 1 1")  for n = 1:upto  println(lpad(n, 4) * lpad(firsts[n], 17) * lpad(lambda(firsts[n]), 14))  end end print_iterated_lambdas()

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 21 3486784401 2324522934 22 10460353203 6973568802 23 31381059609 20920706406 24 94143178827 62762119218 25 282429536481 188286357654

Mathematica |Wolfram Language

Translation of: Python

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

Nim

Translation of: Wren

There are two differences with the Wren version.

First, we don’t use an external library to get the prime factors of the numbers. We proceed by trial division by prime numbers. The list of primes is built at compile time.

Second, we use the simpler Phix way to find the lowest integer for which the value of iterated "k" is "i".

import std/[math, strformat, strutils, sugar, tables] ############################################################################### # List of primes. const Lim = 100_000 proc primes(lim: static Positive): seq[int] {.compileTime.} =  ## Build the list of primes from 2 to "lim".  # Use a sieve of Eratosthenes.  var sieve: array[lim div 2, bool]  var p = 3  while p * p < lim:  if not sieve[(p - 3) div 2]:  for k in countup(p * p, lim, 2 * p):  sieve[(k - 3) div 2] = true  inc p, 2  # Build the list of primes.  result = @[2]  for p in countup(3, lim, 2):  if not sieve[(p - 3) div 2]:  result.add p const Primes = primes(Lim) ############################################################################### type  PrimePower = tuple[prime, power: int]  PrimePowers = seq[PrimePower] proc primePowers(n: Positive): PrimePowers =  var n = n  for p in Primes:  if p * p > n: break  var count = 0  while n mod p == 0:  n = n div p  inc count  if count != 0:  result.add (p, count)  if n != 1: result.add (n, 1) proc phi(p, r: Positive): int =  p ^ (r - 1) * (p - 1) var cache = {1: 1, 2: phi(2, 1), 4: phi(2, 2)}.toTable proc carmichaelHelper(p, r: Positive): int =  let n = p ^ r  if n in cache: return cache[n]  result = if p > 2: phi(p, r) else: phi(p, r - 1)  cache[n] = result proc carmichaelLambda(n: Positive): int =  if n in cache: return cache[n]  let pps = primePowers(n)  if pps.len == 1:  let (p, r) = pps[0]  result = if p > 2: phi(p, r) else: phi(p, r - 1)  else:  let a = collect(for (p, r) in pps: carmichaelHelper(p, r))  result = lcm(a)  cache[n] = result proc iterationsToOne(n: Positive): int =  var n = n  while n > 1:  n = carmichaelLambda(n)  inc result when isMainModule:  echo " n λ k"  echo "----------"  for n in 1..25:  echo &"{n:>2} {carmichaelLambda(n):>2} {iterationsToOne(n):>2}"  echo "\nIterations to 1 i lambda(i)"  echo "====================================="  var n = 1  for i in 0..16:  while iterationsToOne(n) != i:  inc n  echo &"{i:>4} {insertSep($n):>18} {insertSep($carmichaelLambda(n)):>12}"

Output:

On out computer, the execution time for i in 0..15 is about 6.3 seconds.

 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

For the stretch task, the execution time is not the first limiting factor. On our machine, we are only able to complete the stretch task for i in 16..18 before being out of memory. In fact, the cache which allows to save some time consumes a lot of memory.

For i in 1..18, the execution time is 3 min 30 s.

 16 14_348_907 9_565_938 17 43_046_721 28_697_814 18 86_093_443 86_093_442

Perl

# 20240925 Perl programming solution  use strict; use warnings; use ntheory qw(is_carmichael carmichael_lambda);  sub iterated_to_one {  my ($n) = @_;  for (my $k = 0;;) { ($n = carmichael_lambda($n)) > 1 ? $k++ : return ++$k } }  print " n λ k\n----------\n"; for my $n (1..25) {  printf "%2d %2d %2d\n", $n, carmichael_lambda($n), iterated_to_one($n) }  print "\nIterations to 1 i lambda(i)\n",'='x37,"\n"; print " 0 1 1\n";  my ($max_n, $max_i, @found) = (15, 5_000_000, (1)); for my $i (1 .. $max_i) {  unless ($found[ my $n = iterated_to_one($i) ]) {  printf "%4d %18d %12d\n", $n, $i, carmichael_lambda($i);  $n == $max_n ? last : ( $found[$n] = 1 )   } }

Output:

 n λ k ---------- 1 1 1 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 1 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

Translation of: Wren

# 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 😅

REXX

Translation of: Julia

Modules: How to use
Modules: Source code

The used recurring algorithm was also proposed by ChatGPT. Procedure Lambda(x) (in Numbers) returns the the lambda number for x.

-- 23 Aug 2025 include Setting say 'CARMICHAEL LAMBDA FUNCTION' say version say numeric digits 10 arg n if n = '' then  n = 25 call Time 'r' say '----------' say ' n l k' say '----------' do i = 1 to n  k = 1; a = Lambdan(i); b = a  do while b > 1  k = k+1; b = Lambdan(b)  end  say Right(i,2) Right(a,3) Right(k,3) end say '----------' say Format(Time('e'),,3) 'seconds' say say '----------' say ' k n' say '----------' call Time 'r' a = 1 do i = 1 to 15  do j = a until k = i  k = 0; b = j  do until b = 1  k = k+1; b = Lambdan(b)  end  end  say Right(k,2) Right(j,7)  a = j+1 end say '----------' say Format(Time('e'),,3) 'seconds' exit include Math

Output:

CARMICHAEL LAMBDA FUNCTION - 4 Mar 2025 REXX-ooRexx_5.0.0(MT)_64-bit 6.05 23 Dec 2022 ---------- n l k ---------- 1 1 1 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 ---------- 0.000 seconds ---------- k n ---------- 1 1 2 3 3 5 4 11 5 23 6 47 7 283 8 719 9 1439 10 2879 11 34549 12 138197 13 531441 14 1594323 15 4782969 ---------- 483.303 seconds

Because up to k = 15 this already takes 8 minutes, I didn't try the stretched task.

Rust

Works with: Rust

Translation of: C++

use std::cmp;  #[derive(Debug, Clone)] struct PrimePower {  prime: u32,  power: u32, }  impl PrimePower {  fn new(prime: u32, power: u32) -> Self {  PrimePower { prime, power }  } }  fn prime_powers(number: u32) -> Vec<PrimePower> {  let mut powers = Vec::new();  let mut n = number;    let mut i = 2;  while i * i <= n {  if n % i == 0 {  powers.push(PrimePower::new(i, 0));  while n % i == 0 {  powers.last_mut().unwrap().power += 1;  n /= i;  }  }  i += 1;  }    if n > 1 {  powers.push(PrimePower::new(n, 1));  }    powers }  fn gcd(a: u32, b: u32) -> u32 {  if b == 0 {  a  } else {  gcd(b, a % b)  } }  fn lcm(a: u32, b: u32) -> u32 {  (a / gcd(a, b)) * b }  fn carmichael_lambda(number: u32) -> u32 {  if number == 1 {  return 1;  }    let powers = prime_powers(number);  let mut result = 1;    for prime_power in powers {  let mut car = (prime_power.prime - 1) * prime_power.prime.pow(prime_power.power - 1);  if prime_power.prime == 2 && prime_power.power >= 3 {  car /= 2;  }  result = lcm(result, car);  }    result }  fn count_iterations_to_one(n: u32) -> u32 {  if n <= 1 {  0  } else {  count_iterations_to_one(carmichael_lambda(n)) + 1  } }  fn main() {  println!(" n carmichael(n) iterations(n)");  println!("--------------------------------");    for i in 1..=25 {  println!("{:2}{:10}{:14}",   i,   carmichael_lambda(i),   count_iterations_to_one(i));  }    println!();  println!("Iterations to 1 n lambda(n)");  println!("-----------------------------------");    let mut n = 1;  for i in 0..=15 {  while count_iterations_to_one(n) != i {  n += 1;  }  println!("{:2}{:19}{:13}", i, n, carmichael_lambda(n));  } }

Output:

 n carmichael(n) iterations(n) -------------------------------- 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

Sidef

Built-in as Number#carmichael_lambda:

func iteratedToOne(n) {  var k = 0  while (n > 1) {  n.carmichael_lambda!  ++k  }  return k } say " n λ k" say "----------" for n in (1..25) {  printf("%2d %2d %2d\n", n, n.carmichael_lambda, iteratedToOne(n)) } say "\nIterations to 1 i lambda(i)" say "=====================================" var table = [] 1..Inf -> each {|k|  var n = iteratedToOne(k)  if (!table[n]) {  table[n] = true  printf("%4s %18s %12s\n", n, k, k.carmichael_lambda)  break if (n == 15)  } }

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 1439 1438 10 2879 2878 11 34549 34548 12 138197 138196 13 531441 354294 14 1594323 1062882 15 4782969 3188646

Wren

Library: Wren-math

Library: Wren-fmt

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

Zig

Works with: Zig version 0.14.1

Translation of: Rust

const std = @import("std"); const print = std.debug.print; const ArrayList = std.ArrayList; const Allocator = std.mem.Allocator;  const PrimePower = struct {  prime: u32,  power: u32,   fn init(prime: u32, power: u32) PrimePower {  return PrimePower{  .prime = prime,  .power = power,  };  } };  fn primePowers(allocator: Allocator, number: u32) !ArrayList(PrimePower) {  var powers = ArrayList(PrimePower).init(allocator);  var n = number;    var i: u32 = 2;  while (i * i <= n) {  if (n % i == 0) {  try powers.append(PrimePower.init(i, 0));  while (n % i == 0) {  powers.items[powers.items.len - 1].power += 1;  n /= i;  }  }  i += 1;  }    if (n > 1) {  try powers.append(PrimePower.init(n, 1));  }    return powers; }  fn gcd(a: u32, b: u32) u32 {  if (b == 0) {  return a;  } else {  return gcd(b, a % b);  } }  fn lcm(a: u32, b: u32) u32 {  return (a / gcd(a, b)) * b; }  fn pow(base: u32, exponent: u32) u32 {  var result: u32 = 1;  var exp = exponent;  var b = base;    while (exp > 0) {  if (exp % 2 == 1) {  result *= b;  }  b *= b;  exp /= 2;  }    return result; }  fn carmichaelLambda(allocator: Allocator, number: u32) !u32 {  if (number == 1) {  return 1;  }    var powers = try primePowers(allocator, number);  defer powers.deinit();    var result: u32 = 1;    for (powers.items) |prime_power| {  var car = (prime_power.prime - 1) * pow(prime_power.prime, prime_power.power - 1);  if (prime_power.prime == 2 and prime_power.power >= 3) {  car /= 2;  }  result = lcm(result, car);  }    return result; }  fn countIterationsToOne(allocator: Allocator, n: u32) !u32 {  if (n <= 1) {  return 0;  } else {  const lambda = try carmichaelLambda(allocator, n);  const iterations = try countIterationsToOne(allocator, lambda);  return iterations + 1;  } }  pub fn main() !void {  var gpa = std.heap.GeneralPurposeAllocator(.{}){};  defer _ = gpa.deinit();  const allocator = gpa.allocator();   print(" n carmichael(n) iterations(n)\n" , .{});  print("--------------------------------\n", .{});    var i: u32 = 1;  while (i <= 25) : (i += 1) {  const lambda = try carmichaelLambda(allocator, i);  const iterations = try countIterationsToOne(allocator, i);  print("{d:2}{d:10}{d:14}\n", .{ i, lambda, iterations });  }    print("\n", .{});  print("Iterations to 1 n lambda(n)\n", .{});  print("-----------------------------------\n", .{});    var n: u32 = 1;  i = 0;  while (i <= 15) : (i += 1) {  while (true) {  const iterations = try countIterationsToOne(allocator, n);  if (iterations == i) break;  n += 1;  }  const lambda = try carmichaelLambda(allocator, n);  print("{d:2}{d:19}{d:13}\n", .{ i, n, lambda });  } }

Output:

 n carmichael(n) iterations(n) -------------------------------- 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 ...