Wprowadzenie

A229037 ma dość intrygującą fabułę (przynajmniej przez kilka pierwszych terminów):

Istnieje przypuszczenie, że rzeczywiście może mieć jakąś właściwość fraktalną.

Jak zbudowana jest ta sekwencja?

Określić a(1) = 1, a(2) = 1Następnie każde n>2znajduje się minimalną liczbą całkowitą dodatnią a(n), że dla każdej sekwencji arytmetycznej 3 termin n,n+k,n+2kindeksów, odpowiadający wartości sekwencji a(n),a(n+k),a(n+2k)jest nie arytmetyczna sekwencji.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą njako dane wejściowe, wypisz pierwsze nwarunki a(1), ... , a(n)tej sekwencji. (Z dowolnym rozsądnym formatowaniem. Możliwe znaki / łańcuchy prowadzące / szkoleniowe są nieistotne.)

Dostępne są fragmenty służące do generowania tej sekwencji, ale myślę, że inne podejścia mogą być bardziej przydatne w golfie / bardziej odpowiednie dla niektórych języków.

Daj nam znać, jak działa Twój program. Jeśli spotkasz się ze szczególnie wydajnym algorytmem, możesz również o tym wspomnieć, ponieważ pozwoliłby on wykreślić więcej terminów sekwencji w krótszym czasie.

Kilka pierwszych przypadków testowych:

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

Więcej przypadków testowych:

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

Wszystkie warunki do n=100000są dostępne tutaj: https://oeis.org/A229037/b229037.txt

Dzięki @ MartinBüttner za pomoc i zachętę.

Python 2, 95 bajtów

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

Główną sztuczką jest generowanie liczb, których nowa wartość musi unikać. Trzymając do tej pory odwróconą sekwencję l, przyjrzyjmy się, które elementy mogą tworzyć trzyterminowy postęp arytmetyczny z wartością, którą zamierzamy dodać.

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

Pozostałe liczby to sparowani członkowie li co drugi element l, więc zip(l,l[1::2]). Jeśli ta para jest (b,c)wtedy arytmetycznym (a,b,c)zdarza a=2*b-c. Po wygenerowaniu zestawu auników kod pobiera minimum dopełnienia, drukuje go i dołącza do listy. (W rzeczywistości obliczenia są wykonywane przy liczbach zmniejszonych o 1 i wydrukowanych o 1 wyżej, aby range(n)służyły jako wszechświat kandydatów.)

Mathematica, 95 bajtów

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]]&

Z pewnością nie jest to najbardziej golfowe podejście, ale w rzeczywistości jest to dość wydajne, w porównaniu do algorytmów, które wypróbowałem ze strony OEIS.

W przeciwieństwie do sprawdzania wszystkich niedozwolonych wartości dla każdego s (n), kiedy tam dotrzemy, używam podejścia opartego na sicie. Kiedy znajdziemy nową wartość s (n) , natychmiast sprawdzamy, które wartości to zabrania dla m> n . Następnie rozwiązujemy s (n + 1) , szukając pierwszej wartości, która nie była zabroniona.

Można to uczynić jeszcze bardziej wydajnym, zmieniając warunek --i>0na 2n-#<=--i>0. W takim przypadku unikamy sprawdzania niedozwolonych wartości dla n większych niż dane wejściowe.

Aby uzyskać nieco bardziej czytelną wersję, zacząłem od tego kodu, który przechowuje wyniki aż do maxfunkcji f, a następnie przełożyłem ją do powyższej funkcji czystego wiersza:

 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 bajtów

Prawdopodobnie można grać w golfa więcej, ale wciąż jest to przyzwoita pierwsza próba:

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

Nie golfowany:

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

Jest to prosta implementacja, która zwraca „0” dla poza zakresem. Następnie dla każdej możliwej wartości sprawdza, czy dla wszystkich k <= n oraz w granicach, [x, a (xk), a (x-2k)] nie jest ciągiem arytmetycznym.

