9
\$\begingroup\$

Definition

  • a(1) = 1
  • a(2) = 2
  • a(n) is smallest number k>a(n-1) which avoids any 3-term arithmetic progression in a(1), a(2), ..., a(n-1), k.
  • In other words, a(n) is the smallest number k>a(n-1) such that there does not exist x, y where 0<x<y<n and a(y)-a(x) = k-a(y).

Worked out example

For n=5:

We have a(1), a(2), a(3), a(4) = 1, 2, 4, 5

If a(5)=6, then 2, 4, 6 form an arithmetic progression.

If a(5)=7, then 1, 4, 7 form an arithmetic progression.

If a(5)=8, then 2, 5, 8 form an arithmetic progression.

If a(5)=9, then 1, 5, 9 form an arithmetic progression.

If a(5)=10, no arithmetic progression can be found.

Therefore a(5)=10.

Task

Given n, output a(n).

Specs

  • n will be a positive integer.
  • You can use 0-indexed instead of 1-indexed, in which case n can be 0. Please state it in your answer if you are using 0-indexed.

Scoring

Since we are trying to avoid 3-term arithmetic progression, and 3 is a small number, your code should be as small (i.e. short) as possible, in terms of byte-count.

Testcases

The testcases are 1-indexed. You can use 0-indexed, but please specify it in your answer if you do so.

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

References

\$\endgroup\$
  • 2
    \$\begingroup\$ Related. (If I understand your challenge correctly.) \$\endgroup\$ – Martin Ender Aug 2 '16 at 14:56
  • \$\begingroup\$ @MartinEnder You did understand my challenge correctly. \$\endgroup\$ – Leaky Nun Aug 2 '16 at 14:56
8
\$\begingroup\$

Jelly, 4 bytes

Bḅ3‘

Try it online! or verify all test cases.

How it works

This uses 0-based indexing and the primary definition from OEIS:

Szekeres's sequence: a(n)-1 in ternary = n-1 in binary

Bḅ3‘  Main link. Argument: n

B     Convert n to binary.
 ḅ3   Convert from ternary to integer.
   ‘  Increment the result.
\$\endgroup\$
6
\$\begingroup\$

Haskell, 37 36 32 bytes

Using the given formula in the OEIS entry, using 0-based indices. Thanks @nimi for 4 bytes!

a 0=1;a m=3*a(div m 2)-2+mod m 2
\$\endgroup\$
3
\$\begingroup\$

Python 3, 28 bytes

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

An anonymous function that takes input via argument and returns the result. This is zero-indexed.

How it works

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

Try it on Ideone

\$\endgroup\$
2
\$\begingroup\$

Python 3, 113 bytes

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 it!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 28 24 bytes

Using the same method as Dennis, with 0-based indexes:

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

Run the test cases on repl.it: https://repl.it/Cif8/1

\$\endgroup\$
2
\$\begingroup\$

Pyke, 5 bytes

b2b3h

Try it here!

0-based indexing

Same formula as jelly answer

\$\endgroup\$
0
\$\begingroup\$

Java 8, 52 46 bytes

0 indexed.

i->Integer.valueOf(Integer.toString(i,2),3)+1;
\$\endgroup\$
  • \$\begingroup\$ You don't need the return but you do need the semicolon afterwards \$\endgroup\$ – Leaky Nun Aug 3 '16 at 15:12
  • \$\begingroup\$ This answer that say semicolons aren't counted; I could change it either way, but is counting semicolons the consensus? \$\endgroup\$ – Justin Aug 3 '16 at 15:14
  • \$\begingroup\$ Eh, that's what they told me. I don't know if the consensus is as such. \$\endgroup\$ – Leaky Nun Aug 3 '16 at 15:24
  • \$\begingroup\$ Alrighty, no return plus semi-colon is shorter than before anyway :) \$\endgroup\$ – Justin Aug 3 '16 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.