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

Offset

1,1

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

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.

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

Example

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

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

Prog

(Haskell)
a061712 n = fromJust $ find ((== n) . a000120) a000040_list
-- Reinhard Zumkeller, Feb 10 2013
(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

Crossrefs

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

Sequence in context: A127581 A278477 A118883 * A059661 A214704 A231075

Adjacent sequences: A061709 A061710 A061711 * A061713 A061714 A061715

Keyword

nonn,base,nice

Author

Alexander D. Healy, Jun 19 2001

Extensions

Extended to 60 terms by Max Alekseyev, Aug 03 2005

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

Status

approved