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:
- 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.
- W przypadku wszystkich innych liczb zawsze kończymy po kroku usuwania, nigdy po kroku wstawiania. Oznacza to, że wszystkie inne f (n) są parzyste.
- 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.
- 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 ...
