14
\$\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
  • 2
    \$\begingroup\$ Related. (If I understand your challenge correctly.) \$\endgroup\$ Aug 2, 2016 at 14:56
  • \$\begingroup\$ @MartinEnder You did understand my challenge correctly. \$\endgroup\$
    – Leaky Nun
    Aug 2, 2016 at 14:56

11 Answers 11

11
\$\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\$
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
\$\endgroup\$
0
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\$
2
+100
\$\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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ With Dyalog Extended, this can be just 5 bytes! You can also save 2 bytes in Unicode \$\endgroup\$
    – Jo King
    Sep 18, 2020 at 13:23
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.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to CGCC! :) You don't need the static , and you can also golf the if(n==0)return 1;return 3*s(n/2)-2+n%2; to return n<1?1:3*s(n/2)-2+n%s;. :) If you haven't seen it yet, tips for golfing in Java and tips for golfing in all languages might be interesting to read through. Enjoy your stay! \$\endgroup\$ Sep 18, 2020 at 13:54
0
\$\begingroup\$

Java 8, 52 46 bytes

0 indexed.

i->Integer.valueOf(Integer.toString(i,2),3)+1;
\$\endgroup\$
4
  • \$\begingroup\$ You don't need the return but you do need the semicolon afterwards \$\endgroup\$
    – Leaky Nun
    Aug 3, 2016 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, 2016 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, 2016 at 15:24
  • \$\begingroup\$ Alrighty, no return plus semi-colon is shorter than before anyway :) \$\endgroup\$
    – Justin
    Aug 3, 2016 at 15:30
0
\$\begingroup\$

Pip, 11 bytes

1+(aTB2)FB3

Try it online!

Based on Dennis' Jelly answer. Zero Indexed.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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