OEIS a une variation (A111439) sur la séquence de Golomb . Comme dans la séquence de Golomb, A(n)décrit la fréquence d' napparition dans la séquence. Mais en plus, aucun numéro consécutif ne peut être identique. Lors de la création de la séquence, A(n)est toujours choisi comme le plus petit entier positif qui ne viole pas ces deux propriétés. En raison de numéros identiques consécutifs interdits, la série oscille légèrement de haut en bas à mesure qu'elle grandit. Voici les 100 premiers termes:

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9, 
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12, 
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15, 
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18, 
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

La liste complète des 10 000 premiers numéros peut être consultée sur OEIS .

Le défi est d'écrire un programme ou une fonction qui calcule A(n), donné n. nest 1basé pour garantir que la propriété auto-descriptive fonctionne.

Règles

Vous pouvez écrire un programme ou une fonction et utiliser l'une de nos méthodes standard de réception d'entrée et de sortie.

Vous pouvez utiliser n'importe quel langage de programmation , mais notez que ces failles sont interdites par défaut.

Il s'agit de code-golf , donc la réponse valide la plus courte - mesurée en octets - l'emporte.

Cas de test

n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

Haskell , 67 octets

f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

Définit une fonction f. Essayez-le en ligne! C'est très lent, le f 15temps de calcul expire sur TIO.

Explication

Juste pour la définition: à chaque étape, choisissez le nombre positif minimal nqui satisfait les contraintes (différent de l'entrée précédente, et qui ne s'est pas f nencore produit).

f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

Mathematica, 69 68 octets

Merci à Martin Ender d'avoir trouvé un octet supplémentaire de 1 pour moi!

Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Fonction sans nom prenant un entier positif nen entrée et retournant un entier positif. Nous construisons la liste complète des premiers néléments de cette séquence, puis prenons l' Lastélément. La liste est construite en commençant par la liste vide {}et en fonctionnant avec une fonction nfois de suite (via Nest).

