Inspirado en la pregunta anterior .

La secuencia autodescriptiva de Golomb g (n) es una secuencia en la que cualquier número natural nse repite dentro de la secuencia g (n) veces.

Los primeros pocos números en la secuencia son:

n    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
g(n) 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Puede ver que g (4) = 3, y que "4" se repite 3 veces en la secuencia.

Dada una entrada de n, salida g(n).

Limitaciones: n <100000.

El código más pequeño gana.

GolfScript (31 caracteres)

~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=

Manifestación

Gelatina , no competidora

10 bytes Esta respuesta no es competitiva, ya que el desafío es anterior a la creación de Jelly.

’ßßạ¹ß‘µṖ¡

Utiliza la fórmula recursiva a (1) = 1, a (n + 1) = 1 + a (n + 1 - a (a (n))) de la página OEIS.

Pruébalo en línea!

Cómo funciona

’ßßạ¹ß‘µṖ¡ Main link. Input: n

’          Decrement; yield n - 1.
 ßß        Recursively call the main link twice, with argument n - 1.
   ạ¹      Take the absolute difference of a(a(n - 1)) and n.
     ß     Recursively call the main link, with argument n - a(a(n - 1)).
      ‘    Increment the result, yielding 1 + a(n - a(a(n - 1))).
       µ   Combine the chain to the left into a single link.
        Ṗ  Pop [1, ..., n]. This yields [] iff n == 1.
         ¡ Execute the chain iff Ṗ returned a non-empty array.

PHP - 63 caracteres

function g($n){for(;++$i<=$n;){for(;++$j<=$i;){echo $i;}$j=0;}}

Rápido y corto.

Parece que tuve en mente la secuencia incorrecta. Derp.

Esto es CORRECTO, rápido y corto.

function g($n){for(;++$i<$n;){echo round(1.201*pow($i,.618));}}

La precisión puede sufrir más allá de la marca requerida de 100,000, pero de hecho cumplí con la marca.

PHP

Esta versión recursiva es más corta (60) pero computacionalmente ineficiente:

function g($n){return$n==1?1:1+g($n-g(g($n-1)));}echo g($n);

Esto es mucho más rápido pero más largo (78):

