user
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

:   a

    m
    ≡
    1


    (
    mod

    n
    )
    {\displaystyle {\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

:   * Wikipedia entry for Carmichael function
    * OEIS lambda(lambda(n)) function sequence
assistant
**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 😅