login
Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary).
39

%I #71 Nov 02 2023 12:32:56

%S 2,3,7,23,31,311,127,383,991,2039,3583,6143,8191,73727,63487,129023,

%T 131071,522239,524287,1966079,4128767,16250879,14680063,33546239,

%U 67108351,201064447,260046847,536739839,1073479679,5335154687,2147483647

%N Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary).

%C a(n) = 2^n - 1 for n in A000043, so Mersenne primes A000668 is a subsequence of this one. Binary length of a(n) is given by A110699 and the number of zeros in a(n) is given by A110700. - _Max Alekseyev_, Aug 03 2005

%C Drmota, Mauduit, & Rivat prove that a(n) exists for n > N for some N. - _Charles R Greathouse IV_, May 17 2010

%H Charles R Greathouse IV, <a href="/A061712/b061712.txt">Table of n, a(n) for n = 1..3320</a> (first 1024 terms from T. D. Noe)

%H Michael Drmota, Christian Mauduit, and Joel Rivat, <a href="http://www.dmg.tuwien.ac.at/drmota/DMRcomp2.pdf">Primes with an average sum of digits</a>, Compositio Mathematica 145 (2009), pp. 271-292.

%H Kenichiro Kashihara, <a href="https://drive.google.com/file/d/1_2GOlV4IvXJaUci7lYLgBx_brlILl9IA/view">Letter to the Editor</a>, Math. Scientist 20 (1) (1995), 67-68.

%H MathOverflow, <a href="http://mathoverflow.net/questions/22629">Are there primes of every Hamming weight?</a>

%H Samuel S. Wagstaff, <a href="http://projecteuclid.org/euclid.em/999188636">Prime numbers with a fixed number of one bits or zero bits in their binary representation</a>, Experimental Mathematics 10 (2001), pp. 267-273.

%F Conjecture: a(n) < 2^(n+3). - _T. D. Noe_, Mar 14 2008

%F A000120(a(n)) = A014499(A049084(a(n))) = n. - _Reinhard Zumkeller_, Feb 10 2013

%e The fourth term is 23 (10111 in binary), since no prime less than 23 has exactly 4 1's in its binary representation.

%p with(combstruct); a:=proc(n) local m,is,s,t,r; if n=1 then return 2 fi; r:=+infinity; for m from 0 to 100 do is := iterstructs(Combination(n-2+m),size=n-2); while not finished(is) do s := nextstruct(is); t := 2^(n-1+m)+1+add(2^i,i=s); # print(s,t); if isprime(t) then r:=min(t,r) fi; od; if r<+infinity then return r fi; od; return 0; end; seq(a(n),n=1..60); # _Max Alekseyev_, Aug 03 2005

%t Do[k = 1; While[ Count[ IntegerDigits[ Prime[k], 2], 1] != n, k++ ]; Print[ Prime[k]], {n, 1, 30} ]

%t (* Second program: *)

%t a[n_] := Module[{m, s, k, p}, For[m=0, True, m++, s = {1, Sequence @@ #, 1} & /@ Permutations[Join[Table[1, {n-2}], Table[0, {m}]]] // Sort; For[k=1, k <= Length[ s], k++, p = FromDigits[s[[k]], 2]; If[PrimeQ[p], Print["a(", n, ") = ", p]; Return[p]]]]]; a[1] = 2; Array[a, 100] (* _Jean-François Alcover_, Mar 16 2015 *)

%t Module[{hw=Table[{n,DigitCount[n,2,1]},{n,Prime[Range[250*10^6]]}]}, Table[ SelectFirst[hw,#[[2]]==k&],{k,31}]][[All,1]] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale_, Jan 01 2019 *)

%o (Haskell)

%o a061712 n = fromJust $ find ((== n) . a000120) a000040_list

%o -- _Reinhard Zumkeller_, Feb 10 2013

%o (PARI) a(n)=forprime(p=2, , if (hammingweight(p) == n, return(p));); \\ _Michel Marcus_, Mar 16 2015

%o (Python)

%o from itertools import combinations

%o from sympy import isprime

%o def A061712(n):

%o l, k = n-1, 2**n

%o while True:

%o for d in combinations(range(l-1,-1,-1),l-n+1):

%o m = k-1 - sum(2**(e) for e in d)

%o if isprime(m):

%o return m

%o l += 1

%o k *= 2 # _Chai Wah Wu_, Sep 02 2021

%Y Cf. A000043, A000120, A000668, A001348, A014499, A049084, A066195, A110699, A110700.

%K nonn,base,nice

%O 1,1

%A _Alexander D. Healy_, Jun 19 2001

%E Extended to 60 terms by _Max Alekseyev_, Aug 03 2005

%E Further terms from _T. D. Noe_, Mar 14 2008