A308334 Lexicographically earliest sequence of distinct positive numbers such that for any n > 0, a(n) OR a(n+1) is a prime number (where OR denotes the bitwise OR operator).

1, 2, 3, 4, 5, 6, 7, 16, 13, 8, 11, 9, 10, 21, 12, 17, 14, 19, 15, 18, 23, 20, 25, 22, 27, 28, 29, 24, 31, 26, 33, 36, 37, 32, 41, 34, 43, 35, 40, 39, 42, 45, 38, 47, 44, 49, 52, 53, 48, 59, 50, 57, 51, 56, 61, 60, 67, 62, 65, 63, 64, 71, 58, 69, 66, 77, 54

Offset: 1

Author

Rémy Sigrist, May 20 2019

Keywords

• nonn
• base

Comments

By Dirichlet's theorem on arithmetic progressions, we can always extend the sequence: say a(n) < 2^k, then a(n) OR 1 and 2^k are coprime and there are infinitely many prime numbers of the form (a(n) OR 1) + m*2^k = a(n) OR (1 + m*2^k) and we can extend the sequence.

Will every integer appear in this sequence?

Numerous sequences are based on the same model: the sequence is the lexicographically earliest sequence of distinct positive terms such that some function in two variables yields prime numbers when applied to consecutive terms:

f(u,v) Analog sequence

------- -----------------

u OR v a (this sequence)

u + v A055265

u*v + 1 A073666

u*v - 1 A081943

abs(u-v) A065186

max(u,v) A282649

u^2 + v^2 A100208

The appearance of numbers much earlier or later than their corresponding index is flagged strikingly in the plot2 graph of a(n)/n (see links). - Peter Munn, Sep 10 2022

Examples

			The first terms, alongside a(n) OR a(n+1), are:
  n   a(n)  a(n) OR a(n+1)
  --  ----  --------------
   1     1               3
   2     2               3
   3     3               7
   4     4               5
   5     5               7
   6     6               7
   7     7              23
   8    16              29
   9    13              13
  10     8              11
  11    11              11
  12     9              11
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Peter Munn, Plot2 graph of a(n)/n

Crossrefs

See A308340 for the corresponding prime numbers.

See A055265, A065186, A073666, A081943, A100208, A282649 for similar sequences.

Programs

PARI

s=0; v=1; for (n=1, 67, s+=2^v; print1 (v ", "); for (w=1, oo, if (!bittest(s,w) && isprime(o=bitor(v,w)), v=w; break)))

Python

from sympy import isprime
from itertools import count, islice
def agen():
    aset, k, mink = {1}, 1, 2
    for n in count(1):
        an = k; yield an; aset.add(an)
        s, k = set(str(an)), mink
        while k in aset or not isprime(an|k): k += 1
        while mink in aset: mink += 1
print(list(islice(agen(), 67))) # Michael S. Branicky, Sep 10 2022