Inspiré par la question précédente .

La séquence auto-descriptive de Golomb g (n) est une séquence où tout nombre naturel nest répété dans la séquence g (n) fois.

Les premiers chiffres de la séquence sont les suivants:

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

Vous pouvez voir que g (4) = 3 et que "4" est répété 3 fois dans la séquence.

Étant donné une entrée de n, une sortie g(n).

Limitations: n <100000.

Le plus petit code gagne.

GolfScript (31 caractères)

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

Démo

Gelée , non compétitive

10 octets Cette réponse n'est pas concurrente, car le défi est antérieur à la création de Jelly.

’ßßạ¹ß‘µṖ¡

Cela utilise la formule récursive a (1) = 1, a (n + 1) = 1 + a (n + 1 - a (a (n))) de la page OEIS.

Essayez-le en ligne!

Comment ça fonctionne

’ßßạ¹ß‘µṖ¡ 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 caractères

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

Rapide ET court.

Il me semble avoir eu la mauvaise séquence en tête. Derp.

C'est CORRECT, rapide et court.

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

La précision peut souffrir au-delà de la barre des 100 000, mais je l'ai en fait atteinte.

PHP

Cette version récursive est plus courte (60) mais inefficace sur le plan des calculs:

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

C'est beaucoup plus rapide mais plus long (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];

Beaucoup plus rapide, mais à 89 caractères serait:

$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];

Qui est O (n)

Haskell, 30 27 caractères

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

Oasis , 7 octets (non concurrent)

Code:

n<aae>T

Essayez-le en ligne!

Oasis est un langage conçu par Adnan qui est spécialisé dans les séquences.

Actuellement, cette langue peut faire récursivité et forme fermée.

Le Tà la fin est un raccourci pour 10, ce qui indique que a(0) = 0et a(1) = 1. Pour ajouter plus de tests, ajoutez simplement à la liste à la fin.

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

