Definicja
- Dwie liczby całkowite są chronione prawem autorskim, jeśli nie dzielą żadnych dodatnich wspólnych dzielników innych niż
1
. a(1) = 1
a(2) = 2
a(n)
jest najmniejszą liczbą całkowitą dodatnią, która jest względnie pierwsze doa(n-1)
aa(n-2)
i jeszcze nie pojawił się na całkowitąn >= 3
.
Zadanie
- Podana dodatnia liczba całkowita
n
, wyjście / wydruka(n)
.
Przykład
a(11) = 6
ponieważ6
jest chroniony prawem autorskim wobec dwóch ostatnich poprzedników (mianowicie11
i13
) i6
nie pojawił się wcześniej.
Notatki
- Zauważ, że sekwencja nie rośnie, co oznacza, że element może być mniejszy niż jego poprzednik.
Okular
- Państwo musi użyć 1-indeksowane.
Przypadki testowe
n a(n)
1 1
2 2
3 3
4 5
5 4
6 7
7 9
8 8
9 11
10 13
11 6
12 17
13 19
14 10
15 21
16 23
17 16
18 15
19 29
20 14
100 139
1000 1355
10000 13387
100000 133361
Punktacja
- Ponieważ coprime oznacza, że dwie liczby dzielą tylko jeden dzielnik (
1
) i1
jest małą liczbą, twój kod powinien być tak mały, jak to możliwe pod względem liczby bajtów.
Bibliografia
- OEIS A084937
code-golf
sequence
number-theory
Leaky Nun
źródło
źródło
Odpowiedzi:
Python 3.5,
160141126124121109 bajtówJest to prosta implementacja definicji sekwencji. Sugestie dotyczące gry w golfa mile widziane.
Edycja: -17 bajtów dzięki Dziurawej Zakonnicy. -9 bajtów dzięki Peterowi Taylorowi. -6 bajtów dzięki Sp3000 i przejściu na Python 3.5.
Ungolfing:
źródło
import math
wtedyg=math.gcd
powinien być krótszy niż definiowanie własnychg
. Dla zanim 3,5, można to zrobićfrom fractions import*
zagcd
.c=3
wewnątrz pętli, musisz to zrobić tylko raz. Według moich obliczeń oszczędzasz 3 znaki.r=[c]+r
zamiast+=
, ale trzy ujemne wskaźniki stają się dodatnie. I jeszcze jedna oszczędność 2 znaków od przepisywania jako lambda, chociaż jest to dość drastyczna zmiana:from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1)
i nie ma potrzeby,print
ponieważ nie jest to już pełny program.MATL ,
2827 bajtówKod jest wolny, ale daje poprawny wynik.
Wypróbuj online! Lub sprawdź pierwsze dziesięć przypadków .
Mała modyfikacja kodu tworzy wykres sekwencji:
Zobacz go jako grafikę ASCII lub z graficznym wyjściem w kompilatorze offline:
Wyjaśnienie
źródło
C, 185 bajtów
źródło
Faktycznie ,
383735333130 bajtówJest to prosta implementacja definicji funkcji. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
Edycja: -3 bajty dzięki Dziurawej Zakonnicy.
Ungolfing:
źródło
Haskell,
8173 bajtówPrzykład użycia:
((0:1:c[2,1])!!) 12
->17
.Zbuduj listę wszystkich
a(n)
, zaczynając od,0
aby naprawić indeks oparty na 1,1
a następniec[2,1]
.c
bierze na czele listę argumentów,l
po której następuje rekurencyjne wywołanie, a następnie dodany jest następny numer, który pasuje (co-prime, nie widziałem wcześniej)l
. Wybierzn
element th z tej listy.źródło
R, 141 bajtów
bez golfa
źródło
Mathematica,
9790 bajtówNa podstawie
moich przypuszczeń, żea(n) < 2n
dla wszystkichn
.Aby uzyskać szybszy przebieg, dodaj
a@n=
po oryginale,:=
aby funkcja nie musiała ponownie obliczać poprzednich wartości .Zaoszczędź 7 bajtów dzięki Sherlock9 (jeśli
gcd(a,b)=1
togcd(ab,m) = gcd(a,m)*gcd(b,m)
)źródło
ABS(a(n)-n) < n
”n
.Pyth, 23 bajty
Zestaw testowy
Dość prosta implementacja, ale z kilkoma fajnymi sztuczkami golfowymi.
źródło