Carmichael lambda function

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

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

$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