Wprowadzenie (może zostać zignorowane)
Umieszczenie wszystkich liczb dodatnich w regularnej kolejności (1, 2, 3, ...) jest trochę nudne, prawda? Oto szereg wyzwań związanych z permutacjami (przetasowaniami) wszystkich liczb dodatnich. To czwarte wyzwanie w tej serii (linki do pierwszego , drugiego i trzeciego wyzwania).
W tym wyzwaniu zbadamy nie jedną permutację liczb naturalnych, ale cały świat permutacji!
W 2000 roku Clark Kimberling stanowiły problemu w 26 -tego wydania Crux Mathematicorum , czasopiśmie naukowym matematyki opublikowanych przez Canadian Towarzystwa Matematycznego. Problem polegał na:
Czy każda dodatnia liczba całkowita występuje dokładnie raz w tej sekwencji?
W 2004 r. Mateusz Kwasnicki przedstawił pozytywny dowód w tym samym czasopiśmie, aw 2008 r. Opublikował bardziej formalny i (w porównaniu z pierwotnym pytaniem) bardziej ogólny dowód. Sformułował sekwencję z parametrami i :
Udowodnił, że dla każdego takiego, że jest nieracjonalne, sekwencja jest permutacją liczb naturalnych. Ponieważ istnieje nieskończona liczba wartości i , dla których jest to prawdą, jest to naprawdę cały świat permutacji liczb naturalnych. Będziemy trzymać się oryginału , a dla tych parametrów sekwencję można znaleźć jako A050000w OEIS. Pierwsze 20 elementów to:
1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, 21, 10, 5, 15
Ponieważ jest to wyzwanie „czystej sekwencji”, zadaniem jest wyprowadzenie dla danego jako danych wejściowych, gdzie to A050000 .
Zadanie
Biorąc pod uwagę liczbę całkowitą , wypisz w formacie liczby całkowitej, gdzie:
Uwaga: tutaj zakłada się indeksowanie 1; możesz użyć indeksowania opartego na 0, więc itd. Podaj to w swojej odpowiedzi, jeśli zdecydujesz się na to.
Przypadki testowe
Input | Output
---------------
1 | 1
5 | 2
20 | 15
50 | 165
78 | 207
123 | 94
1234 | 3537
3000 | 2245
9999 | 4065
29890 | 149853
Zasady
- Dane wejściowe i wyjściowe są liczbami całkowitymi (program powinien co najmniej obsługiwać dane wejściowe i wyjściowe w zakresie od 1 do 32767)
- Niepoprawne dane wejściowe (0, liczby zmiennoprzecinkowe, ciągi, wartości ujemne itp.) Mogą prowadzić do nieprzewidzianych wyników, błędów lub (nie) zdefiniowanego zachowania.
- Obowiązują domyślne reguły we / wy .
- Domyślne luki są zabronione.
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach
Odpowiedzi:
Japt ,
1514 bajtów1-indeksowany.
Spróbuj
źródło
JavaScript (ES6),
55 5150 bajtówZapisano 1 bajt dzięki @EmbodimentofIgnorance
Zapisano 1 bajt dzięki @tsh
Wypróbuj online!
źródło
n=>eval("for(o=[p=2];n--;)o[p=o[q=p>>1]?3*p:q]=p")
Galaretka , 15 bajtów
Pełny program akceptujący liczbę całkowitą
n
(na podstawie 1) ze STDIN, który wypisuje wynik.Wypróbuj online!
W jaki sposób?
źródło
05AB1E ,
1615 bajtówZaoszczędził 1 bajt dzięki Kevinowi Cruijssenowi .
0-indeksowane.
Wypróbuj online!
Wyjaśnienie
Używając
n=1
jako przykładźródło
Perl 6 , 49 bajtów
-2 bajty dzięki nwellnof
Wypróbuj online!
Zwraca element o indeksie 0 w sekwencji. Możesz zmienić to na 1-indeksowane, zmieniając elementy początkowe na
0,1
zamiast1,3
Wyjaśnienie:
źródło
J ,
4740 bajtówWypróbuj online!
bez golfa
Bezpośrednie tłumaczenie definicji na J. Buduje się oddolnie, używając
^:
iteracji od wartości początkowej wymaganej liczby razy.źródło
Java 10,
12099 bajtówWypróbuj online.
Wyjaśnienie:
źródło
Haskell ,
6765 bajtówWypróbuj online!
Wykorzystuje indeksowanie 0.
EDYCJA: zapisano 2 bajty przy użyciu
elem
zamiastnotElem
warunków przełączaniaźródło
Galaretka , 21 bajtów
Wypróbuj online!
Łącze monadyczne, które ma indeksowane zeron jako argument i zwraca a ( n ) .
źródło
Rubin ,
545248 bajtówWypróbuj online!
źródło
C ++ (gcc) ,
189180 bajtów-9 bajtów do małego golfa
Wypróbuj online!
Oblicza sekwencję do
n
, a następnie zwraca żądany element. Powolny dla większych indeksów.źródło
Python 2 , 66 bajtów
Wypróbuj online!
Używa indeksowania zerowego. Lambda robi niewiele więcej niż rekurencyjne budowanie sekwencji i powrót, gdy tylko zostanie osiągnięty wymagany indeks.
źródło
Stax , 14 bajtów
Uruchom i debuguj
Zero indeksowane.
źródło
Wolfram Language (Mathematica) , 63 bajty
Wypróbuj online!
To jest indeksowane na 0
(w TIO dodałem -1 w każdym przypadku testowym)
źródło
Python 2 , 62 bajty
Wypróbuj online!
Zwraca
True
zaa(0)
. 0-indeksowane.źródło
Python 3 ,
1051031009583 bajtów-2 bajty dzięki Agtoever
-12 bajtów dzięki ArBo
Wypróbuj online!
źródło
while len(s)<=n
i zastąpić i-1
. To powinno ogolić jedną z dwóch postaci.if
zwhile
obiegu, aby umożliwić jedną okładzinę pętliGaia ,
2220 bajtówWypróbuj online!
Indeks oparty na 0.
Kredyt na Kudłaty na podejściu
;D
źródło
Haskell , 55 bajtów
Wypróbuj online!
Golfing user1472751 zręczna metoda generowania listy .
Ta sama długość:
Wypróbuj online!
źródło
Lua , 78 bajtów
Wypróbuj online!
źródło
z
zmiennej i zmianę instrukcji if na trójskładnik