A081858 - OEIS

%I #33 Mar 03 2024 19:24:33

%S 0,3,8,11,15,20,23,35,36,39,44,48,51,56,63,68,75,83,95,96,99,111,116,

%T 119,120,128,131,135,140,155,156,168,170,176,179,183,191,200,204,215,

%U 216,219,224,228,231,239,243,251,260,280,284,288,296,299,300,303,308

%N Numbers k such that 2*k+1 divides 2^k-1.

%C From _Chris Boyd_, Mar 16 2014: (Start)

%C n is a term if and only if n=0, 2n+1 is a prime of the form 8k+-1, or 2n+1 is an Euler pseudoprime satisfying 2^n == 1 mod 2n+1.

%C Case 1: 0 is a term. Case 2, 2n+1 prime: by Euler's criterion and the quadratic character of 2, 2^n == 1 mod 2n+1 only if 2n+1 is of the form 8k+-1. Case 3, 2n+1 composite: 2^n == 1 mod 2n+1 only if 2n+1 is one of the subset of Euler pseudoprimes satisfying 2^n == 1 mod 2n+1.

%C The first term for which 2n+1 is a qualifying Euler pseudoprime is n=170.

%C The first Euler pseudoprime that does not correspond to a term is 3277, because 2^((3277-1)/2) == -1 mod 3277. (End)

%H Amiram Eldar, <a href="/A081858/b081858.txt">Table of n, a(n) for n = 1..10000</a>

%F k such that A002326(k)|k: since 2^k == 1 mod 2*k+1, k must be a multiple of the order of 2 mod 2*k+1.

%t Join[{0}, Select[Range[300], PowerMod[2, #, 2*# + 1] === 1 &]] (* _Amiram Eldar_, Jun 02 2022 *)

%o (PARI) isok(n) = !((2^n-1) % (2*n+1)); \\ _Michel Marcus_, Dec 04 2013

%o (PARI) for(n=0,400,if(n%znorder(Mod(2,2*n+1))==0,print1(n","))) \\ _Chris Boyd_, Mar 16 2014, after _Michael Somos_ in A002326

%Y Cf. A002326, A014664.

%K nonn

%O 1,2

%A _Benoit Cloitre_, Apr 11 2003

%E Formula corrected by _Chris Boyd_, Mar 16 2014