A353708 -id:A353708 - cp's OEIS frontend

A121216 a(1)=1, a(2) = 2; thereafter a(n) = the smallest positive integer which does not occur earlier in the sequence and which is coprime to a(n-2).

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

Offset: 1

Leroy Quet, Aug 20 2006

nonn

Permutation of the positive natural numbers with inverse A225047: a(A225047(n)) = A225047(a(n)) = n. - Reinhard Zumkeller, Apr 25 2013

I confirm that this is a permutation. - N. J. A. Sloane, Mar 28 2015 [This can be proved using an argument similar to (but simpler than) the proof in A093714. - N. J. A. Sloane, May 05 2022]

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers

Cf. A084937, A121217, A225047, A098550, A256219 (positions of primes), A256399.

import Data.List (delete, (\\))
a121216 n = a121216_list !! (n-1)
a121216_list = 1 : 2 : f 1 2 [3..] where
f x y zs = g zs where
  g (u:us) = if gcd x u == 1 then h $ delete u zs else g us where
   h (v:vs) = if gcd y v == 1 then u : v : f u v (zs \\ [u,v]) else h vs
-- Reinhard Zumkeller, Apr 25 2013

Nest[Append[#, Block[{k = 3}, While[Nand[FreeQ[#, k], GCD[#[[-2]], k] == 1], k++]; k]] &, {1, 2}, 70] (* Michael De Vlieger, Dec 26 2019 *)

Extended by Ray Chandler, Aug 22 2006

A353709 a(0)=0, a(1)=1; thereafter a(n) = smallest nonnegative integer not among the earlier terms of the sequence such that a(n) and a(n-2) have no common 1-bits in their binary representations and also a(n) and a(n-1) have no common 1-bits in their binary representations.

Original entry on oeis.org

0, 1, 2, 4, 8, 3, 16, 12, 32, 17, 6, 40, 64, 5, 10, 48, 65, 14, 128, 33, 18, 68, 9, 34, 20, 72, 35, 132, 24, 66, 36, 25, 130, 96, 13, 144, 98, 256, 21, 42, 192, 257, 22, 104, 129, 258, 28, 97, 384, 26, 37, 320, 136, 7, 80, 160, 11, 84, 288, 131, 76, 272, 161, 70, 264, 49, 134, 328, 512, 19, 44, 448, 513, 30, 224, 768, 15, 112, 640, 259, 52, 200, 514, 53

Offset: 0

N. J. A. Sloane, May 06 2022

A set-theory analog of A084937.

Conjecture: This is a permutation of the nonnegative numbers.

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Walter Trump, Table of n, a(n) for n = 0..10^6
Walter Trump, Log-log plot of first 2^24 terms

Cf. A084937 (number theory analog), A109812, A121216, A353405 (powers of 2), A353708, A353710, A353715 and A353716 (a(n)+a(n+1)), A353717 (inverse), A353718, A353719 (primes), A353720 and A353721 (Records).

For the numbers that are the slowest to appear see A353723 and A353722.

read(transforms) : # ANDnos def'd here
A353709 := proc(n)
option remember;
local c, i, known ;
if n <= 2 then
n;
else
for c from 1 do
known := false ;
for i from 1 to n-1 do
if procname(i) = c then
known := true;
break ;
end if;
end do:
if not known and ANDnos(c, procname(n-2)) = 0 and ANDnos(c, procname(n-1)) = 0 then
return c;
end if;
end do:
end if;
end proc: # Following R. J. Mathar's program for A109812.
[seq(A353709(n), n=0..256)] ;
# second Maple program:
b:= proc() false end: t:= 2:
a:= proc(n) option remember; global t; local k; if n<2 then n
      else for k from t while b(k) or Bits[And](k, a(n-2))>0
      or Bits[And](k, a(n-1))>0 do od; b(k):=true;
      while b(t) do t:=t+1 od; k fi
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, May 06 2022

nn = 83; c[] = -1; a[0] = c[0] = 0; a[1] = c[1] = 1; u = 2; Do[k = u; While[Nand[c[k] == -1, BitAnd[a[n - 1], k] == 0, BitAnd[a[n - 2], k] == 0], k++]; Set[{a[n], c[k]}, {k, n}]; If[k == u, While[c[u] > -1, u++]], {n, 2, nn}]; Array[a, nn+1, 0] (* _Michael De Vlieger, May 06 2022 *)

from itertools import count, islice
def A353709_gen(): # generator of terms
    s, a, b, c, ab = {0,1}, 0, 1, 2, 1
    yield from (0,1)
    while True:
        for n in count(c):
            if not (n & ab or n in s):
                yield n
                a, b = b, n
                ab = a|b
                s.add(n)
                while c in s:
                    c += 1
                break
A353709_list = list(islice(A353709_gen(),20)) # Chai Wah Wu, May 07 2022

A354169 a(0) = 0, a(1) = 1, a(2) = 2; for k >= 2, given a(k), the sequence is extended by adjoining two terms: a(2k-1) = smallest m >= 0 not among a(0) .. a(k) such that {m, a(k), a(k+1), ..., a(2k-2)} are pairwise disjoint in binary, and a(2k) = smallest m >= 0 not among a(0) .. a(k) such that {m, a(k), ..., a(2k-1)} are pairwise disjoint in binary.

Original entry on oeis.org

0, 1, 2, 4, 8, 3, 16, 32, 64, 12, 128, 256, 512, 17, 1024, 34, 2048, 4096, 8192, 68, 16384, 136, 32768, 65536, 131072, 768, 262144, 524288, 1048576, 1025, 2097152, 18, 4194304, 2080, 8388608, 16777216, 33554432, 12288, 67108864, 134217728, 268435456, 16388

Offset: 0

N. J. A. Sloane, Jun 05 2022

The paper by De Vlieger et al. (2022) calls this the "binary two-up sequence".
"Pairwise disjoint in binary" means no common 1-bits in their binary representations.
This is a set-theory analog of A090252. It bears the same relation to A090252 as A252867 does to A098550, A353708 to A121216, A353712 to A347113, etc.
A consequence of the definition, and also an equivalent definition, is that this is the lexicographically earliest infinite sequence of distinct nonnegative numbers with the property that the binary representation of a(n) is disjoint from (has no common 1's with) the binary representations of the following n terms.
An equivalent definition is that a(n) is the smallest nonnegative number that is disjoint (in its binary representation) from each of the previous floor(n/2) terms.
For the subsequence 0, 3, 12, 17, 34, ... of the terms that are not powers of 2 see A354680 and A354798.
All terms are the sum of at most two powers of 2 (see De Vlieger et al., 2022). - N. J. A. Sloane, Aug 29 2022

			After a(2) = 2 = 10_2, a(3) must equal ?0?_2, and the smallest such number we have not seen is a(3) = 100_2 = 4, and a(4) must equal ?00?_2, and the smallest such number we have not seen is a(4) = 1000_2 = 8.

Rémy Sigrist, Table of n, a(n) for n = 0..4941
Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary Two-Up Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022.
Rémy Sigrist, PARI program
N. J. A. Sloane, Construction of terms a(0) through a(18)
N. J. A. Sloane, Table showing first 190 terms (pdf file of scan of large table)
N. J. A. Sloane, Left-hand portion of rows 97-135 of preceding table, showing columns 67-96, rotated counter-clockwise by 90 degrees. The red line in this table should be aligned with the red line between rows 135 and 136 in the preceding table. [This portion of the table was too wide to fit through the scanner.]
N. J. A. Sloane, Blog post about the Two-Up sequence, June 13 2022. Mentions this sequence.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 16.

A355889 is a more efficient way to present this sequence.
Cf. A000120, A090252, A098550, A121216, A252867, A347113, A353708, A353712, A354680, A354767, A354798, A355150.
See also A354773, A354774, A354775, A354780, A354781, A354783.

nn = 42; c[] = r = 0; m = 1; Array[Set[{a[#], c[#]}, {#, #}] &, 2, 0]; Do[k = SelectFirst[Union@ Map[Total, Rest@ Subsets[2^Reverse[Length[#] - Position[#, 1][[All, 1]]] &@ IntegerDigits[2^(r + 2) - m - 1, 2]]], c[#] == 0 &]; Set[{a[n], c[k]}, {k, n}]; m += a[n]; If[And[IntegerQ[#], # > 0], m -= a[#]] &[n/2]; If[And[EvenQ[k], PrimePowerQ[k], k > 2^r], r++], {n, 2, nn}]; Table[a[n], {n, 0, nn}] (* _Michael De Vlieger, Jul 13 2022 *)

PARI
```
See Links section.
```

from itertools import count, islice
from collections import deque
from functools import reduce
from operator import or_
def A354169_gen(): # generator of terms
    aset, aqueue, b, f = {0,1,2}, deque([2]), 2, False
    yield from (0,1,2)
    while True:
        for k in count(1):
            m, j, j2, r, s = 0, 0, 1, b, k
            while r > 0:
                r, q = divmod(r,2)
                if not q:
                    s, y = divmod(s,2)
                    m += y*j2
                j += 1
                j2 *= 2
            if s > 0:
                m += s*2**b.bit_length()
            if m not in aset:
                yield m
                aset.add(m)
                aqueue.append(m)
                if f: aqueue.popleft()
                b = reduce(or_,aqueue)
                f = not f
                break
A354169_list = list(islice(A354169_gen(),40)) # Chai Wah Wu, Jun 06 2022

More terms from Rémy Sigrist, Jun 06 2022

cp's OEIS Frontend

A121216 a(1)=1, a(2) = 2; thereafter a(n) = the smallest positive integer which does not occur earlier in the sequence and which is coprime to a(n-2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A353709 a(0)=0, a(1)=1; thereafter a(n) = smallest nonnegative integer not among the earlier terms of the sequence such that a(n) and a(n-2) have no common 1-bits in their binary representations and also a(n) and a(n-1) have no common 1-bits in their binary representations.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions