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,2

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

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Peter Munn, Plot2 graph of a(n)/n

Example

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

Prog

(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

Crossrefs

See A308340 for the corresponding prime numbers.

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

Sequence in context: A065640 A264974 A334953 * A161673 A368533 A309126

Adjacent sequences: A308331 A308332 A308333 * A308335 A308336 A308337

Keyword

nonn,base

Author

Rémy Sigrist, May 20 2019

Status

approved