

A242595


a(n) is the primitive period length for the sequence 2^k (mod n), k = 1, 2, ...


0



1, 1, 2, 0, 4, 2, 3, 0, 6, 4, 10, 0, 12, 3, 4, 0, 8, 6, 18, 0, 6, 10, 11, 0, 20, 12, 18, 0, 28, 4, 5, 0, 10, 8, 12, 0, 36, 18, 12, 0, 20, 6, 14, 0, 12, 11, 23, 0, 21, 20, 8, 0, 52, 18, 20, 0, 18, 28, 58, 0, 60, 5, 6, 0, 12, 10, 66, 0, 22, 12, 35, 0, 9, 36, 20, 0, 30, 12, 39, 0, 54, 20, 82, 0, 8, 14, 28, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The computation of this sequence was inspired by Gary Detlefs's May 15 2014 comment on A050229.
It is clear that 2^k (mod 4*m), for k >= 1 is not periodic because otherwise 4*m would divide 2^k*(2^P  1) for all k >= 1, with P >= 1 the period length. But this is false for k = 1. Therefore, a(4*m) = 0.
a(2*(2*m+1)) = a(2*m+1), m = (0), 1, 2, ... because 2*(2*m+1) has to divide 2^k*(2^a(2*(2*m+1)  1) for each k >= 1, which means that (2*m+1) has to divide (2^a(2*(2*m+1))  1), and a(2*(2*m+1)) has to be the smallest such number. But the smallest number P such that (2*m+1) divides (2^P  1) is P = a(2*m+1).
a(prime) = phi(prime) = prime  1 (phi is given in A000010) is equivalent to: prime divides 2^k*(2^(prime1)  1), for all k >= 1, and prime1 is the smallest exponent. For the even prime 2 this is trivial, and for an odd prime p this means that p divides 2^phi(prime)  1, but not with a smaller exponent; that is 2 is a primitive root modulo this odd p. See A001122 for the primes with primitive root 2. This means that a(prime) = prime  1 exactly for 2 and the odd primes of A001122. The odd primes with no primitive root 2 are given in A216838.
For composite odd numbers m one has: m divides (2^a(m)  1) with the smallest such a(m).


LINKS

Table of n, a(n) for n=1..88.


FORMULA

a(n) is the primitive (smallest) period length of the sequence 2^k (mod n), for k >=1, and n >= 1.


EXAMPLE

a(1) = 1 because 2^1 == 0 == 1 (mod 1), therefore 2^k (mod 1) is the 0sequence with primitive period length 1.
a(2) = 1 because 2^k == 0 (mod 2) for k >= 1, hence also the 0sequence with primitive period length 1. Note that 2 is not a primitive root of 2 even though a(2) = 21 = 1 (see the comment above).
a(3) = 31 = 2 because 3 is odd and 2 is a primitive root modulo 3. See A001122(1).
a(7) = 3 because the sequence 2^k (mod 7) starts 2, 4, 1, ... therefore the primitive period is 2, 4, 1 of length 3, because 2^(k+3) = 2^k*8 == 2^k*1 (mod 7) == 2^k (mod 7) for all k >= 1. The prime 7 belongs to A216838.
a(4) = 0 because a(4*m) = 0 for all m >= 1 (see the comment above).
a(6) = 2 because the sequence starts with 2, 4, 2, ... and
6 = 2*3 divides 2^k*(2^2  1) = 2^k*3 for all k >= 1. That is a(6) = a(3); see a comment above.
a(9) = 6 from the sequence start 2, 4, 8, 7, 5, 1,... Note that a(3^2) = (31)*3. a(5^2) = 20 = (41)*5. But a(7^2) = 21 = (71)*7/2.


CROSSREFS

Cf. A000010, A050229, A060749, A001122, A216838.
Sequence in context: A308022 A001100 A218831 * A136265 A066910 A094405
Adjacent sequences: A242592 A242593 A242594 * A242596 A242597 A242598


KEYWORD

nonn,easy


AUTHOR

Wolfdieter Lang, May 18 2014


STATUS

approved



