login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of distinct sequences {i^k mod n; i >= 0} with k >= 0.
1

%I #9 Sep 08 2024 13:47:36

%S 1,2,3,4,5,3,7,5,8,5,11,4,13,7,5,8,17,8,19,6,7,11,23,5,22,13,21,8,29,

%T 5,31,13,11,17,13,8,37,19,13,7,41,7,43,12,14,23,47,8,44,22,17,14,53,

%U 21,21,9,19,29,59,6,61,31,8,22,13,11,67,18,23,13,71,9,73,37,22,20,31,13,79,8

%N Number of distinct sequences {i^k mod n; i >= 0} with k >= 0.

%H David W. Wilson, <a href="/A134198/b134198.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A051903(n) + A002322(n).

%e Let S(k) be the sequence (0^k, 1^k, 2^k, ...) mod 8. S(k) is periodic with period 8 and we find that (1,1,1,1,1,1,1,1,...) = S(0), (0,1,2,3,4,5,6,7,...) = S(1), (0,1,4,1,0,1,4,1,...) = S(2), (0,1,0,3,0,5,0,7,...) = S(3) = S(5) = S(7) = ... and (0,1,0,1,0,1,0,1,...) = S(4) = S(6) = S(8) = ... The first A002322(8) = 3 sequences occur for exactly one value of k. The remaining A051903(8) = 2 sequences occur for an infinite number of k. This gives a(8) = 3+2 = 5.

%t a[n_] := Max[FactorInteger[n][[;;, 2]]] + CarmichaelLambda[n]; a[1] = 1; Array[a, 100] (* _Amiram Eldar_, Sep 07 2024 *)

%o (PARI) a(n) = if(n == 1, 1, my(f = factor(n)); vecmax(f[, 2]) + lcm(znstar(f)[2])); \\ _Amiram Eldar_, Sep 07 2024

%Y Cf. A002322, A051903.

%K nonn,easy

%O 1,2

%A _David W. Wilson_, Oct 13 2007