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) = 1
Następnie każde n>2
znajduje się minimalną liczbą całkowitą dodatnią a(n)
, że dla każdej sekwencji arytmetycznej 3 termin n,n+k,n+2k
indeksó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ą n
jako dane wejściowe, wypisz pierwsze n
warunki 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=100000
są dostępne tutaj: https://oeis.org/A229037/b229037.txt
Dzięki @ MartinBüttner za pomoc i zachętę.
Odpowiedzi:
Python 2, 95 bajtów
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ć.Pozostałe liczby to sparowani członkowie
l
i co drugi elementl
, więczip(l,l[1::2])
. Jeśli ta para jest(b,c)
wtedy arytmetycznym(a,b,c)
zdarzaa=2*b-c
. Po wygenerowaniu zestawua
unikó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, abyrange(n)
służyły jako wszechświat kandydatów.)źródło
Mathematica, 95 bajtów
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>0
na2n-#<=--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
max
funkcjif
, a następnie przełożyłem ją do powyższej funkcji czystego wiersza:źródło
Haskell,
90,89,84, 83 bajtówPrawdopodobnie można grać w golfa więcej, ale wciąż jest to przyzwoita
pierwszapróba:Nie golfowany:
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:
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.
źródło
Brachylog ,
3331 bajtówWypró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, czya(n),a(n-k),a(n-2k)
dla niektórych jest sekwencją arytmetycznąk
.Na przykład z wejściem
[1,2,1,1,2,1,1]
: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)
.Wreszcie główny predykat
;Ė{...}ⁱ⁽↔
przyjmuje liczbę wejściową i wyprowadza tyle terminów sekwencji.źródło
Rubinowy , 71 bajtów
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] <= n
dla 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:
*a
służy do inicjalizacji tablicy dodatkowych argumentów (które zostałyby zignorowane, gdybyśmy ją przekazali), a następniea.fill
mutuje tablicę argumentów i domyślnie zwraca ją.źródło
a[s-o]
ia[s-2*o]
można użyća[s-=1]
ia[s-o]
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
Wyjaśnienie
APL (Dyalog Unicode) ,
433938 bajtów SBCSOto szybsze, ale mniej golfowe rozwiązanie, które można obliczyć
⍺(10000)
w kilka sekund.Wypróbuj online!
źródło
MATLAB,
156147 bajtówW końcu zacząłem trochę grać w golfa:
Nie golfowany:
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 wa(i)
.try-catch
Potrzebne blok leczenia przypadku pusta (zero), co oznacza pełnas
macierz: w tym przypadku najniższa wartość1
jest już dopuszczalne.Jednak potrzeba pamięci (lub środowisko uruchomieniowe?) Staje się dość nieporządna powyżej
N=2000
. Oto niekonkurencyjne, bardziej wydajne rozwiązanie:W tej implementacji
s
macierz ponownie zawiera niedozwolone wartości, ale w uporządkowany sposób, bez żadnych bloków zerowych (które są obecne w wersji konkurencyjnej). Wektor indeksui
śledzi liczbę zabronionych wektorów ws
. Na pierwszy rzut oka komórki byłyby świetne do śledzenia przechowywanych informacjis
, 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 liniis(N,max(i(j))) = 0;
: to rozszerzys
nam macierz, gdy zajdzie taka potrzeba. NawiasemN*0.07+20
mó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
s
macierz, aby miała rozmiarN/2
. W przypadku pierwszych1e5
elementów wydaje się to bardzo hojne, więc usunąłem krok ekspansjis
wspomniany w poprzednim akapicie. Łącznie oznacza to, że kod będzie szybszy, ale także mniej odporny na bardzo wysokim poziomieN
(ponieważ nie wiem, jak wygląda tam seria).Oto kilka porównawczych środowisk uruchomieniowych
Zmierzyłem je na R2012b, biorąc najlepszy z 5 przebiegów wewnątrz definicji funkcji o nazwie
tic/toc
.N=100
:0.011342 s
0.015218 s
0.015076 s
N=500
:0.101647 s
0.085277 s
0.081606 s
N=1000
:0.641910 s
0.187911 s
0.183565 s
N=2000
:5.010327 s
0.452892 s
0.430547 s
N=5000
:2.021213 s
1.572958 s
N=10000
:6.248483 s
5.812838 s
Wydaje się, że
v3
wersja jest znacznie, ale nie przytłaczająco szybsza. Nie wiem, czy element niepewności (dla bardzo dużychN
) jest wart niewielkiego wzrostu czasu działania.źródło
M=1;M(end+1)=2;
działa idealnie dla mnie?M=rand(2); M(end+1)=2
zamiast tego :)Galaretka ,
2419 bajtówTo 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!
Wyjaśnienie
źródło
ḟ
zrobi równie dobrze, jakœ-
uratowanie bajtu“”
go1
wypisaniem galaretki reprezentacji listy z pełnego programu, oszczędzając jeszcze jeden.Œœị@2
można grać w golfa, abyḊm2
zaoszczędzić dwa.L‘R
można grać w golfa, aby goŻJ
uratować.ES6, 114 bajtów
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:
źródło