|
|
A061712
|
|
Smallest prime with Hamming weight n (i.e., with exactly n 1's when written in binary).
|
|
39
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
Conjecture: a(n) < 2^(n+3). - T. D. Noe, Mar 14 2008
|
|
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
(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
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|