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.

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

Offset: 1

Author

T. D. Noe, Apr 13 2006

Keywords

• nonn

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)

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from T. D. Noe)

Crossrefs

Cf. A118107 (period of the vector sequence d(n)^2^k mod n), A051903.

Programs

Mathematica

Table[d=Divisors[n]; k=0; found=False; While[i=0; While[i
				

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

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