introduction

A229037 a une intrigue assez intrigante (au moins pour les premiers termes):

Il y a la conjecture, qu'il pourrait en effet avoir une sorte de propriété fractale.

Comment se construit cette séquence?

Définissez a(1) = 1, a(2) = 1ensuite pour chaque n>2recherche un entier positif minimal a(n)tel que pour chaque séquence n,n+k,n+2kd'indices arithmétique à 3 termes , les valeurs correspondantes de la séquence nea(n),a(n+k),a(n+2k) soient pas une séquence arithmétique.

Défi

Étant donné un entier positif nen entrée, sortez les premiers ntermes a(1), ... , a(n)de cette séquence. (Avec tout formatage raisonnable. Les caractères / chaînes de début / de fin possibles ne sont pas pertinents.)

Il existe des extraits pour générer cette séquence, mais je pense que d'autres approches pourraient être plus adaptées au golf / plus adaptées à certaines langues.

Veuillez nous faire savoir comment fonctionne votre programme. Si vous croisez un algorithme particulièrement efficace, vous voudrez peut-être également le mentionner, car cela permettrait de tracer plus de termes de la séquence en un temps plus court.

Premiers cas de test:

1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13

Plus de tests:

  a(100)  =   4
  a(500)  =   5
 a(1000)  =  55
 a(5000)  =  15
a(10000)  = 585

Tous les termes jusqu'à n=100000sont disponibles ici: https://oeis.org/A229037/b229037.txt

Merci @ MartinBüttner pour l'aide et les encouragements.

Python 2, 95 octets

l=[];n=input()
exec"a=min(set(range(n))-{2*b-c for b,c in zip(l,l[1::2])});print-~a;l=[a]+l;"*n

L'astuce principale consiste à générer les nombres que la nouvelle valeur doit éviter. En gardant la séquence inversée jusqu'à présent l, regardons quels éléments pourraient former une progression arithmétique à trois termes avec la valeur que nous sommes sur le point d'ajouter.

? 4 2 2 1 1 2 1 1   a b c
^ ^ ^               ? 4 2
^   ^   ^           ? 2 1
^     ^     ^       ? 2 2
^       ^       ^   ? 1 1

