Biorąc pod uwagę dodatnią liczbę całkowitą N , Twoim zadaniem jest zwrócenie liczby kroków wymaganych przez następujący algorytm do osiągnięcia N :

1. Znajdź najmniejszą trójkątny numer T _i taka, że T _i  ≥ N . Zbuduj odpowiednią listę L = [1, 2, ..., i] .

2. Chociaż suma wyrażeń L jest większa niż N , usuń pierwszy wyraz z listy.

3. Jeśli suma warunków L jest teraz mniejsza niż N , zwiększ i i dodaj ją do listy. Przejdź do kroku 2.

Zatrzymujemy się, gdy tylko N zostanie osiągnięte. Tylko pierwszy krok jest wykonywany systematycznie. Kroki 2 i 3 mogą w ogóle nie zostać przetworzone.

Przykłady

Poniżej znajduje się przykład dla N = 11 :

Oczekiwany wynik dla N = 11 wynosi 4 .

Inne przykłady:

• N = 5 - Zaczynamy od T ₃ = 1 + 2 + 3 = 6 , a następnie 2 + 3 = 5 . Oczekiwany wynik: 2 .
• N = 10 - wymagany jest tylko pierwszy krok, ponieważ 10 jest liczbą trójkątną: T ₄ = 1 + 2 + 3 + 4 = 10 . Oczekiwany wynik: 1 .

Pierwsze 100 wartości

Poniżej znajdują się wyniki dla 1 ≤ N ≤ 100 :

  1,  2,  1,  4,  2,  1,  2, 10,  2,  1,  4,  2,  6,  2,  1, 22,  8,  2, 10,  2,
  1,  2, 12,  6,  2,  4,  2,  1, 16,  2, 18, 50,  2,  6,  2,  1, 22,  6,  2,  4,
 26,  2, 28,  2,  1,  8, 30, 16,  2,  6,  4,  2, 36,  2,  1,  2,  4, 12, 40,  2,
 42, 14,  2,108,  2,  1, 46,  2,  6,  4, 50,  2, 52, 18,  2,  4,  2,  1, 56, 12,
  2, 20, 60,  4,  2, 22, 10,  2, 66,  2,  1,  4, 10, 24,  2, 40, 72,  8,  2,  6

Zasady

• Możesz napisać pełny program lub funkcję, która albo wydrukuje, albo zwróci wynik.
• Jesteś zobowiązany do przetwarzania dowolnego N ≤ 65536 w mniej niż jedną minutę na sprzęcie średniej klasy.
• Biorąc pod uwagę wystarczającą ilość czasu, twój program / funkcja powinna teoretycznie działać na każdą wartość N, która jest natywnie obsługiwana przez twój język. Jeśli nie, proszę wyjaśnić dlaczego w swojej odpowiedzi.
• To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach!

Galaretka , 29 31 bajtów

ÆDµ’H+Ṛ%1$ÐḟṂ
>TḢ_@Ç}‘Ḥ
R+\ðċȯç

Łącze monadyczne, które zwraca wynik (N = 65536 zajmuje mniej niż dwie sekundy).

Wypróbuj online!

W jaki sposób?

Dokładne wyjaśnienie algorytmu znajduje się w fantastycznym poście Martina Endera .

ÆDµ’H+Ṛ%1$ÐḟṂ - Link 1, smallest natural number, M, that satisfies the below*, N
              - * N = T(M) - T(i) for some non-negative integer i <= M
ÆD            - divisors of N
  µ           - monadic chain separation, call that d
   ’          - increment d (vectorises)
    H         - halve (vectorises
      Ṛ       - reverse d
     +        - add (vectorises)
          Ðḟ  - filter discard if:
       %1$    -   modulo one is truthy (those which are the result of even divisors)
            Ṃ - minimum

>TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N
>         - T(i) > N
 T        - truthy indexes
  Ḣ       - head (yields the first i for which T(i) > N)
     Ç}   - call last link (1) as a monad converted to a dyad using the right argument
   _@     - subtract with reverse @rguments
       ‘  - increment
        Ḥ - double 

R+\ðċȯç - Main link: N
R       - range -> [1,2,...,N]
 +\     - reduce with addition -> [1,3,6,10,...T(N)]
   ð    - dyadic chain separation, call that t
    ċ   - count occurrences of N in t (1 if N is triangular else 0)
      ç - call last link (2) as a dyad(t, N)
     ȯ  - or

