login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A242595 a(n) is the primitive period length for the sequence 2^k (mod n), k = 1, 2, ... 1

%I #15 Aug 13 2017 16:27:16

%S 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,

%T 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,

%U 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

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

%C The computation of this sequence was inspired by _Gary Detlefs_'s May 15 2014 comment on A050229.

%C 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.

%C 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).

%C a(prime) = phi(prime) = prime - 1 (phi is given in A000010) is equivalent to: prime divides 2^k*(2^(prime-1) - 1), for all k >= 1, and prime-1 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.

%C For composite odd numbers m one has: m divides (2^a(m) - 1) with the smallest such a(m).

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

%e a(1) = 1 because 2^1 == 0 == 1 (mod 1), therefore 2^k (mod 1) is the 0-sequence with primitive period length 1.

%e a(2) = 1 because 2^k == 0 (mod 2) for k >= 1, hence also the 0-sequence with primitive period length 1. Note that 2 is not a primitive root of 2 even though a(2) = 2-1 = 1 (see the comment above).

%e a(3) = 3-1 = 2 because 3 is odd and 2 is a primitive root modulo 3. See A001122(1).

%e 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.

%e a(4) = 0 because a(4*m) = 0 for all m >= 1 (see the comment above).

%e a(6) = 2 because the sequence starts with 2, 4, 2, ... and

%e 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.

%e a(9) = 6 from the sequence start 2, 4, 8, 7, 5, 1,... Note that a(3^2) = (3-1)*3. a(5^2) = 20 = (4-1)*5. But a(7^2) = 21 = (7-1)*7/2.

%Y Cf. A000010, A050229, A060749, A001122, A216838.

%K nonn,easy

%O 1,3

%A _Wolfdieter Lang_, May 18 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)