A109746 Number of distinct sequences of the type m^k mod n for n fixed, k>=1.

1, 2, 3, 4, 2, 6, 4, 7, 4, 10, 3, 12, 6, 4, 7, 16, 7, 18, 5, 6, 10, 22, 4, 21, 12, 20, 7, 28, 4, 30, 12, 10, 16, 12, 7, 36, 18, 12, 6, 40, 6, 42, 11, 13, 22, 46, 7, 43, 21, 16, 13, 52, 20, 20, 8, 18, 28, 58, 5, 60, 30, 7, 21, 12, 10, 66, 17, 22, 12, 70, 8, 72

Offset

2,2

Comments

It appears that a(p)= p-1 (for prime p) and a(2p) = p-1 (for odd prime p), but this is only speculation. I (or someone else) need to calculate more values of a(n) to settle this conjecture.

From Lars Blomberg, Oct 27 2015: (Start)

It also appears that:

When all factors of n have multiplicity=1 then a(n)=lcm(all factors - 1).

When n=p^2 then a(n)=n-p+1.

When n=2^k, k>2 then a(n)=2^(k-2)+k-1.

These conjectures hold for n <= 10000. (End)

Links

Lars Blomberg, Table of n, a(n) for n = 2..10000

Charles Burnette, On power maps over weakly periodic rings, arXiv:2207.14283 [math.RA], 2022. See p. 11 for a proof of the conjectures.

Formula

a(n) = A002322(n) + A051903(n) - 1 (conjectured). - Ben Whitmore, Jul 23 2020

Example

m mod 4 = {0,1,2,3,0,1,2,3,...}; m^2 mod 4 = {0,1,0,1,...}; m^3 mod 4 = {0,1,0,3,0,1,0,3,...}; but m^4 mod 4 = {0,1,0,1} = m^2 mod 4; so for higher powers of m these sequences cycle and are not distinct, thus for mod 4 we have {0,1,2,3}, {0,1} and {0,1,0,3} as distinct, so a(4) = 3.

Crossrefs

Cf. A002322, A051903.

Sequence in context: A361697 A091732 A299439 * A286365 A345061 A061020

Adjacent sequences: A109743 A109744 A109745 * A109747 A109748 A109749

Keyword

nonn

Author

Bruce Corrigan (scentman(AT)myfamily.com), Aug 10 2005

Extensions

More terms from Lars Blomberg, Oct 27 2015

Status

approved