29-bajtowa implementacja pełnego programu, którą stworzyłem opisanego algorytmu, zajmuje 4 min 30 dla N = 65536 na moim laptopie, więc przypuszczam, że się nie liczy.

Ṁ‘ṭµS<³µ¿
ḊµS>³µ¿
0®Ḃ‘©¤ĿÐĿL’

Użycie pętli while dla każdego kroku 3 i ponowne użycie go jako kroku 1 jest równe długości tego, co mogę zrobić przy inicjalizacji listy, ponieważ brak kontroli w kroku 3 oznacza zbudowanie listy, dopóki nic nie pozostanie, a następnie znalezienie pierwszego indeksu wartości:

ḊµS>³µ¿
Ṁ‘ṭ
Ḥ½_.ĊR®Ḃ‘©¤ĿÐĿS€i

Mathematica, 79 bajtów

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&

Wyjaśnienie

Nie mogłem się martwić implementacją algorytmu w wyzwaniu, więc chciałem poszukać skrótu do rozwiązania. Chociaż znalazłem jedną, niestety nie bije ona odpowiedzi Mathematica, która implementuje algorytm. To powiedziawszy, jestem pewien, że to nie jest jeszcze optymalna gra w golfa, i mogą istnieć inne języki, które mogą skorzystać z tego podejścia lub niektórych spostrzeżeń uzyskanych w tym procesie.

Twierdzę więc, że sekwencja, którą powinniśmy obliczyć to:

f (n) = 2 * ( A212652 (n) - A002024 (n)) + 1 + A023532 (n-1)

Alternatywnie jest to f (n) = 1, jeśli n jest liczbą trójkątną, a f (n) = 2 * ( A212652 (n) - A002024 (n) + 1) w przeciwnym razie.

W pierwszym wyrażeniu A023532 po prostu koduje te dwa różne przypadki. Pozostałe dwie sekwencje (plus 1) to różnica między największą liczbą całkowitą k w najdłuższym rozkładzie n na kolejne liczby całkowite (k-i + 1) + (k-i + 2) + ... + k = n i największa liczba całkowita j, tak że 1 + 2 + ... + j <n .

W nieco prostszych słów, oto jak znaleźć odpowiedź na liczbach niż trójkątne: po pierwsze, znaleźć największą liczbę trójkątną T _j , która jest mniejsza niż n . Zatem j jest przedostatnią liczbą całkowitą, która jest dodawana podczas kroku 1 (ponieważ po dodaniu j + 1 przekroczymy n ). Następnie rozłóż n na tak wiele (lub tak małe) kolejnych liczb całkowitych, jak to możliwe i wywołaj maksimum spośród tych liczb k . Wynik to po prostu 2 * (kj) . Intuicyjnie wynika to z tego, że maksimum w rozkładzie rośnie o 1 co drugi krok i zatrzymujemy się, gdy osiągamyk .

Musimy pokazać cztery rzeczy, aby udowodnić, że to działa:

1. f (n) = 1 dla liczb trójkątnych. Jest to trywialna sytuacja, ponieważ pierwszy krok po prostu przechodzi przez wszystkie liczby trójkątne. Jeśli naciśniemy n dokładnie podczas tego procesu, to skończymy i był tylko jeden krok do obliczenia.
2. W przypadku wszystkich innych liczb zawsze kończymy po kroku usuwania, nigdy po kroku wstawiania. Oznacza to, że wszystkie inne f (n) są parzyste.
3. W każdym kroku wstawiania po pierwszym dodajemy tylko jeden numer. To gwarantuje, że dojdziemy do rozkładu, w tym k po parach kj kroków.
4. Ostateczny rozkład n , który otrzymujemy, jest zawsze najdłuższym możliwym rozkładem n na kolejne liczby całkowite, lub innymi słowy, zawsze jest to rozkład n z najniższą wartością maksymalną spośród sumowanych liczb. Innymi słowy, ostatnią liczbą, którą dodajemy do sumy, jest zawsze A212652 (n) .

Pokazaliśmy już, dlaczego (1) jest prawdą. Następnie dowodzimy, że nie możemy zakończyć kroku wstawiania oprócz początkowego (co nie dzieje się w przypadku liczb innych niż trójkątne).

