A085427 - OEIS

%I #38 Dec 19 2019 05:55:58

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

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

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

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

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

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

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

%C a(n) = 1 if and only if n is in A000043. - _Felix Fröhlich_, Sep 14 2014

%H Pierre CAMI, <a href="/A085427/b085427.txt">Table of n, a(n) for n = 0..3000</a>

%F a(n) << 19^n by Xylouris's improvement to Linnik's theorem. - _Charles R Greathouse IV_, Dec 10 2013

%t 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 *)

%o (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

%Y Cf. A035050, A057778, A126717.

%K nonn

%O 0,1

%A _Jason Earls_, Aug 13 2003