A085427 Least k such that k*2^n - 1 is prime.

3, 2, 1, 1, 2, 1, 2, 1, 5, 7, 5, 3, 2, 1, 5, 4, 2, 1, 2, 1, 14, 7, 26, 13, 39, 22, 11, 16, 8, 4, 2, 1, 5, 6, 3, 24, 12, 6, 3, 25, 24, 12, 6, 3, 14, 7, 20, 10, 5, 19, 11, 21, 20, 10, 5, 3, 32, 16, 8, 4, 2, 1, 12, 6, 3, 67, 63, 43, 63, 40, 20, 10, 5, 15, 12, 6, 3, 55, 47, 30, 15, 30, 15, 64, 32, 16, 8

Offset: 0

Author

Jason Earls, Aug 13 2003

Keywords

• nonn

Comments

First few pairs (n,k) such that k > n are (1,2), (22,26), (24,39), (65,67), (110,150), (112,140), (135,150), (137,169), ... Also, for n=398 there is an interesting anomaly since k=893 which is > 2n.

Conjecture: for every n there exists a number k < 3n such that k*2^n - 1 is prime. Comment from T. D. Noe: this fails at n=624, where a(n)=2163.

Define sumk = Sum_{n=1..N} k(n), and define sumn = Sum_{n=1..N} n, then as N increases the ratio sumk/sumn tends to log(2)/2 = 0.3465735.... so on average k(n) is about 0.35*n and seems to be always < 3.82*n or 11*log(2)/2. - Pierre CAMI, Feb 27 2009

a(n) = 1 if and only if n is in A000043. - Felix Fröhlich, Sep 14 2014

Links

• Pierre CAMI, Table of n, a(n) for n = 0..3000

Crossrefs

Cf. A035050, A057778, A126717.

Programs

Mathematica

k2np[n_]:=Module[{k=1,x=2^n},While[!PrimeQ[k x-1],k++];k]; Array[ k2np,90,0] (* Harvey P. Dale, Nov 19 2011 *)

PARI

lim=10^9; for(n=0, 200, k=1; i=0; while(k < lim, if(ispseudoprime(k*2^n-1), print1(k, ", "); i++; break({1})); if(i==0 && k >= lim-1, print1(">", lim, ", "); i=0); k++)) \\ Felix Fröhlich, Sep 20 2014

Formula

a(n) << 19^n by Xylouris's improvement to Linnik's theorem. - Charles R Greathouse IV, Dec 10 2013