tło
Rozważ sekwencję zdefiniowaną w następujący sposób:
- Pierwszy element to 0;
- Drugi element to 4;
- Od trzeciego elementu jego wartość można obliczyć poprzez:
- Przyjęcie zestawu liczb całkowitych od 0 do poprzedniego elementu sekwencji (włącznie lub wykluczenia, to nie ma znaczenia);
- Usunięcie ze zbioru wszelkich liczb całkowitych, które pojawiły się wcześniej w sekwencji;
- Dodanie razem pozostałych elementów zestawu; to jest wartość, którą chcesz.
Co ciekawe, ta sekwencja nie wydaje się jeszcze znajdować w OEIS .
Zadanie
Napisać program lub funkcja, która bierze całkowitą N jako dane wejściowe, i wysyła n ty element sekwencji.
Przypadki testowe
Pierwsze kilka elementów sekwencji to:
- 0
- 4
- 6 (1 + 2 + 3)
- 11 (1 + 2 + 3 + 5)
- 45 (1 + 2 + 3 + 5 + 7 + 8 + 9 + 10)
- 969 (1 + 2 + 3 + 5 + 7… 10 + 12… 44)
- 468930 (1 + 2 + 3 + 5 + 7… 10 + 12… 44 + 46… 968)
Wyjaśnienia
- Twój program powinien teoretycznie być w stanie obsłużyć dowolne n, jeśli działa na wariancie twojego języka, który ma nieskończenie duże liczby całkowite i dostęp do nieograniczonej ilości pamięci. (Języki bez bignum raczej nie będą w stanie wyjść znacznie dalej niż 468930, ale to nie jest usprawiedliwienie dla zakodowania odpowiedzi na sztywno).
- Możesz wybrać indeksowanie w oparciu o 0 lub w oparciu o 1 (np. Od Ciebie zależy, czy n = 1 zwróci pierwszy element, n = 2 drugi element itd. Lub czy n = 0 zwróci pierwszy element , n = 1 drugi element itd.).
- Nie ma wymagań dotyczących używanego algorytmu ani jego wydajności; możesz zaimplementować definicję sekwencji bezpośrednio (nawet jeśli jest ona naprawdę nieefektywna), a także możesz zaimplementować inny algorytm, który prowadzi do takich samych wyników.
Warunek zwycięstwa
To jest golf golfowy , więc wygrywa najkrótszy poprawny program, mierzony w bajtach.