La fonction en question est {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, qui prend une liste partielle de valeurs de séquence (essentiellement ##&@@#) et y ajoute la valeur suivante. La valeur suivante est calculée en commençant par x=1, puis en la remplaçant xde x+1manière répétée aussi longtemps que la condition x==Last@#||#~Count~x==#[[x]]est remplie, en d'autres termes, si l'un ou l'autre xest l'élément précédent, ou s'il xfigure déjà dans la liste le nombre correct de fois. Cette fonction crache quelques erreurs, car (par exemple) nous ne devrions pas appeler le xe élément de la liste initiale {}; cependant, les valeurs sont toutes correctes.

Python 2, 99 86 octets

Merci à @Dennis pour plusieurs améliorations totalisant 13 octets!

s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

Le programme se déroule assez naïvement: il garde la liste des valeurs déterminées jusqu'à présent et cherche à ajouter la valeur suivante. Il essaie d'ajouter un 1à la fin de la liste s'il le peut; sinon, il essaie a 2et ainsi de suite jusqu'à ce que quelque chose soit autorisé.

Maintenant, nous commençons par ensemencer les résultats pour 1,2,3être 1,2,3. Ceci est fait pour éviter tout problème avec la liste des valeurs déjà calculées étant trop courte: je suppose que si nest au moins 4alors a(n)est strictement inférieur à n. (Dans ce programme, s[n]est égal à a(n). Notre liste est en fait initialisée pour être [0,1,2,3]parce que les listes sont 0-indexées en Python. Ainsi, par exemple a(1)=s[1]=1, et a(2)=s[2]=2.)

Alors, disons que nous essayons de déterminer s[m], ce qui signifie que notre liste comprend déjà s[0], s[1], ..., s[m-1]. Nous allons commencer t=1et essayer de régler s[m]=1. Lorsque cela ne fonctionne pas, nous allons t=2et essayons de régler s[m]=2. Chaque fois que nous augmentons t, nous vérifions si s.count(t)==s[t]... mais le côté droit ne produira pas d'erreur tant que nous n'aurons jamais à aller aussi haut que t=m. La conjecture dit que nous n'avons jamais à le faire, car la première valeur que nous calculons est en fait s[4].

Cette implémentation calcule 3 valeurs de séquence de plus que nécessaire. Par exemple, si nest 8, il calculera jusqu'à s[11]ce qu'il renvoie la valeur de s[8].

Je serais heureux de voir une preuve de la conjecture. Je crois que cela peut être prouvé par une induction (forte?).

Edit: Voici une preuve de la conjecture . Nous prouvons en fait une forme légèrement plus forte de la déclaration, car elle n'implique aucun travail supplémentaire.

Théorème: Pour tout nsupérieur ou égal à 4, le terme a(n)est inférieur ou égal à (n-2).

Preuve (par Strong Induction): (Base n=4): L'énoncé est vrai pour n=4, depuis a(4) = 2 = 4-2.

Supposons maintenant que a(k)est inférieur ou égal à k-2pour tous kde 4travers à ninclusif (et supposons nest au moins 4). En particulier, cela signifie que tous les termes précédents de la séquence étaient au maximum (n-2). Nous devons montrer que ce a(n+1)sera tout au plus (n-1). Maintenant, par définition, a(n)est le plus petit entier positif qui ne viole aucune des conditions, nous devons donc simplement montrer que la valeur (n-1)ne violera aucune des conditions.

La valeur (n-1)ne violera pas la condition "pas de répétitions consécutives", car par l'hypothèse d'induction l'entrée précédente était au plus (n-2). Et cela ne violera pas la condition " a(m)est le nombre de fois mapparaît", à moins d' (n-1)avoir déjà été atteint a(n-1)fois. Mais par l'hypothèse d'induction forte, (n-1)avait déjà été atteint 0fois, et a(n-1)n'est pas égal à 0car il a(m)est positif pour tous m.

a(n+1)Est donc inférieur ou égal à n-1 = (n+1)-2, comme souhaité. QED.

Gelée , 17 octets

Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

Les trois derniers cas de test sont trop pour TIO. J'ai vérifié 1000 et 1257 localement.

Essayez-le en ligne! ou vérifiez les 100 premiers termes .

Comment ça marche

⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.


Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

Python 2 , 77 74 octets

f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

Il s'agit d'une implémentation récursive de l'algorithme de @ mathmandan .

L'implémentation est O (fou) : l'entrée 9 prend localement 2 secondes, l'entrée 10 52 secondes et l'entrée 11 17 minutes et 28 secondes. Cependant, si elle est déclarée comme une fonction régulière plutôt que comme lambda, la mémorisation peut être utilisée pour vérifier les cas de test.

Essayez-le en ligne!

Notez que même avec la mémorisation, TIO ne peut pas calculer f (1257) ou f (10000) (tous deux vérifiés localement).

05AB1E , 32 31 octets

XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

Essayez-le en ligne!

Explication

XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true     
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list 
                                   and output last value in list and end of program

Nous sommes techniquement en boucle Glorsque nous ajoutons N à la liste globale, mais toutes les boucles de 05AB1E utilisent la même variable N comme index, donc la boucle interne [...]a écrasé le N de Gsens, nous pouvons l'ajouter en dehors de la boucle.

Les problèmes avec les boucles imbriquées et les conditions nous empêchent de le faire à l'intérieur de la boucle.

Befunge, 141 136 octets

<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

Essayez-le en ligne!

En raison des limites de mémoire de Befunge, il n'est pas vraiment pratique de garder une trace de toutes les entrées d'entrées précédentes dans la séquence, donc cette solution utilise un algorithme avec une empreinte mémoire inférieure qui calcule les valeurs plus directement.

Cela dit, nous sommes toujours limités par la taille de la cellule, qui dans l'interpréteur de référence Befunge-93 est une valeur signée de 8 bits, de sorte que le nombre pair le plus élevé pris en charge dans la séquence est A(1876) = 126, et le nombre impair le plus élevé pris en charge est A(1915) = 127.

Si vous souhaitez tester des valeurs plus grandes, vous devrez utiliser un interpréteur avec une taille de cellule plus grande. Cela devrait inclure la plupart des implémentations de Befunge-98 ( essayez-le en ligne! ).

Python 2, 117 octets

Meh. Pas si court. La solution itérative simple.

L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

Essayez-le en ligne

Voici une très mauvaise tentative de solution récursive (129 octets):

def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)