cp's OEIS Frontend

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

%I A061712 #75 Jul 23 2025 05:29:50
%S A061712 2,3,7,23,31,311,127,383,991,2039,3583,6143,8191,73727,63487,129023,
%T A061712 131071,522239,524287,1966079,4128767,16250879,14680063,33546239,
%U A061712 67108351,201064447,260046847,536739839,1073479679,5335154687,2147483647,8581545983,16911433727,32212254719
%N A061712 Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary).
%C A061712 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 A061712 Drmota, Mauduit, & Rivat prove that a(n) exists for n > N for some N. - _Charles R Greathouse IV_, May 17 2010
%H A061712 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 A061712 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 A061712 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 A061712 MathOverflow, <a href="http://mathoverflow.net/questions/22629">Are there primes of every Hamming weight?</a>
%H A061712 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 A061712 Conjecture: a(n) < 2^(n+3). - _T. D. Noe_, Mar 14 2008
%F A061712 A000120(a(n)) = A014499(A049084(a(n))) = n. - _Reinhard Zumkeller_, Feb 10 2013
%e A061712 The fourth term is 23 (10111 in binary), since no prime less than 23 has exactly 4 1's in its binary representation.
%p A061712 with(combstruct):
%p A061712 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);
%p A061712 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 A061712 Do[k = 1; While[ Count[ IntegerDigits[ Prime[k], 2], 1] != n, k++ ]; Print[ Prime[k]], {n, 1, 30} ]
%t A061712 (* Second program: *)
%t A061712 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 A061712 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 A061712 (Haskell)
%o A061712 a061712 n = fromJust $ find ((== n) . a000120) a000040_list
%o A061712 -- _Reinhard Zumkeller_, Feb 10 2013
%o A061712 (PARI) a(n)=forprime(p=2, , if (hammingweight(p) == n, return(p));); \\ _Michel Marcus_, Mar 16 2015
%o A061712 (Python)
%o A061712 from itertools import combinations
%o A061712 from sympy import isprime
%o A061712 def A061712(n):
%o A061712     l, k = n-1, 2**n
%o A061712     while True:
%o A061712         for d in combinations(range(l-1,-1,-1),l-n+1):
%o A061712             m = k-1 - sum(2**(e) for e in d)
%o A061712             if isprime(m):
%o A061712                 return m
%o A061712         l += 1
%o A061712         k *= 2 # _Chai Wah Wu_, Sep 02 2021
%Y A061712 Cf. A000043, A000120, A000668, A001348, A014499, A049084, A066195, A110699, A110700.
%K A061712 nonn,base,nice
%O A061712 1,1
%A A061712 _Alexander D. Healy_, Jun 19 2001
%E A061712 Extended to 60 terms by _Max Alekseyev_, Aug 03 2005
%E A061712 Further terms from _T. D. Noe_, Mar 14 2008