Załóżmy, że zakończyliśmy krok wstawiania, osiągając n po dodaniu wartości p do sumy. Oznacza to, że przed tym krokiem wstawiania wartość wynosiła np ( lub mniej, jeśli dodaliśmy wiele wartości na raz). Ale ten krok wstawiania był poprzedzony krokiem usuwania (ponieważ nie mogliśmy trafić n podczas kroku 1). Ostatnia wartość q, którą usunęliśmy podczas tego etapu usuwania, była z konieczności mniejsza niż p ze względu na sposób działania algorytmu. Ale to oznacza, że ​​zanim usunęliśmy q , mieliśmy n-p + q ( lub mniej ), co jest mniejsze niż n. Ale to sprzeczność, ponieważ musielibyśmy przestać usuwać liczby całkowite, gdy naciśniemy n-p + q zamiast usuwać kolejne q . To potwierdza punkt (2) powyżej. Teraz wiemy, że zawsze kończymy krok usuwania i dlatego wszystkie liczby inne niż trójkątne mają nawet dane wyjściowe.

Następnie udowodnimy (3), że każdy krok wstawiania może wstawić tylko jedną wartość. Jest to zasadniczo następstwo (2). Wykazaliśmy, że po dodaniu jednej wartości nie możemy trafić n dokładnie, a ponieważ w dowodzie zastosowano nierówność, nie możemy również skończyć poniżej n (ponieważ od tego czasu n-p + q nadal będzie mniejsze niż n i nie powinniśmy byli usuwać tak wiele wartości w pierwszej kolejności). Tak więc za każdym razem, gdy dodamy jedną wartość, gwarantujemy, że przekroczysz n, ponieważ spadliśmy poniżej n , usuwając mniejszą wartość. Wiemy zatem, że górna granica sumy rośnie o 1 co drugi krok. Znamy wartość początkową tego górnego końca (jest to najmniejszy m taki, żeT _m > n ). Teraz musimy tylko ustalić ten górny koniec, gdy osiągniemy ostateczną sumę. Wtedy liczba kroków jest po prostu dwukrotnością różnicy (plus 1).

Aby to zrobić, dowodzimy (4), że ostateczna suma jest zawsze rozkładem n na jak najwięcej liczb całkowitych, jak to możliwe, lub rozkładem, w którym maksimum w tym rozkładzie jest minimalne (tj. Jest to najwcześniejszy możliwy rozkład). Znowu zrobimy to przez sprzeczność (sformułowania w tej części mogą być nieco bardziej rygorystyczne, ale spędziłem już na tym zbyt dużo czasu ...).

Powiedzmy, że najwcześniejszy / najdłuższy możliwy rozkład n to jakieś a + (a + 1) + ... (b-1) + b , a ≤ b , i powiedzmy, że algorytm go pomija. Oznacza to, że w momencie dodania b , a nie może już być częścią sumy. Gdyby a było częścią sumy s , wtedy mielibyśmy n ≤ s w tym momencie. Tak więc albo suma zawiera tylko wartości od a do b , która jest równa n, i zatrzymujemy się (stąd nie pominęliśmy tego rozkładu), lub jest co najmniej jedna wartość mniejsza niż a w sumie, wygraj który przypadek n <si ta wartość będzie usuwana, dopóki nie osiągniemy dokładnej sumy (ponownie, rozkład nie został pominięty). Tak musielibyśmy pozbyć przed dodaniem b . Ale to oznacza, że ​​musielibyśmy dojść do sytuacji, w której a jest najmniejszym składnikiem sumy, a największy nie jest jeszcze b . Jednak w tym momencie nie możemy usunąć a , ponieważ suma jest wyraźnie mniejsza niż n (ponieważ brakuje b ), więc musimy najpierw dodać wartości, aż dodamy b i naciśniemy dokładnie n . Dowodzi to (4).

Łącząc te rzeczy razem: wiemy, że pierwsza para kroków daje nam maksymalną wartość A002024 (n) . Wiemy, że maksymalna wartość końcowego rozkładu wynosi A212652 (n) . I wiemy, że to maksimum zwiększa się raz na każdą parę kroków. Zatem końcowe wyrażenie to 2 * ( A212652 (n) - A002024 (n) + 1) . Ta formuła prawie działa na liczbach trójkątnych, z tym wyjątkiem, że dla tych potrzebujemy tylko 1 krok zamiast 2, dlatego korygujemy wynik za pomocą funkcji wskaźnika liczb trójkątnych (lub odwrotnie, w zależności od tego, co jest wygodniejsze).

Wreszcie, jeśli chodzi o wdrożenie. W poprzedniej sekwencji używam wzoru MIN (nieparzysty d | n; n / d + (d-1) / 2) z OEIS. Okazuje się, że zapisujemy kilka bajtów, jeśli weźmiemy współczynnik 2 do tego wyrażenia, aby uzyskać MIN (nieparzyste d | n; 2n / d + d-1) , ponieważ to -1 następnie anuluje z +1 w mojej pierwszej wersji z f (n), który bezpośrednio koduje dwa przypadki dla liczb trójkątnych i nie trójkątnych. W kodzie jest to:

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]

