login
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).
4

%I #21 Sep 10 2022 08:38:46

%S 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,

%T 29,24,31,26,33,36,37,32,41,34,43,35,40,39,42,45,38,47,44,49,52,53,48,

%U 59,50,57,51,56,61,60,67,62,65,63,64,71,58,69,66,77,54

%N 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).

%C 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.

%C Will every integer appear in this sequence?

%C 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:

%C f(u,v) Analog sequence

%C ------- -----------------

%C u OR v a (this sequence)

%C u + v A055265

%C u*v + 1 A073666

%C u*v - 1 A081943

%C abs(u-v) A065186

%C max(u,v) A282649

%C u^2 + v^2 A100208

%C 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

%H Rémy Sigrist, <a href="/A308334/b308334.txt">Table of n, a(n) for n = 1..10000</a>

%H Peter Munn, <a href="https://oeis.org/plot2a?name1=A308334&amp;name2=A000027&amp;tform1=untransformed&amp;tform2=untransformed&amp;shift=0&amp;radiop1=ratio&amp;drawlines=true">Plot2 graph of a(n)/n</a>

%e The first terms, alongside a(n) OR a(n+1), are:

%e n a(n) a(n) OR a(n+1)

%e -- ---- --------------

%e 1 1 3

%e 2 2 3

%e 3 3 7

%e 4 4 5

%e 5 5 7

%e 6 6 7

%e 7 7 23

%e 8 16 29

%e 9 13 13

%e 10 8 11

%e 11 11 11

%e 12 9 11

%o (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)))

%o (Python)

%o from sympy import isprime

%o from itertools import count, islice

%o def agen():

%o aset, k, mink = {1}, 1, 2

%o for n in count(1):

%o an = k; yield an; aset.add(an)

%o s, k = set(str(an)), mink

%o while k in aset or not isprime(an|k): k += 1

%o while mink in aset: mink += 1

%o print(list(islice(agen(), 67))) # _Michael S. Branicky_, Sep 10 2022

%Y See A308340 for the corresponding prime numbers.

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

%K nonn,base

%O 1,2

%A _Rémy Sigrist_, May 20 2019