Górna granica złożoności czasu (wykorzystując fakt ze strony OEIS, że 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)!)

Nie jestem pewien, jak dobre jest to ograniczenie, ponieważ obliczenie pierwszych 1k wartości „t” i użycie modelu liniowego w dziennikach wartości dało appx. O (22 ^ n), z wartością p <10 ^ (- 1291), jeśli ma to znaczenie.

Na poziomie implementacji, kompilując z „-O2”, obliczenie pierwszych 20 wartości zajęło ~ 35 minut.

Brachylog , 33 31 bajtów

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

Wypróbuj online!

W razie potrzeby: 2-bajtowy golf był możliwy dzięki funkcji, o którą prosiłem po pracy nad tym wyzwaniem.

Wyjaśnienie

Iteracyjnie generujemy sekwencję jako listę w odwrotnej kolejności, np. [2,2,1,1,2,1,1]I odwracamy ją na końcu.

Jest tu kilka zagnieżdżonych predykatów. Spójrzmy na nie od wewnątrz. Pierwszy ġh₃hᵐs₂ᶠ-ᵐ=, bierze podsekwencję kandydującą a(n),a(n-1),...,a(0)i określa, czy a(n),a(n-k),a(n-2k)dla niektórych jest sekwencją arytmetyczną 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

Na przykład z wejściem [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.

Następny predykat na zewnątrz, ~b.hℕ₁≜∧.¬{...}∧wprowadza podsekwencję a(n-1),a(n-2),...,a(0)i generuje następną większą podsekwencję 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

Wreszcie główny predykat ;Ė{...}ⁱ⁽↔przyjmuje liczbę wejściową i wyprowadza tyle terminów sekwencji.

;Ė{...}ⁱ⁽↔
;           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

Rubinowy , 71 bajtów

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

Wypróbuj online!

Generuje wszystkie zabronione wartości, a następnie pobiera uzupełnienie tej tablicy w (1..n) i przyjmuje pierwszą wartość wyniku. Oznacza to, że zakładam, że a[n] <= ndla wszystkich n, co można łatwo udowodnić za pomocą indukcji (jeśli wszystkie pierwsze n / 2 warunki są mniejsze niż n / 2, wówczas nie może być postęp arytmetyczny prowadzący do n).

Sztuczka składniowa jest tutaj również nieco interesująca: *asłuży do inicjalizacji tablicy dodatkowych argumentów (które zostałyby zignorowane, gdybyśmy ją przekazali), a następnie a.fillmutuje tablicę argumentów i domyślnie zwraca ją.

APL (Dyalog Extended) , 37 bajtów ^SBCS

Ogromne podziękowania dla Adáma za pomoc w pisaniu i grze w golfa w The APL Orchard , doskonałym miejscu do nauki języka APL. Wypróbuj online!

Edycja: -6 bajtów dzięki Adámowi

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

Wyjaśnienie

{⍵,⍨⊃(⍳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 bajtów ^SBCS

Oto szybsze, ale mniej golfowe rozwiązanie, które można obliczyć ⍺(10000)w kilka sekund.

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

Wypróbuj online!

MATLAB, 156 147 bajtów

W końcu zacząłem trochę grać w golfa:

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

Nie golfowany:

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=...

Dane wejściowe są odczytywane ze STDIN, a drukowanie odbywa się automatycznie ans=i dołączane są inne elementy. Mam nadzieję, że kwalifikuje się to jako „rozsądne” wyjście.

To rozwiązanie również oparte na sito Zmienna s(i,:)śledzi tych wartości sekwencji, które są zabronione w a(i). try-catchPotrzebne blok leczenia przypadku pusta (zero), co oznacza pełna smacierz: w tym przypadku najniższa wartość 1jest już dopuszczalne.

Jednak potrzeba pamięci (lub środowisko uruchomieniowe?) Staje się dość nieporządna powyżej N=2000. Oto niekonkurencyjne, bardziej wydajne rozwiązanie:

%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

W tej implementacji smacierz ponownie zawiera niedozwolone wartości, ale w uporządkowany sposób, bez żadnych bloków zerowych (które są obecne w wersji konkurencyjnej). Wektor indeksu iśledzi liczbę zabronionych wektorów w s. Na pierwszy rzut oka komórki byłyby świetne do śledzenia przechowywanych informacji s, ale byłyby one powolne i nie mogliśmy zindeksować wielu z nich jednocześnie.

Jedną z nieprzyjemnych cech MATLAB jest to, że chociaż możesz powiedzieć M(1,end+1)=3;i automatycznie rozwinąć macierz, nie możesz zrobić tego samego z indeksowaniem liniowym. To ma sens (skąd MATLAB powinien znać wynikowy rozmiar tablicy, w ramach którego powinien interpretować wskaźniki liniowe?), Ale nadal mnie zaskoczyło. To jest powód zbędnej linii s(N,max(i(j))) = 0;: to rozszerzy snam macierz, gdy zajdzie taka potrzeba. Nawiasem N*0.07+20mówiąc, domyślna wielkość początkowa pochodzi z liniowego dopasowania do kilku pierwszych elementów.

Aby przetestować środowisko wykonawcze, sprawdziłem również nieco zmodyfikowaną wersję kodu, w której zainicjowałem smacierz, aby miała rozmiar N/2. W przypadku pierwszych 1e5elementów wydaje się to bardzo hojne, więc usunąłem krok ekspansji swspomniany w poprzednim akapicie. Łącznie oznacza to, że kod będzie szybszy, ale także mniej odporny na bardzo wysokim poziomie N(ponieważ nie wiem, jak wygląda tam seria).

Oto kilka porównawczych środowisk uruchomieniowych

• v1: konkurencyjna wersja gry w golfa,
• v2: wersja dla początkujących, odporna na błędy i
• v3: hojny-początkowy rozmiar, może się nie powieść w przypadku dużych N.

Zmierzyłem je na R2012b, biorąc najlepszy z 5 przebiegów wewnątrz definicji funkcji o nazwie 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: nie dotyczy (nie czekałem)
   • v2: 2.021213 s
   • v3: 1.572958 s
6. N=10000:
   • v1: nie dotyczy
   • v2: 6.248483 s
   • v3: 5.812838 s

Wydaje się, że v3wersja jest znacznie, ale nie przytłaczająco szybsza. Nie wiem, czy element niepewności (dla bardzo dużych N) jest wart niewielkiego wzrostu czasu działania.

Galaretka , 24 19 bajtów

To moja pierwsza odpowiedź na żelki od dłuższego czasu. Cieszę się że wróciłem.

Jest to port mojej odpowiedzi APL, która sama w sobie jest adaptacją wielu używanych tutaj algorytmów. Główną różnicą jest to, że jest to indeksowanie 0.

Edycja: -5 bajtów dzięki Jonathanowi Allanowi.

Wypróbuj online!

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

Wyjaśnienie

Ḋ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 bajtów

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

Zwraca tablicę pierwszych n elementów sekwencji, więc indeksy są o 1 mniejsze od wersji nie golfowej poniżej. Użyłem sita. Ta wersja spowalnia po około n = 2000; poprzednia wersja unikała odczytywania początku tablicy, co oznaczało, że nie zwolniła aż do około n = 2500. Starsza wersja używała tablicy sit jako listy zabronionych wartości, a nie tablicy boolowskiej, której wartości były zabronione; to może osiągnąć około n = 5000 bez zerwania potu. Moja oryginalna wersja próbowała używać masek bitowych, ale okazało się to nieprzydatne (i było też zdecydowanie za długie na 198 bajtów).

Niezupełnie wolna wersja bez golfa:

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;
}