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.

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

Author

Alois P. Heinz, Sep 18 2015

Keywords

• nonn
• base

Comments

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

Examples

			: 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
		

Links

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

Crossrefs

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.

Programs

Maple

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);