Definicja

• a(1) = 1
• a(2) = 2
• a(n)jest najmniejszą liczbą, k>a(n-1)która pozwala uniknąć 3-termicznej progresji arytmetycznej w a(1), a(2), ..., a(n-1), k.
• Innymi słowy, a(n)jest najmniejszą liczbą k>a(n-1), która nie istnieje x, ygdzie 0<x<y<ni a(y)-a(x) = k-a(y).

Opracowany przykład

Dla n=5:

Mamy a(1), a(2), a(3), a(4) = 1, 2, 4, 5

Jeśli a(5)=6, to 2, 4, 6utwórz postęp arytmetyczny.

Jeśli a(5)=7, to 1, 4, 7utwórz postęp arytmetyczny.

Jeśli a(5)=8, to 2, 5, 8utwórz postęp arytmetyczny.

Jeśli a(5)=9, to 1, 5, 9utwórz postęp arytmetyczny.

Jeśli a(5)=10nie można znaleźć postępu arytmetycznego.

W związku z tym a(5)=10.

Zadanie

Biorąc pod uwagę nwydajność a(n).

Okular

• n będzie dodatnią liczbą całkowitą.
• Można użyć 0 indeksowane zamiast 1-indeksowane, w tym przypadku nmoże być 0. Podaj to w swojej odpowiedzi, jeśli używasz 0-indeksowanych.

Punktacja

Ponieważ staramy się unikać 3-termicznej progresji arytmetycznej, a 3 jest małą liczbą, twój kod powinien być tak mały (tj. Krótki), jak to możliwe, pod względem liczby bajtów.

Przypadki testowe

Przypadki testowe mają indeks 1. Możesz użyć indeksowania 0, ale jeśli to zrobisz, podaj go w swojej odpowiedzi.

1     1
2     2
3     4
4     5
5     10
6     11
7     13
8     14
9     28
10    29
11    31
12    32
13    37
14    38
15    40
16    41
17    82
18    83
19    85
20    86
10000 1679657

Bibliografia

• WolframMathWorld
• OEIS A003278

Galaretka , 4 bajty

Bḅ3‘

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Wykorzystuje to indeksowanie 0 i podstawową definicję z OEIS :

Sekwencja Szekeresa: a (n) -1 w trójce = n-1 w systemie binarnym

Bḅ3‘  Main link. Argument: n

B     Convert n to binary.
 ḅ3   Convert from ternary to integer.
   ‘  Increment the result.

Haskell, 37 36 32 bajtów

Przy użyciu podanego wzoru we wpisie OEIS, przy użyciu wskaźników opartych na 0. Dzięki @nimi za 4 bajty!

a 0=1;a m=3*a(div m 2)-2+mod m 2

Python 3, 28 bajtów

lambda n:int(bin(n)[2:],3)+1

Anonimowa funkcja, która pobiera dane wejściowe za pomocą argumentu i zwraca wynik. Jest to indeksowane zero.

Jak to działa

lambda n    Anonymous function with input zero-indexed term index n
bin(n)      Convert n to a binary string..
...[2:]     ...remove `0b` from beginning...
int(...,3)  ...convert from base-3 to decimal...
...+1       ...increment...
:...        and return

Wypróbuj na Ideone

Python 3, 113 bajtów

def f(n):
 i=1;a=[]
 for _ in range(n):
  while any(i+x in[y*2for y in a]for x in a):i+=1
  a+=[i]
 return a[n-1]

Ideone to!

Rubin, 28 24 bajty

Używając tej samej metody co Dennis, z indeksami opartymi na 0:

->n{n.to_s(2).to_i(3)+1}

Uruchom przypadki testowe na repl.it: https://repl.it/Cif8/1

Pyke, 5 bajtów

b2b3h

Wypróbuj tutaj!

Indeksowanie na podstawie 0

Ta sama formuła, co odpowiedź galaretki

Java 8, 52 46 bajtów

0 zindeksowanych.

i->Integer.valueOf(Integer.toString(i,2),3)+1;