Les autres nombres sont les membres appariés de let chaque deuxième élément de l, donc zip(l,l[1::2]). Si cette paire est (b,c)alors la progression arithmétique (a,b,c)se produit pour a=2*b-c. Après avoir généré l'ensemble de a's à éviter, le code prend le minimum du complément, l'imprime et l'ajoute à la liste. (En fait, le calcul se fait avec des nombres diminués de 1, et imprimés 1 plus haut, pour laisser range(n)servir d'univers de candidats.)

Mathematica, 95 octets

For[n_~s~k_=0;n=0,n<#,For[i=n,--i>0,s[2n-i,2f@n-f@i]=1];For[++n;i=1,n~s~i>0,++i];Print[f@n=i]]&

Certainement pas l'approche la plus golfique, mais c'est en fait assez efficace, par rapport aux algorithmes que j'ai essayés depuis la page OEIS.

Au lieu de vérifier toutes les valeurs interdites pour chaque s (n) lorsque nous y arrivons, j'utilise une approche basée sur un tamis. Lorsque nous trouvons une nouvelle valeur s (n), nous vérifions immédiatement quelles valeurs cela interdit pour m> n . Ensuite, nous résolvons simplement le s (n + 1) en recherchant la première valeur qui n'était pas interdite.

Cela peut être rendu encore plus efficace en changeant le conditionnel --i>0en 2n-#<=--i>0. Dans ce cas, nous évitons de vérifier les valeurs interdites pour n supérieur à l'entrée.

Pour une version un peu plus lisible, j'ai commencé avec ce code, qui stocke les résultats jusqu'à maxdans une fonction f, puis je l'ai joué à la fonction pure d'une ligne ci-dessus:

 max = 1000;
 ClearAll[sieve, f];
 sieve[n_, k_] = False;
 For[n = 0, n < max,
  temp = f[n];
  For[i = n - 1, i > 0 && 2 n - i <= max, --i,
   sieve[2 n - i, 2 temp - f[i]] = True;
   ];
  ++n;
  i = 1;
  While[sieve[n, i], ++i];
  f@n = i;
  ]

Haskell, 90 , 89 , 84 , 83 octets

Peut probablement être joué au golf plus, mais c'est toujours une première tentative décente :

a n|n<1=0|n<3=1|1<2=[x|x<-[1..],and[x/=2*a(n-k)-a(n-k-k)||a(n-k-k)<1|k<-[1..n]]]!!0

Ungolfed:

a n | n<1        = 0 
    | n<3        = 1
    | otherwise  = head (goods n)

goods n = [x | x <- [1..], isGood x n]

isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]

Il s'agit d'une implémentation simple qui renvoie «0» pour hors limites. Ensuite, pour chaque valeur possible, il vérifie que pour tous les k <= n et aux bornes, [x, a (xk), a (x-2k)] n'est pas une séquence arithmétique.

Limite supérieure de la complexité temporelle (en utilisant le fait de la page OEIS que a (n) <= (n + 1) / 2:

t n <= sum[ sum[2*t(n-k) + 2*t(n-k-k) | k <- [1..n]] | x <- [1..(n+1)/2]]
    <= sum[ sum[4*t(n-1)              | k <- [1..n]] | x <- [1..(n+1)/2]]
    <= sum[     4*t(n-1)*n                         ] | x <- [1..(n+1)/2]]
    <=          4*t(n-1)*n*(n+1)/2
    ->
O(t(n)) == O(2^(n-2) * n! * (n+1)!)

Je ne sais pas à quel point cette limite est bonne car le calcul des premières valeurs de 1k de 't' et l'utilisation d'un modèle linéaire sur les journaux des valeurs ont donné appx. O (22 ^ n), avec une valeur de p <10 ^ (- 1291), au cas où cela compte.

Au niveau de l'implémentation, en compilant avec '-O2', il a fallu ~ 35 min pour calculer les 20 premières valeurs.

Brachylog , 33 31 octets

;Ė{~b.hℕ₁≜∧.¬{ġh₃hᵐs₂ᶠ-ᵐ=}∧}ⁱ⁽↔

Essayez-le en ligne!

Au cas où cela compte: Le golf sur 2 octets a été possible grâce à une fonctionnalité que j'ai demandée après avoir travaillé sur ce défi.

Explication

Nous générons de manière itérative la séquence sous forme de liste dans l'ordre inverse, par exemple [2,2,1,1,2,1,1], et l'inversons à la fin.

Il y a quelques prédicats imbriqués ici. Regardons-les de l'intérieur. Le premier,, ġh₃hᵐs₂ᶠ-ᵐ=prend une sous-séquence candidate a(n),a(n-1),...,a(0)et détermine s'il a(n),a(n-k),a(n-2k)s'agit d'une séquence arithmétique pour certains k.

ġ            Group the list into equal-length sublists (with the possible exception of
             the last sublist, which might be shorter)
 h₃          Get the first 3 sublists from that list
   hᵐ        and get the head of each of those 3 sublists
             We now have a list containing a(n),a(n-k),a(n-2k) for some k
     s₂ᶠ     Find all 2-element sublists of that list: [a(n),a(n-k)] and [a(n-k),a(n-2k)]
        -ᵐ   Find the difference of each pair
          =  Assert that the two pairwise differences are equal

Par exemple, avec l'entrée de [1,2,1,1,2,1,1]:

ġ has possible outputs of
    [[1],[2],[1],[1],[2],[1],[1]]
    [[1,2],[1,1],[2,1],[1]]
    [[1,2,1],[1,2,1],[1]]
    [[1,2,1,1],[2,1,1]]
    [[1,2,1,1,2],[1,1]]
    [[1,2,1,1,2,1],[1]]
    [[1,2,1,1,2,1,1]]
h₃ has possible outputs of
    [[1],[2],[1]]
    [[1,2],[1,1],[2,1]]
    [[1,2,1],[1,2,1],[1]]
hᵐ has possible outputs of
    [1,2,1]
    [1,1,2]
    [1,1,1]
s₂ᶠ has possible outputs of
    [[1,2],[2,1]]
    [[1,1],[1,2]]
    [[1,1],[1,1]]
-ᵐ has possible outputs of
    [-1,1]
    [0,-1]
    [0,0]
= is satisfied by the last of these, so the predicate succeeds.

Le prédicat suivant vers l'extérieur, entre ~b.hℕ₁≜∧.¬{...}∧une sous-séquence a(n-1),a(n-2),...,a(0)et sort la prochaine sous-séquence plus grande a(n),a(n-1),a(n-2),...,a(0).

~b.hℕ₁≜∧.¬{...}∧
~b.                 The input is the result of beheading the output; i.e., the output is
                    the input with some value prepended
  .h                The head of the output
    ℕ₁              is a natural number >= 1
      ≜             Force a choice as to which number (I'm not sure why this is necessary,
                    but the code doesn't work without it)
        ∧           Also,
         .          the output
          ¬{...}    does not satisfy the nested predicate (see above)
                    I.e. there is no k such that a(n),a(n-k),a(n-2k) is an arithmetic sequence
                ∧   Break unification with the output

Enfin, le prédicat principal ;Ė{...}ⁱ⁽↔prend un numéro d'entrée et génère autant de termes de la séquence.

;Ė{...}ⁱ⁽↔
;           Pair the input number with
 Ė          the empty list
  {...}ⁱ⁽   Using the first element of the pair as the iteration count and the second
            element as the initial value, iterate the nested predicate (see above)
         ↔  Reverse, putting the sequence in the proper order

Rubis , 71 octets

->n,*a{a.fill(0,n){|s|([*1..n]-(1..s/2).map{|o|2*a[s-o]-a[s-2*o]})[0]}}

Essayez-le en ligne!

Génère toutes les valeurs interdites, puis prend le complément de ce tableau dans (1..n) et prend la première valeur du résultat. Cela signifie que je suppose que a[n] <= npour tout n, ce qui est facilement prouvé par induction (si les premiers n / 2 termes sont tous inférieurs à n / 2, il ne peut pas y avoir de progression arithmétique conduisant à n).

L'astuce syntaxique ici est également légèrement intéressante: *aest utilisée pour initialiser un tableau d'arguments supplémentaires (qui seraient ignorés si nous en transmettions), puis a.fillmute le tableau d'arguments et le renvoie implicitement.

APL (Dyalog Extended) , 37 octets ^SBCS

Un grand merci à Adám pour son aide dans la rédaction et le golf de cette réponse dans The APL Orchard , un excellent endroit pour apprendre la langue APL. Essayez-le en ligne!

Edit: -6 octets grâce à Adám

⌽{⍵,⍨⊃(⍳1+≢⍵)~-¯2⊥⍵[2×⍀⍥⍳⌊2÷⍨≢⍵]}⍣⎕,⍬

Explication

{⍵,⍨⊃(⍳1+≢⍵)~-¯2⊥⍵[2×⍀⍥⍳⌊2÷⍨≢⍵]}  ⍵ is our right argument, the sequence S

                        ⌊2÷⍨≢⍵    We start by calculating X = ⌊len(S)÷2⌋
                       ⍳          Get a range [1, X]
                   2×⍀⍥           With that we can get S[:X] and S[:X×2:2]
                                  or S up to halfway and every 2nd element of S
             -¯2⊥⍵[           ]   And with that we can get 2*S[:X] - S[:X×2:2]
                                  Which is C=2*B-A of a progression A B C
     (⍳1+≢⍵)~                     We remove these Cs from our possible a(n)s
                                  I use range [1, len(S)+1]
    ⊃                             Get the first result, which is the minimum
 ⍵,⍨                              And then prepend that to S


⌽{...}⍣⎕,⍬

 {...}⍣⎕    We iterate an "input" ⎕ times
        ,⍬  with an empty list ⍬ as the initial S
⌽           and reversing S at the end as we have built it backwards

APL (Dyalog Unicode) , 43 39 38 octets ^SBCS

Voici une solution plus rapide mais moins golfique qui peut calculer ⍺(10000)en quelques secondes.

⌽{⍵,⍨⊃(⍳1+≢⍵)~-⌿⍵[1 2 1∘.×⍳⌊2÷⍨≢⍵]}⍣⎕,⍬

Essayez-le en ligne!

MATLAB, 156 147 octets

J'ai finalement pu jouer un peu au golf:

N=input('');s=[0;0];for n=1:N,x=s(n,~~s(n,:));try,a(n)=find(~ismember(1:max(x)+1,x),1);catch,a(n)=1;end,s(n+1:2*n-1,end+1)=2*a(n)-a(n-1:-1:1);end,a

Ungolfed:

N=input('');                                   % read N from stdin

s=[0;0];
for n=1:N,
    x=s(n,~~s(n,:));                           % x=nonzeros(s(n,:));
    try,
        a(n)=find(~ismember(1:max(x)+1,x),1);  % smallest OK number
    catch,
        a(n)=1;                                % case of blank page for n
    end,

    s(n+1:2*n-1,end+1)=2*a(n)-a(n-1:-1:1);     % determined new forbidden values
end,
a                                              % print ans=...

L'entrée est lue à partir de STDIN et l'impression se fait automatiquement avec des ans=éléments ajoutés. J'espère que cela peut être qualifié de sortie "raisonnable".

Ceci est également une solution à base de tamis: la variable s(i,:)conserve la trace de ces valeurs de séquence qui sont interdits pour a(i). Le try-catchbloc est nécessaire pour traiter le cas d'une smatrice vide (c'est-à-dire plein zéro) : dans ce cas, la valeur la plus basse de 1est déjà autorisée.

Cependant, le besoin de mémoire (ou d'exécution?) Devient assez désordonné ci-dessus N=2000. Voici donc une solution non compétitive et plus efficace:

%pre-alloc
s = zeros([N,fix(N*0.07+20)]); %strict upper bound, needs adjusting later
i = zeros(1,N);

a = 1;
for n = 2:N,
    x = s(n,1:i(n));
    if isempty(x),
        a(n) = 1;
    else
        a(n) = find(~ismember(1:max(x)+1,x),1);
    end,

    j = n+1:min(2*n-1,N);
    i(j) = i(j)+1;
    s(N,max(i(j))) = 0;   %adjust matrix size if necessary
    b = a(n-1:-1:1);
    s(sub2ind([N,size(s,2)+1],j,i(j))) = 2*a(n)-b(1:length(j));
end

Dans cette implémentation, la smatrice contient à nouveau des valeurs interdites, mais de manière bien ordonnée, sans aucun bloc zéro (qui sont présents dans la version concurrente). Le vecteur d'index igarde une trace du nombre de vecteurs interdits dans s. À première vue, les cellules seraient utiles pour garder une trace des informations stockées s, mais elles seraient lentes et nous ne pourrions pas en indexer un tas en même temps.

Une caractéristique désagréable de MATLAB est que, bien que vous puissiez dire M(1,end+1)=3;et développer automatiquement une matrice, vous ne pouvez pas faire de même avec l'indexation linéaire. Cela a du sens (comment MATLAB devrait-il connaître la taille du tableau résultant, dans le cadre duquel il devrait interpréter les indices linéaires?), Mais cela m'a quand même surpris. C'est la raison de la ligne superflue s(N,max(i(j))) = 0;: cela élargira la smatrice pour nous chaque fois que nécessaire. La supposition de la taille de départ N*0.07+20provient d'un ajustement linéaire aux premiers éléments, soit dit en passant.

Afin de tester l'exécution, j'ai également vérifié une version légèrement modifiée du code, où j'ai initialisé la smatrice pour avoir la taille N/2. Pour les premiers 1e5éléments, cela semble être une supposition très généreuse, j'ai donc supprimé l'étape d'extension smentionnée dans le paragraphe précédent. Ensemble, cela implique que le code sera plus rapide, mais aussi moins robuste à très haut niveau N(car je ne sais pas à quoi ressemble la série là-bas).

Voici donc quelques runtimes, comparant

• v1: la version golfée concurrente,
• v2: la version à faible démarrage, infaillible et
• v3: la version généreuse à la taille de départ, qui pourrait échouer pour un grand N.

J'ai mesuré ceux-ci sur R2012b, en prenant le meilleur des 5 exécutions dans une définition de fonction nommée avec tic/toc.

1. N=100:
   • v1: 0.011342 s
   • v2: 0.015218 s
   • v3: 0.015076 s
2. N=500:
   • v1: 0.101647 s
   • v2: 0.085277 s
   • v3: 0.081606 s
3. N=1000:
   • v1: 0.641910 s
   • v2: 0.187911 s
   • v3: 0.183565 s
4. N=2000:
   • v1: 5.010327 s
   • v2: 0.452892 s
   • v3: 0.430547 s
5. N=5000:
   • v1: N / A (n'a pas attendu)
   • v2: 2.021213 s
   • v3: 1.572958 s
6. N=10000:
   • v1: N / A
   • v2: 6.248483 s
   • v3: 5.812838 s

Il semblerait que la v3version soit considérablement, mais pas extrêmement rapide. Je ne sais pas si un élément d'incertitude (pour très grand N) vaut la légère augmentation du temps d'exécution.

Gelée , 24 19 octets

Ceci est ma première réponse Jelly depuis un bon moment. Heureux d'être de retour.

Ceci est un port de ma réponse APL qui est lui-même une adaptation de la plupart des algorithmes utilisés ici. La principale différence est qu'elle est indexée sur 0.

Edit: -5 octets grâce à Jonathan Allan.

Essayez-le en ligne!

Ḋm2ɓṁḤ_
ŻJḟÇṂ;
1Ç¡U

Explication

Ḋm2ɓṁḤ_  First link. Takes our current sequence S as our left argument.

         We are trying to calculate, of an arithmetic progression A B C, 
           the C using the formula, C = 2*B - A
Ḋ        Remove the first element of S.
 m2      Get every element at indices 0, 2, 4, ...
           This is equivalent to getting every second element of S, a list of As.
   ɓ     Starts a dyad with reversed arguments.
           The arguments here are S and As.
    ṁ    This molds S in the shape of As, giving us a list of Bs.
     Ḥ   We double the Bs.
      _  And subtract As from 2 * Bs.

ŻJḟÇṂ;  Second link. Takes S as our left argument.

Ż       Append a 0 to S.
 J      Range [1, len(z)]. This gets range [1, len(S) + 1].
  ḟÇ    Filter out the results of the previous link, our Cs.
    Ṃ   Take the minimum of Cs.
     ;  And concatenate it with the rest of the sequence so far.

1Ç¡U  Third link. Where we feed our input, n.

1     A list with the element 1.
 Ç¡   Run the previous link n times.
   U  Reverse everything at the end.

ES6, 114 octets

n=>[...r=Array(n)].map((x,i,s)=>{for(y=1;x&&x[y];y++);r[i]=y;for(j=i;++j<n;s[j][y+y-r[i+i-j]]=1)s[j]=s[j]||[]}&&r

Renvoie un tableau des n premiers éléments de la séquence, donc les indices sont à 1 de la version non golfée ci-dessous. J'ai utilisé l'approche tamis. Cette version ralentit après environ n = 2000; une version précédente évitait de lire le début du tableau, ce qui signifiait qu'il ne ralentissait pas jusqu'à environ n = 2500. Une ancienne version utilisait le tableau sieve comme une liste de valeurs interdites plutôt qu'un tableau booléen dont les valeurs étaient interdites; cela pourrait atteindre environ n = 5000 sans casser la sueur. Ma version originale a essayé d'utiliser des bitmasks mais cela s'est avéré inutile (et était également beaucoup trop long à 198 octets).

La version pas tout à fait aussi lente non golfée:

function smoke(n) {
    result = [];
    sieve = [];
    for (i = 1; i <= n; i++) {
        value = 1;
        if (sieve[i]) {
            while (sieve[i][value]) {
                value++;
            }
        }
        result[i] = value;
        for (j = 1; j < i && i + j <= n; j++) {
            if (!sieve[i + j]) sieve[i + j] = [];
            sieve[i + j][value + value - result[i - j]] = true;
        }
    }
    return result;
}