A127699 Length of period of the sequence (1^1^1^..., 2^2^2^..., 3^3^3^..., 4^4^4^..., ...) modulo n.

1, 2, 6, 4, 20, 6, 42, 8, 18, 20, 220, 12, 156, 42, 60, 16, 272, 18, 342, 20, 42, 220, 5060, 24, 100, 156, 54, 84, 2436, 60, 1860, 32, 660, 272, 420, 36, 1332, 342, 156, 40, 1640, 42, 1806, 220, 180, 5060, 237820, 48, 294, 100, 816, 156, 8268, 54, 220, 168

Offset: 1

Author

Jan Fricke, Apr 11 2007

Keywords

• easy
• nonn

Comments

For any positive integers a and m the sequence a, a^a, a^a^a, a^a^a^a,... becomes eventually constant modulo m. So the remainder of a^a^a^... modulo n is well-defined.

Shapiro and Shapiro treat this problem. - T. D. Noe, Jan 30 2009

Examples

			a(10)=20 because the last digit of 1^1^1^.. is 1; the sequence 2,2^2,2^2^2,.. ends with 2,4,6,6,...; the sequence 3,3^3,3^3^3,... with 3,7,7,...; 4,4^4,4^4^4,... with 4,6,6,...; and so on. We get as last digits 1,6,7,6,5,6,3,6,9,0, 1,6,3,6,5,6,7,6,9,0 and then the pattern repeats.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
• Daniel B. Shapiro and S. David Shapiro, Iterated Exponents in Number Theory, Integers 7 (2007), #A23.

Crossrefs

Cf. A002322.

Programs

Maple

a:= proc(n) option remember; `if`(n=1, 1,
      ilcm(n, a(numtheory[lambda](n))))
    end:
seq(a(n), n=1..56);  # Alois P. Heinz, Jan 03 2023

Mathematica

nn=100; a=Table[0,{nn}]; a[[1]]=1; Do[a[[n]]=LCM[n,a[[CarmichaelLambda[n]]]], {n,2,nn}]; a (* T. D. Noe, Jan 30 2009 *)

Python

from functools import lru_cache
from math import lcm
from sympy import reduced_totient
@lru_cache(maxsize=None)
def A127699(n): return 1 if n == 1 else lcm(n, A127699(reduced_totient(n))) # Chai Wah Wu, Jan 03 2023

Formula

a(n) = lcm(n, a(lambda(n))), where lambda is Carmichael's reduced totient function. - T. D. Noe, Jan 30 2009

Extensions

Extension and correction from T. D. Noe, Jan 30 2009

Incorrect formula removed by T. D. Noe, Feb 02 2009