Maintenant, nous avons essentiellement calculé a(n-a(a(n-1))+1.

Perl, 48 caractères

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

Entrée sur stdin, sortie sur stdout. Nécessite Perl 5.10+ et le -M5.010pour activer la sayfonctionnalité. Prend environ O ( n ² ) en raison d'une manipulation de tableau inefficace, mais toujours assez rapide pour calculer facilement jusqu'au 100 000e terme.

Julia - 28

De manière récursive :

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

Production:

[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 caractères

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

Javascript, 93 caractères

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 caractères

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

Définit une fonction en utilisant l'expression asymptotique donnée sur la page wikipedia.

   f 5
3
   f 20
8
   f 100000
1479

De façon ennuyeuse, 9 caractères sont utilisés en arrondissant à l'entier le plus proche.

Prélude , 69 55 54 octets

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

Si un interpréteur conforme standard est utilisé, cela prend l'entrée et la sortie comme valeurs d'octet . Pour utiliser réellement des nombres décimaux sur STDIN / STDOUT, vous auriez besoin de l'interpréteur Python avec NUMERIC_OUTPUT = Trueet d'une option supplémentaire NUMERIC_INPUT = True.

Explication

Le squelette du programme est

?1-(    1 -
1                     )!

Nous lisons l'entrée Nsur la première voix et la décrémentons pour l'obtenir N-1. Nous initialisons également la deuxième voix pour 1. Ensuite, nous bouclons N-1une fois, dont chaque itération obtient la valeur suivante de la séquence sur la deuxième pile. À la fin, nous imprimons le Nnuméro e.

L'idée du programme est de mettre chaque élément de la séquence dans une file d'attente sur la troisième voix, et de décrémenter la tête de cette file d'attente à chaque itération. Lorsque la tête atteint 0, nous incrémentons la valeur de la séquence et la supprimons 0.

Maintenant, le problème est que Prelude utilise des piles et non des files d'attente. Nous devons donc déplacer un peu cette pile pour l'utiliser comme une file d'attente.

v  #
0v ^
(#)

Cela copie la valeur actuelle de la séquence sur la première voix (en tant que copie temporaire), pousse a 0sur la deuxième voix (pour marquer la fin de la file d'attente). Et effectue ensuite une boucle pour décaler (et ainsi inverser) la troisième pile sur la seconde. Après la boucle, nous mettons la copie de la valeur de séquence actuelle au-dessus de la deuxième pile (qui est la queue de notre file d'attente).

 )
(#
 ^#1-

Cela semble un peu moche, mais c'est essentiellement une boucle qui ramène la pile sur la troisième voix. Étant donné que le )est dans la même colonne que les instructions de décalage, le 0nous avons mis sur la deuxième voix plus tôt se retrouvera également sur la troisième voix, nous devons donc le supprimer avec un autre #. Puis décrémentez le haut de la 3ème voix, c'est-à-dire la tête de file d'attente.

Maintenant, cela devient un peu ennuyeux - nous voulons exécuter du code lorsque cette valeur est 0, mais la seule structure de contrôle de Prelude (la boucle) ne répond qu'aux valeurs non nulles.

 0 (1+0)#
(0)#

Notez que le haut de la deuxième voix est véridique (puisque la séquence de Golomb ne contient aucun 0s). La charge de travail va donc dans cette voix (la dernière paire de parenthèses). Nous devons juste empêcher cela de se produire si le chef de file d'attente n'est pas 0encore. Donc, d'abord, nous avons une "boucle" sur la troisième voix qui pousse a 0sur la deuxième voix si la tête de la file d'attente est toujours non nulle. Nous avons également mis une 0troisième voix pour quitter la boucle immédiatement. Le #sur la troisième voix , puis supprime non plus que 0, ou supprime le chef de la file d' attente si c'était déjà nul. Maintenant, cette deuxième boucle n'est entrée que si la tête de la file d'attente était nulle (et le0sur la deuxième voix n'a jamais été poussé). Dans ce cas, nous incrémentons la valeur actuelle de la séquence et appuyons sur a 0pour quitter la boucle. Enfin, il y aura toujours un 0sur le dessus de la pile, que nous devons jeter.

Je vous ai dit que la négation logique est ennuyeuse dans Prelude ...

Mathematica, 27 octets

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

Une autre solution récursive.

CJam, 14 octets

CJam est beaucoup plus jeune que ce défi, donc cette réponse n'est pas éligible pour la coche verte. Cependant, il est assez rare que vous puissiez l'utiliser jcorrectement, donc je voulais quand même le poster.

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

Testez-le ici.

Explication

jest fondamentalement "l'opérateur de récursion mémorisé". Il prend un entier N, un tableau et un bloc F. Le tableau est utilisé pour initialiser la mémoisation: l'élément à index isera retourné pour F(i). jcalcule ensuite F(N), soit en le recherchant, soit en exécutant le bloc (avec nsur la pile) si la valeur n'a pas encore été mémorisée. La fonctionnalité vraiment astucieuse est que dans le bloc, jne prend qu'un entier iet appelle F(i)récursivement. Voici donc le code:

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 octets

    <:{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

Cette solution est fortement basée sur la solution d' Algorithmshark à un problème similaire. Vous pouvez trouver des explications sur cette méthode ici.

J, 33 octets

Dans cette approche, je construis une séquence h(k)avec les valeurs des premiers index ioù le g(i)=kso h = 1 2 4 6 9 12 16.... Nous pouvons obtenir h(k)assez simplement h(1..k-1)avec l'expression ({:+1+[:+/#<:])où se trouve l'entrée h(1..k-1).

Le calcul de la sortie de hest simple.h ([:+/]>:[) input

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

Brachylog , 13 octets (non concurrent)

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

Essayez-le en ligne!

Explication

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 caractères

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 caractères

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

Crée un tableau indexé 1 gcontenant les valeurs de séquence.

Édition - JavaScript - 46 caractères

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

Crée un tableau indexé 1 vcontenant les valeurs de séquence.

Édition 2 - ECMAScript 6 - 27 caractères

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

Les deux premiers sont assez rapides - le troisième est très lent

Haskell, 63 octets

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

Ceci est l'approche naïve, je n'étais pas au courant de la récurrence très courte quand j'ai écrit ceci, mais j'ai pensé que je la publierais de toute façon, même difficile, elle est plus longue que toutes les autres implémentations Haskell, comme par exemple

Calculer le nième terme de la séquence auto-descriptive de Golomb

et

/codegolf//a/23979/24877