La secuencia de números segmentados o números primos de medición ( OEIS A002048 ) es la secuencia de números de manera que cada miembro es el número positivo más pequeño (mayor que cero) que no se puede hacer de una suma de números consecutivos anteriores, con a(0) = 1.

Ejemplo

Para calcular a(7)primero calculamos a(0->6) = [1, 2, 4, 5, 8, 10, 14]. entonces comenzamos desde cero y pasamos por los números hasta encontrar uno que no es la suma de uno o más números consecutivos en la secuencia.

1  = 1
2  = 2
3  = 1 + 2
4  = 4
5  = 5
6  = 2 + 4
7  = 1 + 2 + 4
8  = 8
9  = 4 + 5
10 = 10
11 = 2 + 4 + 5
12 = 1 + 2 + 4 + 5
13 = 5 + 8
14 = 14
15 = ????

Dado que no se pueden hacer quince sumando ninguna subsecuencia consecutiva y cada número más pequeño puede ser quince es el siguiente número en la secuencia. a(7) = 15

Tarea

Su tarea es tomar un número (a través de métodos estándar) y generar el enésimo término en esta secuencia (a través de métodos de salida estándar). Este es el código de golf y se le puntuará como tal.

Casos de prueba

0 -> 1
1 -> 2
2 -> 4
3 -> 5
4 -> 8
5 -> 10
6 -> 14
7 -> 15
8 -> 16
9 -> 21

code-golf sequence Post Rock Garf Hunter
fuente

12

Haskell, 62 58 bytes

-4 bytes gracias a @xnor!

(x:y)#z=x:filter(`notElem`scanl(+)x z)y#(x:z)
([1..]#[]!!)

La secuencia está indexada a 0.

ThreeFx
fuente

1

Creo que necesita dos bytes más y rodear la última línea ()para que sea una función adecuada. El parcial aplicado !!es una sección del operador y debe encerrarse ()para que sea una función. Sin él, es solo un fragmento que solo se convierte en una función (o "valor" para usar términos estrictos de Haskell) con el argumento que falta.

nimi

1

Hermoso método! Sin embargo, la importación parece exagerada; filter(`notElem`scanl(+)x z)ydebería hacer.

xnor

7

Perl, 50 49 bytes

Incluye +1 para -p

Ejecutar con entrada en STDIN:

segmented.pl <<< 7

segmented.pl:

#!/usr/bin/perl -p
${$_-=$\}++for@F;1while${-++$\};++$#F<$_&&redo}{

Explicación

@Fcontiene la lista de sumas (negativas) de números consecutivos que terminan con el último número actual. Cuando se descubre un nuevo número, la lista se extiende con 0 y luego todos los valores se reducen por el nuevo número que mantiene el invariante.

Global %::se utiliza como un hash que asigna todos los números (negativos) que se han visto (hasta @F) a un valor distinto de cero.

$\es el número actual y se incrementa hasta que alcanza un valor que aún no está en %::.

Al tener un poco de cuidado con el orden en que sucede todo, no se necesita inicialización, 1se convertirá automáticamente en el primer número.

Dado que el tamaño de @Fcuántos números se han generado, se puede usar como una condición de detención

Ton Hospel
fuente

4

05AB1E , 17 16 bytes

Xˆ$µ>D¯ŒOså_i¼Dˆ

Explicación

Xˆ                # initialize global array to [1]
  $               # push 1 and input to stack
   µ              # while counter != input
    >             # increase variable on stack
      ¯ŒO         # list of all sums of consecutive number in global array
     D   så_i     # if current stack value is not in the list
             ¼    # increase counter
              Dˆ  # add current stack value to global array

Pruébalo en línea!

Guardado 1 byte gracias a Adnan

Emigna
fuente

¿En $lugar de Xstrabajar?

Adnan

@Adnan: Sí, por supuesto. Tonto de mi. ¡Gracias!

Emigna

4

Jalea , 14 13 11 bytes

Ḷß€Ẇ;ḅ1‘ḟ$Ṃ

Pruébalo en línea!

Cómo funciona

Ḷß€Ẇ;ḅ1‘ḟ$Ṃ  Main link. Argument: n

Ḷ            Unlength; yield [0, ..., n - 1].
 ß€          Recursively map the main link over the range.
   Ẇ         Window; yield all subarrays of consecutive elements of the result.
    ;        Append n to the array of subarrays.
     ḅ1      Convert all subarrays from base 1 to integer.
             This is equivalent to S€ (sum each), but it allows ; to hook.
         $   Combine the previous two links into a monadic chain.
       ‘       Increment all sums.
        ḟ      Filter; remove the original sums from the incremented ones.
          Ṃ  Compute the minimum.

Dennis
fuente

2

Pyth - 19 17 bytes

Maldita sea, arruinando todas mis implicidades. (El mismo número de bytes, literalmente incrementándoseQ : =hQesmaYf!}TsM.:Y)

esmaYf!}TsM.:Y)1h

Banco de pruebas .

Maltysen
fuente

Usando reduce guardar (solo) un byte. Se esperaba más ...eu+Gf!}TsM.:G))hQY

Jakube

1

El mapa de @Jakube suele ser más corto para secuencias autorreferenciales como estas

Maltysen,

2

Javascript, 125 112 110 bytes

Guardado 2 bytes gracias a @Neil

f=n=>{a=[[]];for(i=1,z=0;z<=n;i++)a.some(b=>b.includes(i))||(a[z+1]=[0,...a[z++]||[]].map(v=>i+v));alert(i-1)}

Respuestas anteriores

112 bytes gracias a @Neil:

f=n=>{a=[[]];for(i=1,z=0;z<=n;i++)if(!a.some(b=>b.includes(i))){a[z+1]=[0,...a[z++]||[]].map(v=>i+v)}alert(i-1)}

125 bytes:

f=n=>{a=[[]];for(i=1,k=z=0;z<=n;i++)if(a.every(b=>b.every(c=>c-i))){a[i]=[i].concat((a[k]||[]).map(v=>i+v));k=i,z++}alert(k)}

Hedi
fuente

1

Para b.every(c=>c-i), lo intentaría !b.includes(i)o posiblemente !a.some(b=>b.includes(i))funcione, mientras que [0,...a[k]||[]].map(v=>i+v)podría reemplazarlo [i].concat((a[k]||[]).map(v=>i+v)). ¿También realmente necesitas k?

Neil

1

Ahora que su if(!...){...}es solo una declaración, probablemente podría reemplazarla con ...||(...)o ...?0:....

Neil

1

Python, 113 105 92 80 bytes

s=F={1}
x=1
exec"while{x}<=s:x+=1\nF={x+j for j in{0}|F};s|=F\n"*input()
print x

Los bytes finales que guardé se inspiraron en la respuesta de Perl de Ton: mi Fhace lo mismo que el suyo @F; mi shace esencialmente lo mismo que el suyo %::.

Lynn
fuente

1

JavaScript (ES6), 77 bytes

(n,a=[],s=a,i=1)=>s[i]?f(n,a,s,i+1):--n?f(n,[0,...a].map(j=>s[j+=i]=j),s,i):i

Básicamente, un puerto recursivo del algoritmo de la respuesta Perl de @ TonHospel.

Neil
fuente

Números segmentados