W przypadku drugiej sekwencji ( 1, 2, 2, 3, 3, 3, ...) możemy użyć prostej formy zamkniętej:

⌊(2#)^.5+.5⌋

I na koniec funkcja odwrotnego wskaźnika liczb trójkątnych wynosi 0, gdy 8n + 1 jest idealnym kwadratem. Można to wyrazić w Mathematica jako

⌈Sqrt[8#+1]~Mod~1⌉

Istnieje wiele sposobów wyrażenia tych dwóch ostatnich sekwencji i przesunięcia między nimi stałego przesunięcia, więc jestem pewien, że nie jest to jeszcze optymalna implementacja, ale mam nadzieję, że może to dać innym punkt wyjścia do spojrzenia na nowe podejścia w ich własne języki.

Ponieważ zadałem sobie tyle trudu, oto wykres sekwencji do n = 1000 (mogłem również obliczyć 100k w kilka sekund, ale tak naprawdę nie pokazuje żadnych dodatkowych spostrzeżeń):

Interesujące może być przeanalizowanie wariantów tych bardzo prostych linii, ale zostawię to komuś innemu ...

Mathematica, 72 bajty

(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&

Czysta funkcja przyjmująca argument liczby całkowitej.

Jak to działa

For[ ... ]

ForPętli.

l=u=c=k=0

Inicjalizacja; ustaw l(dolny), u(górny), c(licznik) i k(suma) na 0.

k!=#

Stan; powtórzenie podczas gdy knie jest równe wejściowi.

c++

Przyrost; zwiększyć licznik c.

If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]

Ciało

If[#>k, ... ]

Jeśli dane wejściowe są większe niż k:

While[#>k,k+=++u]

Podczas gdy wartość wejściowa jest większa niż k, przyrost ui przyrost ko u.

Jeśli dane wejściowe nie są większe niż k:

While[#<k,k-=l++]

Choć wejście jest mniejsza niż k, ubytek kprzez li przyrostu l.

( ... ;c)

Wróć cpo pętli.

Python 2 , 104 bajty

N=input();i=s=0;l=()
while N!=sum(l):exec'while sum(l)'+['<N:i+=1;l+=i,','>N:l=l[1:]'][s%2];s+=1
print s

Wypróbuj online!

Na przemian między dodawaniem terminów na końcu listy a usuwaniem terminów od początku.

Haskell , 70 63 68 64 bajtów

EDYTOWAĆ:

• -7 bajtów: Pozbyłem się spacji, dwóch znaków i niektórych nawiasów, negując sens a. Naprawiono błędy w wyjaśnieniach jeden po drugim.
• +5 bajtów: Argh, że całkowicie brakowało 65536 wymogiem, a okazuje się, (1) potęgi 2 są szczególnie drogie, bo dostaje tylko trafienie, gdy pojawi się na samej liczby (2) tak jest podsumowującej długie pasma (które owijają się wokół zero) cały czas. Zastąpiłem sumę wzorem matematycznym.
• -4 bajty: Dostosowane ai bliniowo, aby uzyskać warunki w formule sumowania w celu anulowania.

1#1 to anonimowa funkcja przyjmująca i zwracająca liczbę całkowitą.

Użyj jako (1#1) 100.

1#1
(a#b)n|s<-a*a-b*b=sum$[a#(b+2)$n|s>8*n]++[(b#a)(-n)+1|s<8*n]

Wypróbuj online!

Jak to działa

• (a#b)nreprezentuje bieżący krok obliczeń. a, bsą liczbami w 1, 3, 5, .., a nmogą być dodatnie lub ujemne w zależności od kroku.
  • W kroku 1 lub 3 reprezentuje listę [(a+1)/2,(a+3)/2..(b-1)/2]i numer celu -n.
  • W kroku 2 reprezentuje listę [(b+1)/2,(b+3)/2..(a-1)/2]i numer celu n.
• Dziwna zgodność między a, blistami i między nimi ma na celu dokonanie podsumowania za pomocą krótkiego wyrażenia s=a*a-b*b.
  • W krokach 1 i 3 jest to to samo co s= -8*sum[(a+1)/2..(b-1)/2].
  • W kroku 2 jest to to samo co s=8*sum[(b+1)/2..(a-1)/2].
• Rozgałęzianie odbywa się poprzez zrozumienie listy, która produkuje elementy tylko w jednym przypadku, i zsumowanie wyników.
  • Jeśli s>8*n, to bjest zwiększane o 2 przed powtórzeniem.
    • W kroku 1 i 3 powiększa się lista, podczas gdy w kroku 2 zmniejsza się.
  • Jeśli s<8*n, to rekurencja zmienia krok, zamieniając ai b, i negując n, a do wyniku dodaje się 1.
  • Jeśli s==8*n, to żadne z dwóch zestawień listy nie zawiera żadnych elementów, więc suma jest 0.
• (1#1) nreprezentuje obojętny „etap 2” przed rozpoczęciem, który natychmiast zmienia się na krok 1, od którego budowana jest lista [1..0]=[].

PHP> = 7.0, 74 bajtów

while($i=$r<=>$argn)for($s++;($r<=>$argn)==$i;)$r+=$i+1?-++$y:++$x;echo$s;

użyj operatora statku kosmicznego

Wypróbuj online!

Rozszerzony

while($i=$r<=>$argn) # if input is not equal sum of array
  for($s++;  # raise count steps
  ($r<=>$argn)==$i;)
  # so long as value compare to input has not change to lower/higher to higher/lower or equal  
    $r+=$i+1
      ?-++$y # if $i was higher remove the first integer
      :++$x;} # if $i was lower add the next highest integer     
echo$s; # Output steps

C, 94 91 bajtów

Wypróbuj online

c;s;m;M;f(n){while(s-n){while(s<n)s+=++M;c++;if(s==n)break;while(s>n)s-=++m;c++;}return c;}

JavaScript (ES6), 82 bajty

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

Test Snippet

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

<input type="number" oninput="o.textContent=D(this.value)"></input>
<pre id='o'></pre>

dc , 61 bajtów

dsN[ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx]dsFxz2-

Wypróbuj online!

Wyjaśnienie

Główne makro rekurencyjne:

ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx
   9k4*d2*1+dv-0k2/-                              # Compute triangular root
                    d1+*2/                        # Compute triangular number
  d                       -d[q]s.0=.              # Check if sum is exact
 d                                  -lN-          # Compute S-N or S+N
                                        0lN-sN    # Update N := -N
d                                             lFx # Leave the trail and recurse

To makro:

1. Znajduje minimalną liczbę trójkątną, która przekracza bieżącą liczbę na stosie (używając zmodyfikowanej formuły trójkątnego pierwiastka ).
2. Sprawdza, czy suma trójkątna Sdokładnie reprezentuje bieżącą liczbę. Wychodzi, jeśli tak jest.
3. Przechodzi do kroku 1 z S+N(przybliżeniem) lub S-N(przybliżeniem), wybór zmienia się między iteracjami.

Po wyjściu ślad pozostawiony na stosie informuje program główny, ile iteracji potrzebował.

Python 3, 150 138 bajtów

n=int(input())
S=sum
l=[1]
i=s=1
while S(l)<n:i+=1;l+=[i]
while S(l)!=n:
 while S(l)>n:l.pop(0)
 s+=1
 if S(l)<n:i+=1;l+=[i];s+=1
print(s)

Dziennik zmian:

• Zmieniono dołączenie na + =, usunięto inne (dzięki musicman523, Loovjo; -12 bajtów)

Partia, 126 bajtów

@echo off
set/an=s=l=u=0
:l
if %s% lss %1 set/as+=u+=1,n+=!!l&goto l
if %s% gtr %1 set/as-=l+=1&goto l
cmd/cset/an+n+2-!l

Objaśnienie: lwynosi zero, jeśli krok 2 nigdy nie został wykonany. Pozwala to nna śledzenie liczby iteracji kroku 3. Ponieważ algorytm nigdy nie zatrzymuje się na kroku 3, musi zatem wykonać krok 1 raz, a krok 2 n+1razy, łącznie dla wszystkich n+n+2kroków. Jeśli jednak parametr jest liczbą trójkątną, krok 2 nigdy się nie wykonuje, więc musimy odjąć jeden krok.

Python 2, 86 81 bajtów

n=input()
l=u=i=s=0
while n:k=n>0;i+=k^s;s=k;l+=k;n-=l*k;u+=k^1;n+=u*-~-k
print i

Wypróbuj online!

Oblicza przypadek testowy 65536 w 0.183sTIO.

Ta rekurencyjna wersja o wielkości 84 bajtów nie jest w stanie obliczyć wszystkich wartości do 65536:

def f(n,l=[0],m=1):k=n>sum(l);return n==sum(l)or f(n,[l[1:],l+[l[-1]+1]][k],k)+(m^k)

Wypróbuj online!

Mathematica, 92 bajty

(For[q=a=b=0;t={},t~AppendTo~q;q!=#,If[q<#,q+=++b,q-=++a]];Length@Split@Sign@Differences@t)&

Czysta funkcja przyjmująca argument liczby całkowitej i zwracająca liczbę całkowitą.

Zmienne ai boznaczają (stale zmieniające się) liczby początkowe i końcowe w rozpatrywanej sumie, natomiast qoznaczają bieżącą sumę (liczb od a+1do b); tśledzi wszystkie qnapotkane dotąd wartości. Po zainicjowaniu tych zmiennych Forpętla wykonuje wykonywanie If[q<#,q+=++b,q-=++a], które albo dodaje nową liczbę na końcu, albo odejmuje liczbę z przodu, jak dyktuje specyfikacja, aż qzrówna się z wejściem.

Teraz musimy tylko wyodrębnić liczbę kroków t, listę qwartości napotkanych po drodze. Na przykład, gdy wejście jest 11, Forpętla kończy się z twyrównaniem {0,1,3,6,10,15,14,12,9,15,11}. Najlepszym sposobem, jaki obliczyłem na podstawie liczby kroków, jest policzenie, ile razy różnice przechodzą od przejścia w górę w dół; tak robi pełne polecenie Length@Split@Sign@Differences@t, ale podejrzewam, że można to poprawić.

C (tcc), 71 bajtów (61 + 10)

Argumenty wiersza polecenia (w tym spacja):

-Dw=while

Źródło:

c,m,M,s;f(n){w(++c,s-n){w(c&s<n)s+=++M;w(~c&s>n)s-=m++;}--c;}

Jak to działa:

cliczy liczbę kroków. mi Mprzechowuj minimum i maksimum zakresu, ssumę. Początkowo wszystkie mają zero.

Ciągle cjest zwiększany i sporównywany n. O ile są one nierówne:

• Jeśli cjest nieparzyste, to tak długo, jak s<ndodać liczbę całkowitą na końcu zakresu: zwiększyć Mo jeden i sprzez M.

• Jeśli cjest parzyste, to s>nusuń liczbę całkowitą z początku zakresu: pomniejsz so mi zwiększ mo jeden.

Kiedy pętla wychodzi, czostała zwiększona zbyt wiele razy. Zmniejszenie powoduje uzyskanie poprawnego wyniku i zdarza się, że jest obliczany w odpowiednim rejestrze, aby działał jako wartość zwracana.

Zabawnie się zdarza, że ​​używa dokładnie tych samych nazw zmiennych, co odpowiedź C. w języku Khaled.K . Nie są kopiowane.

Perl 6 , 114 bajtów

{((0,0,1),->(\a,\b,\c){b,(a..*).first(->\d{(d,b).minmax.sum*c>=$_*c}),-c}...->(\a,\b,\c){(a,b).minmax.sum==$_})-1}

(zainspirowany wcześniejszą implementacją Haskell )

Wypróbuj
Działa z wejściem 65536 w mniej niż 45 sekund na moim komputerze, ale nie udało mi się uruchomić go w czasie krótszym niż 60 sekund z TIO.run.
Mam Rakudo v2017.04 +, gdzie ma v2017.01 .
Rakudo / NQP / MoarVM dostaje optymalizacje prawie codziennie, więc od czasu do czasu może być ich dowolna liczba, które są potrzebne, aby uzyskać to na czas.

Rozszerzony

{
  (

    # generate a sequence

    (0,0,1),           # initial value 

    -> (\a,\b,\c) {
      b,               # swap the first two values

      (a..*)
      .first(          # find the first number that brings us to or past the input

        -> \d {
          (d,b).minmax # get a Range object regardless of which is larger
          .sum * c     # sum it, and negate it every other time

          >=           # is it equal to or greater than

          $_ * c       # negate the original input every other time
        }

      ),

      -c               # invert for next round
    }

    ...                # keep doing that until

    -> (\a,\b,\c) {
     (a,b).minmax.sum == $_ # it finally reaches the input
    }

  ) - 1 # count the number of elements in the sequence
        # and subtract one for the initializer
}

Zauważ, że Rakudo ma optymalizację, Range.sumaby nie musiała iterować wszystkich wartości.