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

2, 3, 7, 23, 31, 311, 127, 383, 991, 2039, 3583, 6143, 8191, 73727, 63487, 129023, 131071, 522239, 524287, 1966079, 4128767, 16250879, 14680063, 33546239, 67108351, 201064447, 260046847, 536739839, 1073479679, 5335154687, 2147483647, 8581545983, 16911433727, 32212254719

Offset: 1

Author

Alexander D. Healy, Jun 19 2001

Keywords

• nonn
• base
• nice

Comments

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

Drmota, Mauduit, & Rivat prove that a(n) exists for n > N for some N. - Charles R Greathouse IV, May 17 2010

Examples

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

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..3320 (first 1024 terms from T. D. Noe)
• Michael Drmota, Christian Mauduit, and Joel Rivat, Primes with an average sum of digits, Compositio Mathematica 145 (2009), pp. 271-292.
• Kenichiro Kashihara, Letter to the Editor, Math. Scientist 20 (1) (1995), 67-68.
• MathOverflow, Are there primes of every Hamming weight?
• Samuel S. Wagstaff, Prime numbers with a fixed number of one bits or zero bits in their binary representation, Experimental Mathematics 10 (2001), pp. 267-273.

Crossrefs

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

Programs

Haskell

a061712 n = fromJust $ find ((== n) . a000120) a000040_list
-- Reinhard Zumkeller, Feb 10 2013

Maple

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

Mathematica

Do[k = 1; While[ Count[ IntegerDigits[ Prime[k], 2], 1] != n, k++ ]; Print[ Prime[k]], {n, 1, 30} ]
(* Second program: *)
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 *)
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 *)

PARI

a(n)=forprime(p=2, , if (hammingweight(p) == n, return(p));); \\ Michel Marcus, Mar 16 2015

Python

from itertools import combinations
from sympy import isprime
def A061712(n):
    l, k = n-1, 2**n
    while True:
        for d in combinations(range(l-1,-1,-1),l-n+1):
            m = k-1 - sum(2**(e) for e in d)
            if isprime(m):
                return m
        l += 1
        k *= 2 # Chai Wah Wu, Sep 02 2021

Formula

Conjecture: a(n) < 2^(n+3). - T. D. Noe, Mar 14 2008

A000120(a(n)) = A014499(A049084(a(n))) = n. - Reinhard Zumkeller, Feb 10 2013

Extensions

Extended to 60 terms by Max Alekseyev, Aug 03 2005

Further terms from T. D. Noe, Mar 14 2008