Computación de la secuencia de Remy Sigrist A279125

Question

Estoy curioso por entender cómo puedes calcular secuencias como esta de Rémy Sigrist https://oeis.org/A279125

También puedes verlo en acción en este video de numberphile: https://youtu.be/j0o-pMIR8uk?t=371

---

Lo que me resulta difícil de entender es cómo calcular estos 'solapamientos' que explican. Ni siquiera sé el término correcto para ello... Supongo que está relacionado con el bit de orden más bajo, pero no lo entiendo.

Comencé a escribir una función para ello, pero necesito ayuda para calcular esta comparación de bits.

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

Answer 1

El siguiente código devuelve los primeros $n+1$ términos (términos $0-n$) de la secuencia dada. Es equivalente al código utilizado en el OEIS pero en 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

Primero creamos una lista llena de ceros. Esta lista se utiliza para almacenar los bits que asocian un número a un grupo (por ejemplo, todos los números cuyo valor de secuencia es $1$). Cada número se itera desde $0-n$ en orden y el programa encuentra a qué valor/grupo está asociado el número utilizando una operación de AND a nivel de bits (& en Python). Cuando lo ha hecho (la operación de AND a nivel de bits devuelve cero/Falso), ese número se agrega a la misma posición en la lista para almacenar el patrón de bits de ese número. Luego, para verificar si los números futuros están dentro de este grupo, la operación de AND a nivel de bits permitirá identificar cualquier número que contenga estos bits (la operación de AND a nivel de bits no devuelve cero/Falso en este caso). Luego se hace un yield del valor del número en la secuencia.

Answer 2

En 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

No deberías tener problemas con is_power_of_2. Gracias a Peter Foreman por informarme de numerosos errores. Y deberías almacenar los valores previamente calculados en una tabla de búsqueda si vas a usar este código para algún número medio a grande de n.