$a=[1,2,2];for($i=3;$i<$n;$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Mucho más rápido, pero con 89 caracteres sería:

$a=[1,2,2];for($i=3;!isset($a[$n-1]);$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Que es O (n)

Haskell, 30 27 caracteres

g 1=1
g n=1+(g$n-g(g$n-1))

Oasis , 7 bytes (no competitivos)

Código:

n<aae>T

Pruébalo en línea!

Oasis es un lenguaje diseñado por Adnan especializado en secuencias.

Actualmente, este lenguaje puede hacer recursividad y forma cerrada.

Al Tfinal es la abreviatura de 10, que indica que a(0) = 0y a(1) = 1. Para agregar más casos de prueba, simplemente agregue a la lista al final.

n<aae>T
n<aae>10  expanded

       0  a(0) = 0
      1   a(1) = 1

n         push n (input)
 <        -1
  a       a(above)  [a is the sequence]
   a      a(above)
    e     a(n-above)
     >    +1

Ahora esencialmente calculamos a(n-a(a(n-1))+1.

Perl, 48 caracteres

(@a=(@a,($,)x($a[$,++]||$,)))<$_?redo:say$,for<>

Entrada en stdin, salida a stdout. Necesita Perl 5.10+ y el -M5.010para habilitar la sayfunción. Toma alrededor del tiempo O ( n ² ) debido a la manipulación ineficiente de la matriz, pero aún lo suficientemente rápido como para calcular fácilmente hasta el término 100,000.

Julia - 28

De manera recursiva :

a(n)=n==1?1:1+a(n-a(a(n-1)))

Salida:

[a(i) for i=1:20]'
1x20 Array{Int64,2}:
 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Python - 64 caracteres

n=input()
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]

Javascript, 93 caracteres

c=[,1],i=c.length;function g(n){for(i;i<n;i++) c[i]=g(i);return c[n]||(c[n]=1+g(n-g(g(n-1))))}

J, 43 caracteres

f=:3 :'<.@:+&0.5(p^2-p)*y^p-1[p=:(+%)/20$1'

Define una función utilizando la expresión asintótica dada en la página de wikipedia.

   f 5
3
   f 20
8
   f 100000
1479

Molestamente, se usan 9 caracteres simplemente redondeando al entero más cercano.

Preludio , 69 55 54 bytes

?1-(v  #1)-
1   0v ^(#    0 (1+0)#)!
    (#)  ^#1-(0)#

Si se utiliza un intérprete compatible estándar, esto toma la entrada y la salida como valores de byte . Para usar números decimales en STDIN / STDOUT, necesitaría el intérprete de Python con NUMERIC_OUTPUT = Trueuna opción adicional NUMERIC_INPUT = True.

Explicación

El esqueleto del programa es

?1-(    1 -
1                     )!

Leemos la entrada Nen la primera voz y la disminuimos para obtener N-1. También inicializamos la segunda voz para 1. Luego hacemos N-1un bucle una vez, cada iteración de la cual obtiene el siguiente valor de la secuencia en la segunda pila. Al final imprimimos el Nnúmero th.

La idea del programa es poner cada elemento de la secuencia en una cola en la tercera voz, y disminuir el encabezado de esa cola en cada iteración. Cuando la cabeza alcanza 0, incrementamos el valor de la secuencia y lo eliminamos 0.

Ahora el problema es que Prelude usa pilas y no colas. Así que tenemos que cambiar un poco esa pila para usarla como una cola.

v  #
0v ^
(#)

Esto copia el valor actual de la secuencia a la primera voz (como una copia temporal), empuja a 0a la segunda voz (para marcar el final de la cola). Y luego realiza un bucle para desplazar (y por lo tanto invertir) la tercera pila sobre la segunda. Después del ciclo, colocamos la copia del valor de secuencia actual en la parte superior de la segunda pila (que es la cola de nuestra cola).

 )
(#
 ^#1-

Esto se ve un poco feo, pero esencialmente es un bucle que cambia la pila de nuevo a la tercera voz. Dado que )está en la misma columna que las instrucciones de cambio, la 0que ponemos en la segunda voz antes también terminará en la tercera voz, por lo que debemos eliminarla con otra #. Luego disminuya la parte superior de la tercera voz, es decir, la cabeza de la cola.

Ahora se vuelve un poco molesto: queremos ejecutar algo de código cuando ese valor es 0, pero la única estructura de control de Prelude (el bucle) solo responde a valores distintos de cero.

 0 (1+0)#
(0)#

Tenga en cuenta que la parte superior de la segunda voz es verdadera (ya que la secuencia de Golomb no contiene ninguna 0s). Entonces, la carga de trabajo entra en esa voz (el último par de paréntesis). Solo necesitamos evitar que eso suceda si la cabeza de la cola 0aún no está . Entonces, primero tenemos un "bucle" en la tercera voz que empuja 0a la segunda voz si el encabezado de la cola todavía no es cero. También ponemos una 0tercera voz para salir del bucle de inmediato. El #en la tercera voz a continuación, elimina o bien que 0, o elimina la cabeza de la cola si que ya cero era. Ahora ese segundo ciclo solo se ingresa si el encabezado de la cola era cero (y el0en la segunda voz nunca fue presionada). En ese caso, incrementamos el valor actual de la secuencia y presionamos a 0para salir del bucle. Por último, siempre habrá un 0en la parte superior de la pila, que debemos descartar.

Te dije que la negación lógica es molesta en Prelude ...

Mathematica, 27 bytes

f@1=1;f@n_:=1+f[n-f@f[n-1]]

Otra solución recursiva.

CJam, 14 bytes

CJam es mucho más joven que este desafío, por lo que esta respuesta no es elegible para la marca de verificación verde. Sin embargo, es bastante raro que puedas usar jesto muy bien, así que quería publicarlo de todos modos.

l~2,{_(jj-j)}j

Pruébalo aquí.

Explicación

jes básicamente el "operador de recursión memorizado". Se necesita un número entero N, una matriz y un bloque F. La matriz se utiliza para inicializar la memorización: ise devolverá el elemento en el índice F(i). jluego calcula F(N), ya sea buscándolo o ejecutando el bloque (con nen la pila) si el valor aún no se ha memorizado. La característica realmente ingeniosa es que dentro del bloque, jsolo toma un número entero iy llama F(i)recursivamente. Entonces aquí está el código:

l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";

J, 16 bytes

    <:{1($1+I.)^:[~]

    (<:{1($1+I.)^:[~]) every 1+i.20  NB. results for inputs 1..20
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8

Esta solución se basa en gran medida en la solución de algoritmoshark a un problema similar. Puede encontrar alguna explicación sobre este método allí.

J, 33 bytes

En este enfoque, construyo una secuencia h(k)con los valores de los primeros índices idonde es g(i)=kasí h = 1 2 4 6 9 12 16.... Podemos obtener de manera h(k)bastante simple h(1..k-1)con la expresión ({:+1+[:+/#<:])donde está la entrada h(1..k-1).

Calcular la salida de hes sencillo.h ([:+/]>:[) input

[:+/]>:1 2(,{:+1+[:+/#<:])@]^:[~]

Brachylog , 13 bytes (no competidor)

1|-₁↰↰:?-ṅ↰+₁

Pruébalo en línea!

Explicación

1                Input = 1 = Output
 |               Or
  -₁↰            a(Input - 1)
     ↰           a(a(Input - 1))
      :?-ṅ       Input - a(a(Input - 1))
          ↰      a(Input - a(a(Input - 1))
           +₁    1 + a(Input - a(a(Input -1))

Python - 76 caracteres

n=20;g=[1,2,2];[[g.append(i)for j in range(g[i-1])]for i in range(3,n)];g[n]

JavaScript: 48 caracteres

for(g=[,i=j=k=1,2];i<1e5;k=--k?k:g[++j])g[i++]=j

Crea una matriz indexada 1 que gcontiene los valores de secuencia.

Editar - JavaScript - 46 caracteres

v=[,1];for(x=2;x<1e5;)v[x]=1+v[x-v[v[x++-1]]]

Crea una matriz indexada 1 que vcontiene los valores de secuencia.

Edición 2 - ECMAScript 6 - 27 caracteres

g=x=>x-1?1+g(x-g(g(x-1))):1

Los dos primeros son razonablemente rápidos: el tercero es muy lento

Haskell, 63 bytes

f n|n<3=n|n<4=2|1>0=foldr1(++)[replicate(f m)m|m<-[1..]]!!(n-1)

Este es el enfoque ingenuo, no era consciente de la breve recurrencia cuando escribí esto, pero pensé en publicarlo de todos modos, incluso si es más largo que todas las demás implementaciones de Haskell, como por ejemplo

Calcule el enésimo término de la secuencia autodescriptiva de Golomb

y

/codegolf//a/23979/24877