login
Numbers that begin a run of consecutive integers k such that PrimePi(k) divides 2^k.
3

%I #37 Dec 06 2020 06:28:57

%S 2,7,19,53,131,311,719,1619,3671,8161,17863,38873,84017,180503,386093,

%T 821641,1742537,3681131,7754077,16290047,34136029,71378569,148948139,

%U 310248241,645155197,1339484197,2777105129,5750079047,11891268401,24563311309,50685770167,104484802057,215187847711

%N Numbers that begin a run of consecutive integers k such that PrimePi(k) divides 2^k.

%C It seems that each term is a bit larger than twice the previous one.

%C Runs have lengths 3, 4, 4, 6, 6, 2, 8, 2, 2, 6, 18, 18, 30, 8, 24, 6, 2, 18, ..., respectively.

%C From _Chai Wah Wu_, Jan 27 2020: (Start)

%C Theorem: a(1) = 2 and a(n) = A033844(n) for n > 1. For n > 1, the length of the n-th run is prime(2^n+1)-prime(2^n) = A051439(n)-A033844(n) = A074325(n).

%C Proof: Let r > 1. If p = prime(2^r), then primepi(p) = 2^r.

%C primepi(p-1) = 2^r - 1. Since r > 1, 2^r - 1 > 2 and odd and thus does not divide any power of 2.

%C In addition 2^r < p and thus divides 2^p. This means that p is a term. Let q be such that p < q < prime(2^r+1). Then primepi(q) = 2^r and divides 2^q. Since primepi(q-1) = 2^r and divides 2^(q-1), this means that q does not start a run and thus is not a term.

%C Let w be such that prime(2^r+1) <= w < prime(2^(r+1)). Then 2^r + 1 <= primepi(w) < 2^(r+1) and does not divide any power of 2. This means that w is not a term.

%C (End)

%H Chai Wah Wu, <a href="/A073799/b073799.txt">Table of n, a(n) for n = 1..57</a>

%F Solutions to 2^(x-1) mod PrimePi(x-1) > 0 but 2^x mod PrimePi(x) = 0.

%F a(n) = A033844(n) for n > 1. - _Chai Wah Wu_, Jan 27 2020

%t aQ[k_] := Divisible[2^k, PrimePi[k]]; s = {}; len = {}; n = 2; While[Length[s] < 10, While[! aQ[n], n++]; n1 = n; While[aQ[n], n++]; If[n > n1, AppendTo[s, n1]; AppendTo[len, n - n1]]; n++]; s (* _Amiram Eldar_, Dec 11 2018 *)

%o (Python)

%o from sympy import prime

%o def A073799(n):

%o return 2 if n == 1 else prime(2**n) # _Chai Wah Wu_, Jan 27 2020

%o (PARI) a(n) = if(n==1, 2, prime(2^n)); \\ _Jinyuan Wang_, Mar 01 2020

%Y Cf. A000079, A000720, A015910, A062173, A064367, A073797, A073798.

%Y Cf. A033844. - _R. J. Mathar_, Sep 23 2008

%Y Cf. A051439, A074325.

%K nonn

%O 1,1

%A _Labos Elemer_, Aug 12 2002

%E Edited by _Jon E. Schoenfield_, Dec 10 2018

%E a(15)-a(18) from _Amiram Eldar_, Dec 11 2018

%E a(19)-a(33) from _Chai Wah Wu_, Jan 27 2020