A061712 -id:A061712 - cp's OEIS frontend

A081093 a(n) is the smallest prime such that the number of 1's in its binary expansion is equal to the n-th prime.

3, 7, 31, 127, 3583, 8191, 131071, 524287, 14680063, 1073479679, 2147483647, 266287972351, 4260607557631, 17591112302591, 246290604621823, 17996806323437567, 1152917106560335871, 2305843009213693951

Offset: 1

Reinhard Zumkeller, Mar 05 2003

a(n) = Min{p: A000120(p)=A000040(n), p prime}.
If 2^(Prime[n]) - 1 is a prime number, then a(n) = 2^(Prime[n]) - 1, where Prime[n] denotes the n-th prime number. This means that every Mersenne prime arises in this sequence. - Stefan Steinerberger, Jan 22 2006
For all n with prime(n) < 300, a(n) has either prime(n) or prime(n)+1 bits. - David Wasserman, Oct 25 2006

			n=4, p[4]=11, 3583=[11011111111] has 11 digits=1 and is prime;
2047=23.89=[11111111111] is not here because it is composite.
a(5)=3583=A081092(266)=A000040(502) having eleven 1's: '110111111111' and A000120(p)<11=prime(5) for primes p<3583.
Mersenne-primes are here, Mersenne composites not.

Cf. A000043, A000668, A001348, A061712, A000120, A014499.

Cf. A000040, A000120, A081092.

Do[k=1;While[Count[IntegerDigits[Prime[k], 2], 1] !=Prime[n], k++ ];Print[Prime[k]], {n, 1, 10}]

a(n) = A061712(A000040(n)). - Franklin T. Adams-Watters, Jun 06 2006

More terms from Franklin T. Adams-Watters, Jun 06 2006
Further terms from David Wasserman, Oct 25 2006
Edited by N. J. A. Sloane, Sep 15 2008 at the suggestion of R. J. Mathar

A091991 Minimal number of 1's that must be inserted into the binary representation of n to get a prime.

Original entry on oeis.org

1, 0, 0, 2, 0, 1, 0, 1, 1, 2, 0, 2, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 2, 1, 1, 1, 4, 0, 1, 0, 2, 1, 2, 1, 1, 0, 2, 1, 2, 0, 2, 0, 1, 1, 3, 0, 1, 1, 1, 1, 2, 0, 1, 2, 1, 3, 3, 0, 3, 0, 2, 1, 3, 1, 2, 0, 1, 1, 2, 0, 2, 0, 1, 1, 2, 1, 1, 0, 2, 1, 2, 0, 3, 1, 1, 2, 2, 0, 1, 2, 2, 2, 2, 1, 1, 0, 1, 1, 2, 0, 2

Offset: 1

Reinhard Zumkeller, Mar 17 2004

nonn

Insertion here means that the new 1-bit must come somewhere right of the most significant 1-bit. - Antti Karttunen, Dec 15 2017

			n = 25->'11001': A000040(16)=53->'110[1]01', therefore a(25)=1;
a(255)=a(2^8-1)=5, as 2^(8+5)-1=8191 is a Mersenne prime and 2^(8+i)-1 is not prime for i<5.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to binary expansion of n

Cf. A000668, A014499, A108234.

insert1bit(n,pos) = (((n>>pos)<<(1+pos))+(1<>=1;k++); k; };
A091991(n) = { if(1==n,return(1)); if(isprime(n),return(0)); if(!(n%2),return(1+A091991(1+n+n))); my(k,nexttries,prevtries = Set([n]), w = binwidth(n)-1); for(b=1,oo,nexttries = Set([]); for(t=1,length(prevtries), h = prevtries[t]; for(i=1,w,if(isprime(k=insert1bit(h,i)),return(b),nexttries = setunion(Set([k]),nexttries)))); prevtries = nexttries; w++);};
\\ Antti Karttunen, Dec 15 2017

a(2*n) = a(4*n+1) + 1.
a(A005097(n)) = 1 - A010051(A005097(n)).
a(2^k)=A061712(k); a(2^k+1)=A061712(k-1)*(1-A010051(2^k+1));
a(2^k-1) = A000043(m+1) - k for A000043(m)A000043(m+1).

A102029 Smallest semiprime with Hamming weight n (i.e., smallest semiprime with exactly n ones when written in binary), or -1 if no such number exists.

Original entry on oeis.org

