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.

Carmichael lambda function
You are encouraged to solve this task according to the task description, using any language you may know.

Background

The Carmichael function, or Carmichael lambda function, is a function in numeric theory. The Carmichael lambda λ(n) of a positive integer n is the smallest positive integer n such that

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

• Wikipedia entry for Carmichael function
•   OEIS lambda(lamda(n)) function sequence

Python

Python has the Carmichael function in the SymPy library, where is 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 = 1_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

Wren

Library: Wren-math

Library: Wren-fmt

Takes about 158 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 = {}

var CarmichaelLambda = Fn.new { |n|
    if (n < 1) Fiber.abort("'n' must be a positive integer.")
    if (cache.containsKey(n)) return cache[n]
    if (n == 1) return 1
    if (n == 2) return phi.call(2, 1)
    if (n == 4) return phi.call(2, 2)
    var pps = primePows.call(n)
    if (pps.count == 1) {
        var p = pps[0][0]
        var r = pps[0][1]
        if (p % 2 == 1) return phi.call(p, r)
        if (p == 2 && r >= 3) return phi.call(p, r) / 2
    }
    var a = []
    for (pp in pps) a.add(CarmichaelLambda.call(pp[0].pow(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(" i   λ   k")
System.print("----------")
for (i in 1..25) {
    var lambda = CarmichaelLambda.call(i)
    var k = iteratedToOne.call(i)
    Fmt.print("$2d  $2d  $2d", i, lambda, k)
}

System.print("\nIterations to 1       n     lambda(n)")
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:

 i   λ   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       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