A080165 -id:A080165 - cp's OEIS frontend

A095765 Number of primes in range [2^n+1, 2^(n+1)] whose binary expansion begins '10' (A080165).

0, 1, 1, 3, 4, 6, 12, 22, 38, 70, 130, 237, 441, 825, 1539, 2897, 5453, 10335, 19556, 37243, 70938, 135555, 259586, 497790, 956126, 1839597, 3544827, 6839282, 13212389, 25552386, 49472951, 95883938, 186011076, 361177503, 701906519

Offset: 1

Antti Karttunen, Jun 12 2004

nonn

I.e., number of primes p such that 2^n < p < (2^n + 2^(n-1)).
Ratio a(n)/A036378(n) converges as follows: 0, 0.5, 0.5, 0.6, 0.571429, 0.461538, 0.521739, 0.511628, 0.506667, 0.510949, 0.509804, 0.510776, 0.505734, 0.511787, 0.507921, 0.507444, 0.507303, 0.506866, 0.506173, 0.506115, 0.505487, 0.505395, 0.505318, 0.504951, 0.504786, 0.504588, 0.504437, 0.504301, 0.50415, 0.504016, 0.503887, 0.503763, 0.503654
Ratio a(n)/A095766(n) converges as follows: 0, 1, 1, 1.5, 1.333333, 0.857143, 1.090909, 1.047619, 1.027027, 1.044776, 1.04, 1.044053, 1.023202, 1.048285, 1.032193, 1.030228, 1.029645, 1.027847, 1.025001, 1.024764, 1.022191, 1.021815, 1.021501, 1.020003, 1.019331, 1.01852, 1.017908, 1.017353, 1.016737, 1.016195, 1.015669, 1.015164, 1.014723
I think this explains also the bias present in ratios shown at A095297, A095298, etc.

			Table showing the derivation of the initial terms:
  n   2^n+1  2^(n+1)  a(n)   primes starting '10' in binary
  1     3       4      0       -
  2     5       8      1       5 = 101_2
  3     9      16      1      11 = 1011_2
  4    17      32      3      17 = 10001_2, 19 = 10011_2, 23 = 10111_2

Antti Karttunen and J. Moyer: C-program for computing the initial terms of this sequence
Index entries for sequences related to occurrences of various subsets of primes in range ]2^n,2^(n+1)]

Cf. A036378, A080165, A095297, A095298, A095766.

a[n_] := PrimePi[2^n + 2^(n - 1) - 1] - PrimePi[2^n];
Array[a, 35] (* Robert G. Wilson v, Jan 24 2006 *)

a(n) = A036378(n)-A095766(n).

a(34) and a(35) from Robert G. Wilson v, Jan 24 2006

Edited, restoring meaning of name, by Peter Munn, Jun 27 2023

A262365 A(n,k) is the n-th prime whose binary expansion begins with the binary expansion of k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

2, 2, 3, 3, 5, 5, 17, 7, 11, 7, 5, 19, 13, 17, 11, 13, 11, 37, 29, 19, 13, 7, 53, 23, 67, 31, 23, 17, 17, 29, 97, 41, 71, 53, 37, 19, 19, 67, 31, 101, 43, 73, 59, 41, 23, 41, 37, 71, 59, 103, 47, 79, 61, 43, 29, 11, 43, 73, 131, 61, 107, 83, 131, 97, 47, 31

Offset: 1

Alois P. Heinz, Sep 20 2015

			Square array A(n,k) begins:
:  2,  2,  3,  17,  5,  13,   7,  17, ...
:  3,  5,  7,  19, 11,  53,  29,  67, ...
:  5, 11, 13,  37, 23,  97,  31,  71, ...
:  7, 17, 29,  67, 41, 101,  59, 131, ...
: 11, 19, 31,  71, 43, 103,  61, 137, ...
: 13, 23, 53,  73, 47, 107, 113, 139, ...
: 17, 37, 59,  79, 83, 109, 127, 257, ...
: 19, 41, 61, 131, 89, 193, 227, 263, ...

Alois P. Heinz, Antidiagonals n = 1..200, flattened
Index entries for primes involving decimal expansion of n

Columns k=1-7 give: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Row n=1 gives A164022.
Main diagonal gives A262366.
Cf. A262350, A262369.

u:= (h, t)-> select(isprime, [seq(h*2^t+k, k=0..2^t-1)]):
A:= proc(n, k) local l, p;
      l:= proc() [] end; p:= proc() -1 end;
      while nops(l(k))

