Computing Remy Sigrist sequence A279125

Question

I am curious to understand how you can compute sequences like this one by Rémy Sigrist https://oeis.org/A279125

You can also see it in action in this numberphile video: https://youtu.be/j0o-pMIR8uk?t=371

---

What I struggle with is to understand how to compute these 'overlaps' they explain. I don't even know the right term for it... I guess it is connected to lowest order bit, but I don't understand it.

I started writing a function for it, but I need help with computing this bit comparison.

function remyF(n) {
    let num = parseInt(n, 10);
    return num.toString(2);
} 

Answer 1

In python:

def remyF(n):
  if is_power_of_2(n):
    return 0
  friends = []
  for m in range(1,n):
    if m&n!=0: #true iff m and n share a bit
      friends.append(remyF(m))
  for k in range(max(friends)+1):
      if k not in friends:
        return k 
  return max(friends)+1 #return the first integer in 0...n that is not in friends

You should have no issue with is_power_of_2. Thanks to Peter Foreman for informing me of numerous errors. And you should store previously computed values in a lookup table if you're going to use this code for any medium to large n.

Answer 2

The following code returns the first $n+1$ terms (terms $0-n$) of the given sequence. It is equivalent to the code used on the OEIS but in Python.

def remy(n):
    terms=[0]*n
    for i in range(n+1):
        a=0
        while terms[a]&i:
            a+=1
        terms[a]+=i
        yield a

First we create a list full of zeroes. This list is used to store the bits which associate a number to a group (e.g. all numbers whose sequence value is $1$). Each number is iterated through from $0-n$ in order and the program finds which value/group the number is associated to by using a bitwise AND (& in Python). When it has done so (the bitwise AND returns zero/False), this number is added to the same position in the list in order to store the bit pattern of this number. Then, to check if future numbers are within this group, the operation of bitwise AND will cause any number containing these bits to be identified (bitwise AND does not return zero/False in this case). The value of the number in the sequence is then yielded.