login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061712 Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary). 23

%I

%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

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

%H T. D. Noe and 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 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

%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

%Y Cf. A000043, A000668, A001348, A066195, A110699, A110700.

%K nonn,base,nice,changed

%O 1,1

%A _Alex 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 04:42 EDT 2019. Contains 322294 sequences. (Running on oeis4.)