La séquence est trop méta

25

Nous commençons par une séquence vierge indexée sur 1:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,...

Dans la n ème étape, nous remplissons tous les a (n) blancs avec les entiers supérieurs à 1 en commençant par le premier blanc restant, où a (n) est la n ème entrée de la séquence.

Après la première étape:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,...

Notez que a (1) doit être 2 car le premier entier supérieur à 1 est 2.

Dans la deuxième étape, nous remplissons tous les a (2) blancs. Il sera évident que a (2) doit être 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,...

Dans la troisième étape, nous remplissons tous les a (3) blancs. De la séquence, a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,...

Dans la quatrième étape, nous remplissons tous les a (4) blancs. De la séquence, a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,...

Finalement:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,...

Tâche

Étant donné n, retournez le n ème élément de la séquence.

Les 10 000 000 premiers termes de la séquence peuvent être trouvés ici .

C'est du code-golf . La réponse la plus courte en octets l'emporte. Des échappatoires standard s'appliquent.

code-golf sequence Leaky Nun
la source
@LuisMendo Merci, je l'ai ajouté.
Leaky Nun
Juste curieux, quel mal a fait M. One pour être exclu de la séquence?
Dead Possum
@DeadPossum bien, si vous remplissez chaque blanc, alors vous avez terminé en une seule étape.
Leaky Nun
2
@DeadPossum Si a (n) vaut 1, alors la nième étape remplira tous les blancs restants, mettant fin à la génération.
Leaky Nun
1
@QBrute J'ai fourni une liste des premiers 10 000 000 liés dans la question; il suffit de les tracer.
Leaky Nun

Réponses:

20

Haskell , 80 67 octets

g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m

Essayez-le en ligne!

Haskell est le langage parfait pour définir une liste infinie en termes de lui-même.

Anders Kaseorg
la source
1
Étant donné que le lien TIO fonctionne comme prévu, je suppose que ma question devrait plutôt être: pourriez-vous ajouter une explication sur la façon dont cela fonctionne?
Julian Wolf
2
@JulianWolf On dirait que vous n'êtes pas familier avec les letgardes de modèle.pattern1 | let pattern2 = expr2 = expr1signifie la même chose que pattern1 = let pattern2 = expr2 in expr1(pour la même raison cela [expr1 | let pattern2 = expr2]signifie la même chose que [let pattern2 = expr2 in expr1]).
Anders Kaseorg
1
Je dois me souvenir let des gardes de modèle (surtout qu'ils peuvent faire des fonctions)! En outre, m=2:2:2`drop`g mest un octet plus court.
Ørjan Johansen
1
(!!)$0:m est de deux octets plus court.
Ørjan Johansen
1
En fait, vous pouvez laisser tomber la 2:2:substance entièrement avec un peu plus de paresse: g ~(a:b)|...et m=g m.
Ørjan Johansen
10

C, 123 octets

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

Essayez-le en ligne!

Procédure pas à pas

f(n){int*p=calloc(n,4),

Allouer un tableau de n entiers pour stocker les n premiers éléments de la séquence. Ce code dur sizeof(int)comme 4, qui est une hypothèse sûre dans la plupart des cas et certainement que je suis prêt à faire dans le contexte du golf de code. :)

i=0,j,k;

Ce sont tous des compteurs: ipour l'index de l'étape sur laquelle nous nous trouvons, jparcourir la séquence à la recherche d'espaces vides et kcompter le nombre d'espaces vides qui ont été vus.

for(*p=p[1]=2;i<n;++i)

Avant de commencer notre boucle principale, nous nous faufilons dans une initialisation des deux premiers éléments de la séquence pour 2 . ( p[0]= *(p + 0)= *p.) Cela jette le décompte pour k, cependant, mais ...

for(j=0,k=i/2?0:2-i;j<n;++j)

... nous faisons également une initialisation sournoise de k , qui teste si iest inférieur à 2et corrige la valeur de départ de ksi oui. La boucle intérieure commence également ici, qui itère sur toute la séquence jusqu'à présent à chaque étape.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

Cette ligne pourrait vraiment utiliser quelques explications. Nous pouvons l'étendre à:

if (!(p[j] || ((k++) % p[i]))) {
    p[j] = k / p[i] + 2;
}

par court-circuitage, puis par les lois de De Morgan et le fait qu'il 0est faux en C:

if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
}

