|
%I #25 Nov 04 2019 01:00:20
%S 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,
%T 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,
%U 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
%N 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.
%C 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.
%C 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
%C From _Jianing Song_, Nov 03 2019: (Start)
%C 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).
%C 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).
%C 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)
%H Antti Karttunen, <a href="/A118106/b118106.txt">Table of n, a(n) for n = 1..65537</a> (terms 1..1000 from T. D. Noe)
%F 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
%e 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.
%t 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}]
%o (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
%o (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
%Y Cf. A118107 (period of the vector sequence d(n)^2^k mod n), A051903.
%K nonn
%O 1,6
%A _T. D. Noe_, Apr 13 2006
|
