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