11
\$\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

11 Answers 11

9
\$\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.
| improve this answer | |
\$\endgroup\$
7
\$\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
| improve this answer | |
\$\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

| improve this answer | |
\$\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!

| improve this answer | |
\$\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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pyke, 5 bytes

b2b3h

Try it here!

0-based indexing

Same formula as jelly answer

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Extended), 5 bytes

1+3⊥⊤

Try it online!

Jo King's suggestion.

APL (Dyalog Unicode), 12 bytes

1+3⊥2(⊥⍣¯1)⊢

Try it online!

Based on Dennis' Jelly answer.

Outputs are zero indexed.

1+3⊥2(⊥⍣¯1)⊢
           ⊢ Take argument
    2(⊥⍣¯1)  Encode in binary
  3⊥         Decode from ternary
1+           Add 1
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ With Dyalog Extended, this can be just 5 bytes! You can also save 2 bytes in Unicode \$\endgroup\$ – Jo King 2 days ago
1
\$\begingroup\$

Java 7, 60 42 bytes

0 Indexed

int s(int n){return n<1?1:3*s(n/2)-2+n%2;}

Using the implicit sequence definition from OEIS. Thanks to Kevin for the improvement using only one return statement.

| improve this answer | |
New contributor
Jon Ford is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
0
\$\begingroup\$

Java 8, 52 46 bytes

0 indexed.

i->Integer.valueOf(Integer.toString(i,2),3)+1;
| improve this answer | |
\$\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
0
\$\begingroup\$

Pip, 11 bytes

1+(aTB2)FB3

Try it online!

Based on Dennis' Jelly answer. Zero Indexed.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Japt, 4 bytes

0-indexed

Ò¢n3

Try it or run all test cases from the OEIS entry

Same as most other solutions:

Ò¢n3     :Implicit input of integer U
Ò        :Negation the bitwise NOT of
 ¢       :U converted to a binary string
  n3     :Converted from a ternary string
| improve this answer | |
\$\endgroup\$

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.