|
| |
|
|
A118106
|
|
Period of the vector sequence d(n)^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.
|
|
6
|
|
|
|
1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 3, 4, 1, 1, 6, 1, 4, 6, 10, 1, 2, 1, 12, 1, 6, 1, 4, 1, 1, 10, 8, 12, 6, 1, 18, 3, 4, 1, 6, 1, 10, 12, 11, 1, 4, 1, 20, 16, 12, 1, 18, 5, 6, 18, 28, 1, 4, 1, 5, 6, 1, 4, 10, 1, 8, 22, 12, 1, 6, 1, 36, 20, 18, 30, 12, 1, 4, 1, 20, 1, 6, 16, 14, 28, 10, 1, 12, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
