A118107 -id:A118107 - cp's OEIS frontend

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

T. D. Noe, Apr 13 2006

nonn

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)

			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.

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

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

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

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

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

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula