OFFSET
1,6
COMMENTS
This sequence is related to the period of sigma_k(n) mod n. Note that a(n)=1 iff n is a power of a prime.
The record periods of p-1 occur at n=2p, where p is a prime with primitive root 2 (A001122). - T. D. Noe, Oct 25 2007
From Jianing Song, Nov 03 2019: (Start)
The smallest index m such that from the m-th term on, the sequence {d(n)^k mod n: k >= 0} enters into a cycle is m = A051903(n).
Let b(n) be the period of {sigma_k(n) mod n: k >= 0}, then b(n) | a(n) for all n, but generally they are not necessarily the same (for example, a(576) = 48 while b(576) = 16).
Every number m occurs in this sequence. Suppose m != 1, 6, by Zsigmondy's theorem, 2^m - 1 has at least one primitive factor p. Here a primitive factor p means that ord(2,p) = m. So we have a(2p) = lcm(ord(2,p), ord(p,2)) = m (see the formula below). Specially, we have a(2*A112927(m)) = a(2*A097406(m)) = m for m != 1, 6. (End)
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from T. D. Noe)
FORMULA
Write n = Product_{i=1..t} p_i^e_i, then a(n) = lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j), where ord(a,r) is the multiplicative order of a modulo r. - Jianing Song, Nov 03 2019
EXAMPLE
a(35)=12 because d(35)=(1,5,7,35) and (1,5,7,35)^k (mod 35) is the sequence of vectors (1,5,7,0), (1,25,14,0), (1,20,28,0), (1,30,21,0), (1,10,7,0), (1,15,14,0), (1,5,28,0), (1,25,21,0), (1,20,7,0), (1,30,14,0), (1,10,28,0), (1,15,21,0), (1,5,7,0),..., which has a period of 12.
MATHEMATICA
Table[d=Divisors[n]; k=0; found=False; While[i=0; While[i<k-1 && !found, i++; found=(dk[i]==dk[k])]; !found, k++; dk[k]=PowerMod[d, k, n]]; k-i, {n, 100}]
PROG
(PARI) A118106(n) = { my(divs=apply(d -> (d%n), divisors(n)), odivs = Vec(divs), vs = Map()); mapput(vs, odivs, 0); for(k=1, oo, divs = vector(#divs, i, (divs[i]*odivs[i])%n); if(mapisdefined(vs, divs), return(k-mapget(vs, divs)), mapput(vs, divs, k))); }; \\ Antti Karttunen, Sep 23 2018
(PARI) a(n) = my(m=omega(n), M=vector(m^2), f=factor(n)); for(i=1, m, for(j=1, m, M[(i-1)*m+j]=if(i==j, 1, znorder(Mod(f[i, 1], f[j, 1]^f[j, 2]))))); lcm(M) \\ Jianing Song, Nov 03 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
T. D. Noe, Apr 13 2006
STATUS
approved