Secuencia de Szekeres

9

Definición

  • a(1) = 1
  • a(2) = 2
  • a(n)es el número más pequeño k>a(n-1)que evita cualquier progresión aritmética de 3 términos en a(1), a(2), ..., a(n-1), k.
  • En otras palabras, a(n)es el número más pequeño k>a(n-1)tal que no existe x, ydónde 0<x<y<ny a(y)-a(x) = k-a(y).

Ejemplo resuelto

Para n=5:

Tenemos a(1), a(2), a(3), a(4) = 1, 2, 4, 5

Si a(5)=6, entonces 2, 4, 6forma una progresión aritmética.

Si a(5)=7, entonces 1, 4, 7forma una progresión aritmética.

Si a(5)=8, entonces 2, 5, 8forma una progresión aritmética.

Si a(5)=9, entonces 1, 5, 9forma una progresión aritmética.

Si a(5)=10no se puede encontrar progresión aritmética.

Por lo tanto a(5)=10.

Tarea

Dado n, salida a(n).

Especificaciones

  • n Será un número entero positivo.
  • Puede usar 0 indexado en lugar de 1 indexado, en cuyo caso npuede ser 0. Indíquelo en su respuesta si está utilizando 0 indexado.

Puntuación

Como estamos tratando de evitar la progresión aritmética de 3 términos, y 3 es un número pequeño, su código debe ser tan pequeño (es decir, corto) como sea posible, en términos de conteo de bytes.

Casos de prueba

Las cajas de prueba están indexadas en 1. Puede usar 0 indexado, pero especifíquelo en su respuesta si lo hace.

1     1
2     2
3     4
4     5
5     10
6     11
7     13
8     14
9     28
10    29
11    31
12    32
13    37
14    38
15    40
16    41
17    82
18    83
19    85
20    86
10000 1679657

Referencias

Monja permeable
fuente
2
Relacionado. (Si entiendo tu desafío correctamente.)
Martin Ender
@ MartinEnder Entendiste mi desafío correctamente.
Leaky Nun

Respuestas:

6

Haskell, 37 36 32 bytes

Usando la fórmula dada en la entrada OEIS, usando índices basados ​​en 0. ¡Gracias @nimi por 4 bytes!

a 0=1;a m=3*a(div m 2)-2+mod m 2
falla
fuente
3

Python 3, 28 bytes

lambda n:int(bin(n)[2:],3)+1

Una función anónima que toma datos a través de argumentos y devuelve el resultado. Esto está indexado a cero.

Cómo funciona

lambda n    Anonymous function with input zero-indexed term index n
bin(n)      Convert n to a binary string..
...[2:]     ...remove `0b` from beginning...
int(...,3)  ...convert from base-3 to decimal...
...+1       ...increment...
:...        and return

Pruébalo en Ideone

TheBikingViking
fuente
2

Python 3, 113 bytes

def f(n):
 i=1;a=[]
 for _ in range(n):
  while any(i+x in[y*2for y in a]for x in a):i+=1
  a+=[i]
 return a[n-1]

Ideone it!

Monja permeable
fuente
2

Rubí, 28 24 bytes

Usando el mismo método que Dennis, con índices basados ​​en 0:

->n{n.to_s(2).to_i(3)+1}

Ejecute los casos de prueba en repl.it: https://repl.it/Cif8/1

Jordán
fuente
2

Pyke, 5 bytes

b2b3h

Pruébalo aquí!

Indexación basada en 0

Misma fórmula que la respuesta de gelatina

Azul
fuente
0

Java 8, 52 46 bytes

0 indexado.

i->Integer.valueOf(Integer.toString(i,2),3)+1;
Justin
fuente
No necesita el returnpero sí necesita el punto y coma después
Leaky Nun
Esta respuesta que dice punto y coma no se cuenta; Podría cambiarlo de cualquier manera, ¿pero contar puntos y comas es el consenso?
Justin
Eh, eso es lo que me dijeron. No sé si el consenso es como tal.
Leaky Nun
Muy bien, no hay retorno más punto y coma es más corto que antes de todos modos :)
Justin