nmax = 14;
col[k_] := col[k] = Module[{bk = IntegerDigits[k, 2], lk, pp = {}, coe = 1}, lbk = Length[bk]; While[Length[pp] < nmax, pp = Select[Prime[Range[ coe*nmax]], Quiet@Take[IntegerDigits[#, 2], lbk] == bk&]; coe++]; pp];
A[n_, k_] := col[k][[n]];
Table[A[n-k+1, k], {n, 1, nmax}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 25 2021 *)

A080166 Primes having initial digits "11" in binary representation.

Original entry on oeis.org

3, 7, 13, 29, 31, 53, 59, 61, 97, 101, 103, 107, 109, 113, 127, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 769, 773, 787, 797, 809, 811, 821

Offset: 1

Reinhard Zumkeller, Feb 03 2003

Also primes that terminate at 3,2,1 in the x-1 problem: Repeat, if x is even divide by 2 else subtract 1, until 3 is reached. - Cino Hilliard, Mar 27 2003

Or, primes in A004760. - Vladimir Shevelev, May 04 2009

			A000040(16)=53 -> '110101' therefore 53 is a term.

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A004676, A080168.
Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Column k=3 of A262365.

Select[Prime[Range[200]],Take[IntegerDigits[#,2],2]=={1,1}&] (* Harvey P. Dale, Jul 30 2019 *)

pxnm1(n,p) = { forprime(x=2,n, p1 = x; while(p1>1, if(p1%2==0,p1/=2,p1 = p1*p-1;); if(p1 == 3,break); ); if(p1 == 3,print1(x" ")) ) }

A262284 Primes whose binary expansion begins 101.

Original entry on oeis.org

5, 11, 23, 41, 43, 47, 83, 89, 163, 167, 173, 179, 181, 191, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399

Offset: 1

N. J. A. Sloane, Sep 19 2015

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Suggested by A262350.
Column k=5 of A262365.

lis:=[]; q:=5;
for i from 1 to 10 do for j from 1 to 2^i-1 do
if isprime(q*2^i+j) then lis:=[op(lis),q*2^i+j]; fi; od: od:
lis;

Select[Flatten[Table[FromDigits[#,2]&/@(Join[{1,0,1},#]&/@Tuples[{0,1},n]),{n,0,10}]],PrimeQ] (* Harvey P. Dale, Oct 17 2021 *)

A262285 Primes whose binary expansion begins 111.

Original entry on oeis.org

7, 29, 31, 59, 61, 113, 127, 227, 229, 233, 239, 241, 251, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873

Offset: 1

N. J. A. Sloane, Sep 19 2015

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Suggested by A262350.
Column k=7 of A262365.

lis:=[]; q:=7;
for i from 1 to 10 do for j from 1 to 2^i-1 do
if isprime(q*2^i+j) then lis:=[op(lis),q*2^i+j]; fi; od: od:
lis;

Select[FromDigits[#,2]&/@(Join[{1,1,1},#]&/@Flatten[Table[Tuples[{0,1},n],{n,0,8}],1]),PrimeQ] (* or *) Select[Prime[Range[ 3,350]],Take[ IntegerDigits[ #,2],3]=={1,1,1}&] (* Harvey P. Dale, May 02 2021 *)

A262286 Primes whose binary expansion begins 100.

Original entry on oeis.org

17, 19, 37, 67, 71, 73, 79, 131, 137, 139, 149, 151, 157, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093

Offset: 1

N. J. A. Sloane, Sep 19 2015

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Suggested by A262350.
Column k=4 of A262365.

lis:=[]; q:=4;
for i from 1 to 10 do for j from 1 to 2^i-1 do
if isprime(q*2^i+j) then lis:=[op(lis),q*2^i+j]; fi; od: od:
lis;

A262287 Primes whose binary expansion begins 110.

Original entry on oeis.org

13, 53, 97, 101, 103, 107, 109, 193, 197, 199, 211, 223, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627

Offset: 1

N. J. A. Sloane, Sep 19 2015

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Suggested by A262350.
Column k=6 of A262365.

A262350 a(1) = 2. For n>1, let s denote the binary string of a(n-1) with the leftmost 1 and following consecutive 0's removed. Then a(n) is the smallest prime not yet present whose binary representation begins with s.

Original entry on oeis.org

2, 3, 5, 7, 13, 11, 29, 53, 43, 23, 31, 61, 59, 109, 181, 107, 173, 367, 223, 191, 127, 509, 1013, 4013, 3931, 3767, 13757, 11131, 2939, 1783, 3037, 1979, 3821, 3547, 1499, 1901, 877, 2927, 1759, 1471, 1789, 1531, 2029, 2011, 7901, 60887, 56239, 93887, 28351

Offset: 1

Alois P. Heinz, Sep 18 2015

This sequence is infinite. The number of primes that are not in this sequence is conjectured to be infinite.

Proof of first statement, following a comment from David W. Wilson: It follows from standard results about primes in short intervals (see for example Harman, 1982) that there are infinitely many numbers in any base b starting with any nonzero prefix c. So there are infinitely many primes whose binary expansion begins with s, and so a(n) always exists. - N. J. A. Sloane, Sep 19 2015

			: 10                             ... 2
:   11                           ... 3
:    101                         ... 5
:      111                       ... 7
:       1101                     ... 13
:        1011                    ... 11
:          11101                 ... 29
:           110101               ... 53
:            101011              ... 43
:              10111             ... 23
:                11111           ... 31
:                 111101         ... 61
:                  111011        ... 59
:                   1101101      ... 109
:                    10110101    ... 181
:                      1101011   ... 107
:                       10101101 ... 173

Alois P. Heinz, Table of n, a(n) for n = 1..589
G. Harman, Primes in short intervals, Math. Zeit., 180 (1982), 335-348.

Binary analog of A262283.
Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Cf. A262365.

b:= proc() true end:
a:= proc(n) option remember; local h, k, ok, p, t;
      if n=1 then p:=2
    else h:= (k-> irem(k, 2^(ilog2(k))))(a(n-1)); p:= h;
         ok:= isprime(p) and b(p);
         for t while not ok do
           for k to 2^t-1 while not ok do p:= h*2^t+k;
             ok:= isprime(p) and b(p)
           od
         od
      fi; b(p):= false; p
    end:
seq(a(n), n=1..70);

A262283 a(1)=2. For n>1, let s denote the digit-string of a(n-1) with the first digit omitted. Then a(n) is the smallest prime not yet present which starts with s.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 31, 17, 71, 19, 97, 73, 37, 79, 907, 701, 101, 103, 307, 709, 911, 113, 131, 311, 1103, 1031, 313, 137, 373, 733, 331, 317, 173, 739, 397, 971, 719, 191, 919, 193, 937, 379, 797, 977, 773, 7307, 3079, 7901, 9011, 1109, 109, 929, 29, 941, 41

Offset: 1

N. J. A. Sloane, Sep 18 2015

If a(n-1) has a single digit then a(n) is simply the smallest missing prime.
Leading zeros in s are ignored.
The sequence is infinite, since there infinitely many primes that start with s (see the comments in A080165).
The data in the b-file suggests that there are infinitely many primes that do not appear. Hoever, at present that is no proof that even one prime (23, say) never appears. - N. J. A. Sloane, Sep 20 2015
Alois P. Heinz points out that a(n) = A262282(n+29) starting at the 103rd term. - N. J. A. Sloane, Sep 19 2015

			a(1)=2, so s is the empty string, so a(2) is the smallest missing prime, 3. After a(6)=13, s=3, so a(7) is the smallest missing prime that starts with 3, which is 31.

Alois P. Heinz, Table of n, a(n) for n = 1..676

Cf. A080165, A089755, A262282, A262350.

import Data.List (isPrefixOf, delete)
a262283 n = a262283_list !! (n-1)
a262283_list = 2 : f "" (map show $ tail a000040_list) where
   f xs pss = (read ys :: Integer) :
              f (dropWhile (== '0') ys') (delete ys pss)
              where ys@(_:ys') = head $ filter (isPrefixOf xs) pss
-- Reinhard Zumkeller, Sep 19 2015

More terms from Alois P. Heinz, Sep 18 2015

A080167 Primes beginning with '10' and ending with '01' in binary representation.

Original entry on oeis.org

5, 17, 37, 41, 73, 89, 137, 149, 157, 173, 181, 257, 269, 277, 281, 293, 313, 317, 337, 349, 353, 373, 521, 541, 557, 569, 577, 593, 601, 613, 617, 641, 653, 661, 673, 677, 701, 709, 733, 757, 761, 1033, 1049, 1061, 1069, 1093, 1097, 1109, 1117, 1129, 1153

Offset: 1

Reinhard Zumkeller, Feb 04 2003

Intersection of A002144 and A080165.

			A000040(12)=37 -> '100101' therefore 37 is a term.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A004676, A074832, A030101.

Select[Prime[Range[200]],Take[IntegerDigits[#,2],2]=={1,0}&&Take[ IntegerDigits[#,2],-2]=={0,1}&] (* Harvey P. Dale, May 10 2015 *)

cp's OEIS Frontend

A095765 Number of primes in range [2^n+1, 2^(n+1)] whose binary expansion begins '10' (A080165).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A262365 A(n,k) is the n-th prime whose binary expansion begins with the binary expansion of k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A080166 Primes having initial digits "11" in binary representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A262284 Primes whose binary expansion begins 101.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A262285 Primes whose binary expansion begins 111.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A262286 Primes whose binary expansion begins 100.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A262287 Primes whose binary expansion begins 110.

Views

Author

Keywords

Links

Crossrefs

A262350 a(1) = 2. For n>1, let s denote the binary string of a(n-1) with the leftmost 1 and following consecutive 0's removed. Then a(n) is the smallest prime not yet present whose binary representation begins with s.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A262283 a(1)=2. For n>1, let s denote the digit-string of a(n-1) with the first digit omitted. Then a(n) is the smallest prime not yet present which starts with s.

Views

Author

Keywords