Cela indique essentiellement: "si cet espace est vide, incrémentez k. Et s'il ks'agissait auparavant d'un multiple de la taille de l'étape, exécutez l'instruction suivante." Par conséquent, nous exécutons l'instruction sur chaque élément de taille de pas , ce qui est exactement la façon dont la séquence est décrite. La déclaration elle-même est simple; tout ce qu'il fait est de générer 2, 3, 4, ....

n=p[n-1];}

En utilisant le retour délicat sans retour qui fonctionne avec gcc, nous «renvoyons» le dernier élément des n premiers termes de la séquence, qui se trouve être le n ème terme.

Poignée de porte
la source
3

Pyth, 29 octets

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1

Essayez-le en ligne

Comment ça marche

Au lieu de jouer avec les listes, cela utilise une formule récursive simple.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input())))
Anders Kaseorg
la source
3

Haskell , 67 octets

0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j<i]
f=(%1).pred

Essayez-le en ligne!

Une solution arithmétique récursive qui s'est avérée essentiellement la même méthode que la réponse Pyth d'Anders Kaseorg .

Ce code est couvert de verrues - des parties laides qui semblent pouvoir être jouées au golf, mais je n'ai pas vu comment.

La fonction i%jveut vraiment utiliser un garde pour vérifier si mod i(f j)>0et évaluer l'une des deux expressions correspondantes. Mais, les deux expressions utilisent div i(f j). Lier cela dans un garde ne le fera pas s'appliquer aux deux côtés. Autant que je sache, on ne peut pas faire en sorte qu'un garde "se répartisse" sur les autres gardes. letet wheresont trop longs. Ainsi, le code utilise lastpour choisir l'une des deux expressions pendant que le garde lie la variable. Pouah.

Idéalement, nous utiliserions divModparce que les deux divet modsont utilisés, mais (d,m)<-divMod ...c'est une longue expression. Au lieu de cela, nous vérifions de manière hackeuse que le mod n'est pas nul en voyant si la divvaleur multipliée par le diviseur est inférieure à la valeur d'origine.

L' 0%j=2affaire ne serait pas nécessaire si Haskell court-circuite div 0, ce qui n'est pas le cas. Le .predconvertit l'entrée indexée 1 en indexée zéro, sinon il y aurait des -1corrections partout.

xnor
la source
Si vous activez l' %index 1, vous avez besoin d'une correction de cinq octets - qui ne fait que lier. Cependant , vous pouvez alors en ligne fen %sans frais, puis fdevient anonyme si vous enregistrez deux octets d' ensemble.
Ørjan Johansen
@ ØrjanJohansen Que voulez-vous dire ici par inline? Je ne vois pas comment changer les références fsans perdre d'octets.
xnor
divModsemble être un octet moins cher, car il permet la ramification avec !!(0^m). Jusqu'à présent, j'ai:1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);(%1)
Ørjan Johansen
Comme vous le voyez, l'inline présuppose la 1-réindexation, ce qui supprime le .pred.
Ørjan Johansen
2

JavaScript (ES6), 98 93 91 octets

Une fonction récursive qui s'arrête dès que le résultat est disponible.

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Version alternative, 90 octets

Suggéré par Shaggy pour -1 octet

Celui-ci doit être appelé avec f(n)(). Bien que le poste correspondant en méta donne actuellement un score positif, cette syntaxe est apparemment contestée.

n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Démo

Afficher l'extrait de code

Arnauld
la source
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k?c:++v:(i=1,v=2),i=0,k=a[p]||2))devrait fonctionner pour 92 octets. Appelez-le avec f(n)().
Shaggy
@Shaggy Merci! Ajouté en tant que version alternative.
Arnauld
1

Java 8, 124 octets

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];}

Expression lambda.

Crée un tableau entier et le remplit continuellement jusqu'à ce que la nième valeur soit remplie.

Pré-déclaration des variables en haut pour réduire autant de déclarations que possible car chacune intcoûte 4 octets d'espace au lieu d'ajouter,n 2.

À la j'ième itération de calcul, le nombre de' blancs 'qu'il faut sauter est égal à a[j](ou 2, si vide). Il se trouve que si le premier espace vide que nous devons remplir est en position k, k * a[j]nous donne le «step» ( s).

Xanderhall
la source