4, 6, 14, 15, 55, 95, 247, 447, 511, 1535, 2047, 7167, 12287, 32255, 49151, 98303, 196607, 393215, 983039, 1572863, 3145727, 6291455, 8388607, 33423359, 50331647, 117440511, 201326591, 528482303, 805306367, 1879048191, 3221225471

Offset: 1

Jonathan Vos Post, Jun 23 2007

Semiprime analog of A061712. Extended by Stefan Steinerberger. Includes the subset Mersenne semiprimes A092561.

			a(1) = 4 because the first semiprime A001358(1) is 4 (base 10) which is written 100 in binary, the latter representation having exactly 1 one.
a(2) = 6 since A001358(2) = 6 = 110 (base 2) has exactly 2 ones.
a(4) = 15 since A001358(6) = 15 = 1111 (base 2) has exactly 4 ones and, as it also has no zeros, is the smallest of the Mersenne semiprimes.

Donovan Johnson, Table of n, a(n) for n = 1..250

Cf. A000043, A000120, A000337, A000668, A001358, A007088, A061712, A085724, A089226, A089998, A089999, A091991, A092558, A092559, A092561, A092562, A081093, A102782, A110472, A110699, A110700.

Join[{4},Table[SelectFirst[Sort[FromDigits[#,2]&/@Permutations[ Join[ PadRight[{}, n,1],{0}]]],PrimeOmega[#]==2&],{n,2,40}]] (* Harvey P. Dale, Feb 06 2015 *)

A372538 Numbers k such that the number of ones minus the number of zeros in the binary expansion of the k-th prime number is 1.

Original entry on oeis.org

3, 8, 20, 23, 24, 26, 30, 58, 61, 63, 65, 67, 78, 80, 81, 82, 84, 88, 185, 187, 194, 200, 201, 203, 213, 214, 215, 221, 225, 226, 227, 234, 237, 246, 249, 253, 255, 256, 257, 259, 266, 270, 280, 284, 287, 290, 573, 578, 586, 588, 591, 593, 611, 614, 615, 626

Offset: 1

Gus Wiseman, May 13 2024

			The binary expansion of 83 is (1,0,1,0,0,1,1) with ones minus zeros 4 - 3 = 1, and 83 is the 23rd prime, so 23 is in the sequence.
The primes A000040(a(n)) together with their binary expansions and binary indices begin:
     5:           101 ~ {1,3}
    19:         10011 ~ {1,2,5}
    71:       1000111 ~ {1,2,3,7}
    83:       1010011 ~ {1,2,5,7}
    89:       1011001 ~ {1,4,5,7}
   101:       1100101 ~ {1,3,6,7}
   113:       1110001 ~ {1,5,6,7}
   271:     100001111 ~ {1,2,3,4,9}
   283:     100011011 ~ {1,2,4,5,9}
   307:     100110011 ~ {1,2,5,6,9}
   313:     100111001 ~ {1,4,5,6,9}
   331:     101001011 ~ {1,2,4,7,9}
   397:     110001101 ~ {1,3,4,8,9}
   409:     110011001 ~ {1,4,5,8,9}
   419:     110100011 ~ {1,2,6,8,9}
   421:     110100101 ~ {1,3,6,8,9}
   433:     110110001 ~ {1,5,6,8,9}
   457:     111001001 ~ {1,4,7,8,9}
  1103:   10001001111 ~ {1,2,3,4,7,11}
  1117:   10001011101 ~ {1,3,4,5,7,11}
  1181:   10010011101 ~ {1,3,4,5,8,11}
  1223:   10011000111 ~ {1,2,3,7,8,11}

Restriction of A031448 to the primes, positions of ones in A145037.
Taking primes gives A095073, negative A095072.
Positions of ones in A372516, absolute value A177718.
Cf. A066196, A095070-A095075, A177796, A372539.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A030190 gives binary expansion, reversed A030308.
A035103 counts zeros in binary expansion of primes, firsts A372474.
A048793 lists binary indices, reverse A272020, sum A029931.
A070939 gives the length of an integer's binary expansion.
A101211 lists run-lengths in binary expansion, row-lengths A069010.
A372471 lists binary indices of primes.
Cf. A000040, A003714, A035100, A037861, A053738, A061712, A066195, A104080, A211997, A372429, A372517, A372686.

Select[Range[1000],DigitCount[Prime[#],2,1]-DigitCount[Prime[#],2,0]==1&]

A372539 Numbers k such that the number of ones minus the number of zeros in the binary expansion of the k-th prime number is -1.

Original entry on oeis.org

7, 19, 21, 25, 56, 57, 59, 60, 62, 68, 71, 77, 79, 87, 175, 177, 179, 180, 186, 188, 189, 192, 193, 195, 196, 197, 204, 210, 212, 216, 218, 243, 244, 248, 254, 262, 263, 265, 279, 567, 572, 576, 577, 583, 592, 598, 599, 600, 602, 603, 605, 606, 610, 613, 616

Offset: 1

Gus Wiseman, May 14 2024

			The binary expansion of 17 is (1,0,0,0,1) with ones minus zeros 2 - 3 = -1, and 17 is the 7th prime, 7 is in the sequence.
The primes A000040(a(n)) together with their binary expansions and binary indices begin:
    17:         10001 ~ {1,5}
    67:       1000011 ~ {1,2,7}
    73:       1001001 ~ {1,4,7}
    97:       1100001 ~ {1,6,7}
   263:     100000111 ~ {1,2,3,9}
   269:     100001101 ~ {1,3,4,9}
   277:     100010101 ~ {1,3,5,9}
   281:     100011001 ~ {1,4,5,9}
   293:     100100101 ~ {1,3,6,9}
   337:     101010001 ~ {1,5,7,9}
   353:     101100001 ~ {1,6,7,9}
   389:     110000101 ~ {1,3,8,9}
   401:     110010001 ~ {1,5,8,9}
   449:     111000001 ~ {1,7,8,9}
  1039:   10000001111 ~ {1,2,3,4,11}
  1051:   10000011011 ~ {1,2,4,5,11}
  1063:   10000100111 ~ {1,2,3,6,11}
  1069:   10000101101 ~ {1,3,4,6,11}
  1109:   10001010101 ~ {1,3,5,7,11}
  1123:   10001100011 ~ {1,2,6,7,11}
  1129:   10001101001 ~ {1,4,6,7,11}
  1163:   10010001011 ~ {1,2,4,8,11}

Restriction of A031444 (positions of '-1's in A145037) to A000040.
Taking primes gives A095072.
Positions of negative ones in A372516, absolute value A177718.
The negative version is A372538, taking primes A095073.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A030190 gives binary expansion, reversed A030308.
A035103 counts zeros in binary expansion of primes, firsts A372474.
A048793 lists binary indices, reverse A272020, sum A029931.
A070939 gives the length of an integer's binary expansion.
A101211 lists run-lengths in binary expansion, row-lengths A069010.
A372471 lists binary indices of primes.
Cf. A003714, A031448, A035100, A037861, A053738, A061712, A066195, A104080, A211997, A372429, A372517, A372686.

Select[Range[1000],DigitCount[Prime[#],2,1]-DigitCount[Prime[#],2,0]==-1&]

A372685 Prime numbers such that no lesser prime has the same binary weight (number of ones in binary expansion).

Original entry on oeis.org

2, 3, 7, 23, 31, 127, 311, 383, 991, 2039, 3583, 6143, 8191, 63487, 73727, 129023, 131071, 522239, 524287, 1966079, 4128767, 14680063, 16250879, 33546239, 67108351, 201064447, 260046847, 536739839, 1073479679, 2147483647, 5335154687, 8581545983, 16911433727

Offset: 1

Gus Wiseman, May 10 2024

The unsorted version is A061712.

			The terms together with their binary expansions and binary indices begin:
     2:            10 ~ {2}
     3:            11 ~ {1,2}
     7:           111 ~ {1,2,3}
    23:         10111 ~ {1,2,3,5}
    31:         11111 ~ {1,2,3,4,5}
   127:       1111111 ~ {1,2,3,4,5,6,7}
   311:     100110111 ~ {1,2,3,5,6,9}
   383:     101111111 ~ {1,2,3,4,5,6,7,9}
   991:    1111011111 ~ {1,2,3,4,5,7,8,9,10}
  2039:   11111110111 ~ {1,2,3,5,6,7,8,9,10,11}
  3583:  110111111111 ~ {1,2,3,4,5,6,7,8,9,11,12}
  6143: 1011111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,13}

Michael S. Branicky, Table of n, a(n) for n = 1..3320 (terms 36..3320 using A061712)

This statistic (binary weight of primes) is A014499.
Sorted version of A061712.
For binary length instead of weight we have A104080, firsts of A035100.
These primes have indices A372686, sorted version of A372517.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A029837 gives greatest binary index, least A001511.
A030190 gives binary expansion, reversed A030308.
A035103 counts zeros in binary expansion of primes, firsts A372474.
A048793 lists binary indices, reverse A272020, sum A029931.
A372471 lists binary indices of primes.
Cf. A000040, A005940, A066195, A069010, A070939, A071814, A211997, A372429, A372516, A372684.

First/@GatherBy[Select[Range[1000],PrimeQ],DigitCount[#,2,1]&]

from itertools import islice
from sympy import nextprime
def A372685_gen(): # generator of terms
    p, a = 1, {}
    while (p:=nextprime(p)):
        if (c:=p.bit_count()) not in a:
            yield p
        a[c] = p
A372685_list = list(islice(A372685_gen(),20)) # Chai Wah Wu, May 12 2024

a(n) = prime(A372686(n)).

a(22)-a(33) from Chai Wah Wu, May 12 2024

A115156 Smallest number having exactly n ones in binary representation and also exactly n prime factors (counted with multiplicity).

Original entry on oeis.org

2, 6, 28, 54, 405, 486, 2808, 4860, 21870, 40824, 192456, 524160, 708588, 4059072, 14348907, 58576608, 123731712, 462944160, 1837080000, 3874204890, 11809800000, 48183984000, 65086642152, 339033848832, 1360965131136, 2928898896840, 6595446404736

Offset: 1

Reinhard Zumkeller, Jan 14 2006

nonn

A001222(a(n)) = A000120(a(n)) = n; subsequence of A071814.
a(n) is roughly 3^n and so far 4 <= a(n)/3^(n-2) <= 15. - Robert G. Wilson v
Does a(n) exist for every n?  It exists for large enough n due to a result of Drmota, Mauduit, & Rivat, see A061712. T. D. Noe's conjecture there implies that a(n) < 4*4^n. - Charles R Greathouse IV, Jul 30 2011

			a(5) = 3*3*3*3*5 = 405_10 = 110010101_2.
a(10) = 2*2*2*3*3*3*3*3*3*7 = 40824_10 = 1001111101111000_2.
a(18) = 2*2*2*2*2*3*3*3*3*3*3*3*3*3*3*5*7*7 = 462944160_10 = 11011100101111111011110100000_2. - _Robert G. Wilson v_

Lk[n_] := Block[{k = 2^n - 1}, While[n != Plus @@ IntegerDigits[k, 2] || n != Plus @@ (Transpose[FactorInteger@k][[2]]), k++ ]; k]; L = {}; Do[v = Lk[n]; Print[{n, v}]; AppendTo[L, v], {n, 2, 16}]; L (Resta)
t = Table[0, {20}]; f[n_] := Block[{b = Count[ IntegerDigits[n, 2], 1], e = Plus @@ Last /@ FactorInteger@n}, If[b == e, b, 0]]; Do[ a = f@n; If[a > 0 && t[[a]] == 0, t[[a]] = n; Print[{a, n}]], {n, 550000000}]; t (* Robert G. Wilson v *)
f[n_] := Min[ Select[ FromDigits[ #, 2] & /@ Permutations[ Join[ Table[0, {Max[6, 2n/3]}], Table[1, {n}]]], Plus @@ Last /@ FactorInteger@# == n &]]; Array[f, 18] (* Robert G. Wilson v *)

a(14)-a(17) from Giovanni Resta, Jan 18 2006
a(14)-a(18) from Robert G. Wilson v, Jan 18 2006
a(19) from Robert G. Wilson v, Jan 22 2006
a(20)-a(24) from Donovan Johnson, Apr 07 2008
a(25)-a(27) from Donovan Johnson, Jul 30 2011

A177835 Primes p for which a smaller prime q exists with A000120(q) >= 2*A000120(p)-1.

Original entry on oeis.org

17, 37, 41, 67, 73, 97, 131, 137, 139, 149, 163, 193, 197, 257, 263, 269, 277, 281, 293, 337, 353, 389, 401, 449, 521, 523, 547, 577, 593, 641, 643, 673, 769, 773, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1091, 1093, 1097, 1109, 1123, 1129, 1153, 1163, 1171

Offset: 1

Vladimir Shevelev, May 14 2010

See A177836 for a comparison with A095075.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000120, A014499, A095075, A061712, A177768, A177836.

read("transforms") ;A000120 := proc(n) wt(n) ; end proc:
isA177835 := proc(p) if isprime(p) then q := 2 ; while q < p do if A000120(q) >= 2*A000120(p)-1 then return true; end if; q := nextprime(q) ; end do: return false; else false; end if; end proc:
for i from 1 to 2000 do if isA177835(ithprime(i)) then printf("%d,",ithprime(i)) ; end if; end do: # R. J. Mathar, May 31 2010

With[{b = DigitCount[Prime[Range[200]], 2, 1]}, Rest@ Prime[Position[2*b - 1 - FoldList[Max, b], ?(# <= 0 &)] // Flatten]] (* _Amiram Eldar, Jul 25 2023 *)

keyword:base and more terms added by R. J. Mathar, May 31 2010

A177836 Terms of A095075 which are not in A177835.

Original entry on oeis.org

2, 541, 557, 563, 569, 587, 601, 613, 617, 647, 653, 659, 661, 677, 709, 787, 809, 929, 2141, 2203, 2221, 2251, 2281, 2333, 2347, 2357, 2381, 2389, 2393, 2417, 2467, 2473, 2617, 2659, 2699, 2707, 2713, 2729, 2837, 2851, 2857, 2897, 2953, 3221, 3347, 3461

Offset: 1

Vladimir Shevelev, May 14 2010

Note that the consecutive terms A095075(2)=17 up to A095075(27)=523 are all in A177835.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A095075, A177835, A000120, A014499, A061712, A177768.

With[{b = DigitCount[Prime[Range[600]], 2, 1]}, Join[{2}, Select[Prime[Position[ 2*b - 1 - FoldList[Max, b], ?(# > 0 &)] // Flatten], Differences[DigitCount[#, 2]][[1]] >= 0 &]]] (* _Amiram Eldar, Jul 27 2023 *)

A095075 \ A177835.

Keyword:base and more terms from R. J. Mathar, May 31 2010

A236513 The n-th prime with n 1-bits in its binary expansion.

Original entry on oeis.org

2, 5, 13, 53, 79, 373, 379, 983, 1783, 6007, 7151, 21503, 31231, 98207, 129919, 259967, 507839, 1564159, 1830911, 4193263, 8355583, 25157567, 33288191, 92274671, 134180863, 394264447, 536838139, 1072693243, 2145382399, 6442188791, 8522825599, 17179836413

Offset: 1

Irina Gerasimova, Jan 27 2014

			Primes p such that
A000120(p) = 1: 2;
A000120(p) = 2: 3, 5, 17, 257,...
A000120(p) = 3: 7, 11, 13, 19, 37, 41,...
A000120(p) = 4: 23, 29, 43, 53, 71, 83, 89,...
A000120(p) = 5: 31, 47, 59, 61, 79, 103, 107, 109,...
A000120(p) = 6: 311, 317, 347, 349, 359, 373,...

Chai Wah Wu, Table of n, a(n) for n = 1..1014

Cf. A061712 (least prime having n ones in binary).

nn = 20; t = Table[-n + 1, {n, nn}]; p = 1; While[Min[t] <= 0, p = NextPrime[p]; b = Total[IntegerDigits[p, 2]]; If[b <= nn, If[t[[b]] < 0, t[[b]]++, If[t[[b]] == 0, t[[b]] = p]]]]; t (* T. D. Noe, Jan 27 2014 *)

lista(nn) = {prm = primes(5000000); for (n = 1, nn, ltp = select(p->hammingweight(p)== n, prm); print1(ltp[n], ", "););} \\ Michel Marcus, Jan 27 2014

from itertools import combinations
from sympy import isprime
def A236513(n):
    l, k, c = n-1, 2**n, 0
    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):
                c += 1
                if c == n:
                    return m
        l += 1
        k *= 2 # Chai Wah Wu, Sep 02 2021

a(24)-a(32) from Giovanni Resta, Feb 04 2014

cp's OEIS Frontend

A081093 a(n) is the smallest prime such that the number of 1's in its binary expansion is equal to the n-th prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A091991 Minimal number of 1's that must be inserted into the binary representation of n to get a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A102029 Smallest semiprime with Hamming weight n (i.e., smallest semiprime with exactly n ones when written in binary), or -1 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A372538 Numbers k such that the number of ones minus the number of zeros in the binary expansion of the k-th prime number is 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A372539 Numbers k such that the number of ones minus the number of zeros in the binary expansion of the k-th prime number is -1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A372685 Prime numbers such that no lesser prime has the same binary weight (number of ones in binary expansion).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A115156 Smallest number having exactly n ones in binary representation and also exactly n prime factors (counted with multiplicity).

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Extensions

A177835 Primes p for which a smaller prime q exists with A000120(q) >= 2*A000120(p)-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple