[Question]
  [
(This is [A065825](https://oeis.org/A065825).) The [sequence](/questions/tagged/sequence "show questions tagged 'sequence'") defaults apply, so you can pick another format other than this one.
Given an input integer `n`, find the smallest number `k` so that there exists an n-item subset of `{1,...,k}` where no three items form an arithmetic progression.
## Procedure
Here, we calculate `A065825(9)`.
We assume you have already looped from 1 to 19, and `k`=20 (it's just an example).
### 1. Generate a range from 1 to k.
```
[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
```
### 2. Pick `n` items from that sequence, following the original order of the sequence.
```
[1 2 6 7 9 14 15 18 20]
```
### 3. No 3 items form an arithmetic progression.
If a sequence has arithmetic progression, it basically means the sequence has the same step between every two consecutive items.
For example, the sequence of positive even numbers (`[2 4 6 8 ...]`) has a consistent step (i.e. `4-2=2`, and `6-4=2`, etc.), so it has arithmetic progression.
The Fibonacci sequence (`[1 1 2 3 5 8 13 21 ...]`) does not have arithmetic progression, since it does not have a consistent step. (`3-2=1`, `5-3=2`, `8-5=3`, etc.)
As an example, let's pick 3 items from our generated sequence.
```
[1 2 6 [7 9 14] 15 18 20]
```
The picked 3-item sequence does not have arithmetic progression, since the differences are respectively `9-7=2` and `14-9=5`.
This has to apply to **every 3-item pair**:
```
[[1 2 6] 7 9 14 15 18 20] (2 -1 =1, 6 -2 =4)
[1 [2 6 7] 9 14 15 18 20] (6 -2 =4, 7 -6 =1)
[1 2 [6 7 9] 14 15 18 20] (7 -6 =1, 9 -7 =2)
[1 2 6 [7 9 14] 15 18 20] (9 -7 =2, 14-9 =5)
[1 2 6 7 [9 14 15] 18 20] (14-9 =5, 15-14=1)
[1 2 6 7 9 [14 15 18] 20] (15-14=1, 18-15=3)
[1 2 6 7 9 14 [15 18 20]] (18-15=3, 20-18=2)
```
Here are some examples of picking non-consecutive items from the output sequence:
```
[1 [2] 6 [7] 9 [14] 15 18 20] (7-2=5,14-7=7)
[[1] 2 6 [7] [9] 14 15 18 20] (7-1=6,9 -7=2)
```
If the above is satisfied for `k`, then `k` is a valid output for `A065825(9)`.
## Test cases
[Here](https://tio.run/##AS4A0f9vc2FiaWX//@KInsqSTMOmScO5ypLDpjPDuc61wqXDi33DoF99Z8SAfdC9//83) is a reference program I use to check my test cases.
```
n       a(n)
1       1
2       2
3       4
4       5
5       9
6       11
7       13
8       14
9       20
```
  
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 17 bytes
```
ff!/#.OZ.cY3.cSTQ
```
[Try it online!](https://tio.run/##K6gsyfj/Py1NUV9Zzz9KLznSWC85OCTw/38zAA "Pyth – Try It Online")
`.cSTQ`: generate all list of numbers in the range [1,T] with length equal to the input.
`.cY3`: for each of those, generate all length 3 subsequences.
`/#.OZ`: filter for the subsequences where the average is a member of the list. These are the arithmetic progressions.
`f!`: filter for the original lists with no arithmetic progressions
`f`: find the lowest T where at least one list is found.
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), ~~123~~ ~~115~~ ~~96~~ 94 bytes
Another ~~-15~~ -17 bytes thanks to [Surcolose Sputum](https://codegolf.stackexchange.com/users/92237/surculose-sputum)!
```
f=lambda n,k=1:len(d:=f'{k:b}')*all(k>>i&k&k<<i<1for i in range(d.count('1')//n,k))or f(n,k+1)
```
[Try it online!](https://tio.run/##Vc7BasMwDAbge55C9NDYntvGK5QSksDYqXS7bL2PNHE2YccOsnMoo8/emY0NdhAI6dOPpkv88G67n@iG4@QpAungZ@q0hHAJWap10JF0N1NA7yyOGJkqhNjx7Jd@i5/N3@jl6fB8OL29nh4ejxLYvRDbQsJKcX4batuO574FJ02tSqsd68t6yD9Neb7mXLTWMtM0uDRLU1VYqcETIKADat27Zv2687OLLFc532xSCOcJDCx1dyrF/9dKqoKXGcBEmI5QwmLVLGTymH75Ag "Python 3.8 (pre-release) – Try It Online")
---
# [Python 2](https://docs.python.org/2/), ~~147~~ ~~135~~ 124 bytes
-11 bytes thanks to [Surcolose Sputum](https://codegolf.stackexchange.com/users/92237/surculose-sputum)!
```
from itertools import*
f=lambda n,k=1,C=combinations:k*any(all(a+c-b*2for a,b,c in C(w,3))for w in C(range(k),n))or f(n,k+1)
```
[Try it online!](https://tio.run/##JcwxDoMwDIXhnVNkjMEdQjckJk7iUNJaJDYKkRCnT0GM79ent53lp9LXGrImw2XJRTXuhtOmubRNGCMl/yEjuI4Op3HW5FmosMo@rC3JaSlGS9388m0fNBtCj7NhMZM98A1wt@PZmeS72BVQAK4a7PXaOag34Zs8wKFzMDRmyyzFMF6Qof4B "Python 2 – Try It Online")
[Answer]
# [R](https://www.r-project.org/), ~~96~~ 83 bytes
```
k=n=scan();C=combn;`[`=Map;try(while(!any(all[diff[C[C(1:k,n,,F),3],1,2]]))k=k+1);k
```
[Try it online!](https://tio.run/##K/r/P9s2z7Y4OTFPQ9Pa2TY5PzcpzzohOsHWN7HAuqSoUqM8IzMnVUMxMa9SIzEnJzolMy0t2jnaWcPQKlsnT0fHTVPHOFbHUMcoNlZTM9s2W9tQ0zr7v8V/AA "R – Try It Online")
Full program, returns 1-indexed member of the sequence. Very slow for `n > 8`.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 19 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
∞.ΔLI.Æε3.Æε¥Ë≠}P}à
```
Outputs the \$n^{th}\$ value \$k\$.
[Try it online](https://tio.run/##yy9OTMpM/f//Ucc8vXNTfDz1Dred22oMJg8tPdz9qHNBbUDt4QX//5sDAA) or [verify the first 8 test cases](https://tio.run/##yy9OTMpM/W/h6ndopb2SwqO2SQpK9v8fdczTOzfF59A6vcNt57Yag8lDSw93P@pcUBtQe3jB/1qd/wA) (times out for \$\geq9\$).
**Explanation:**
```
∞.Δ                 # Find the first positive integer `k`
   L                # for which its list in the range [1,k]
    I.Æ             # with combinations of the input amount of elements
       ε         }à # contains any combination-list which is truthy for:
        3.Æ         #  When taking all 3-element combinations of the current list
           ε   }P   #  they are all truthy for:
            ¥       #   When taking the forward differences of both pairs in this triplet
             Ë≠     #   they are NOT the same
                    # (after which the resulting `k` is output implicitly)
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~109...94~~ 91 bytes
*-8 bytes thanks to @GB*
```
->n{1.step.find{|k|[*1..k].combination(n).any?{|p|p.combination(3).all?{|a,b,c|b-a!=c-b}}}}
```
[Try it online!](https://tio.run/##VY0/D4IwFMR3P8VDB8A8Ggti/BN0MA4umhg3ZGhRIlEfRHAwbT871sTFG2643@Xu@ZLvrkhOXbAkxVnTXmpWlHRW@qbTIWfslrG8esiSRFtW5JHPBL1XSte6/gORBfe7BQIl5loGwknyQBqrTowm8TSMIYGUY4hjjHGGnCOPkI8xHGU9zz7NfHYR@RUUaNJQ2XaRUraA@tU20BfeQJHxbTpQlfmak/x2WXMtixZW4G53LszBdc16fzhs1kenD6b7AA "Ruby – Try It Online") Takes less than 1 s for \$n\le9\$. Times out for \$n\ge12\$.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 14 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
œcœc3IEƇƊÐḟð1#
```
A monadic Link accepting a non-negative integer which yields a non-negative integer.
**[Try it online!](https://tio.run/##y0rNyan8///o5GQgMvZ0PdZ@rOvwhIc75h/eYKj8//9/cwA "Jelly – Try It Online")** (Too inefficient for n=9 within 60s.) Or see the [test-suite](https://tio.run/##y0rNyan8///o5GQgMvZ0PdZ@rOvwhIc75h/eYKj83@Jw@6OmNf8B "Jelly – Try It Online").
### How?
```
œcœc3IEƇƊÐḟð1# - Link: integer, n
            1# - let k=n and count up to find the first k, for which this is truthy:
           ð   -   dyadic chain - i.e. f(k, n):
œc             -     combinations of length (n) of (implicit [1..k])
         Ðḟ    -     filter discard those n-tuples which are truthy under:
        Ɗ      -       last three links as a monad:
  œc3          -         combinations of length three of (the n-tuple)
     I         -         incremental differences - e.g. [3,6,8]->[6-3,8-6]->[3,2]
       Ƈ       -         filter keep those diffence-pairs which are truthy under:
      E        -           all equal?
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 94 bytes
```
(t=1;While[Select[Range@t++~(S=Subsets)~{#},!Or@@(Equal@@Differences@#&/@#~S~{3})&]=={}];t-1)&
```
[Try it online!](https://tio.run/##JcwxCsMgFADQq7QIEkmLhE4lCH9o55Y6dAgZrPwkghGqP5PEq9uh7wBvNbTgashZU2dVG1Jd/16cx0GjR0vDy4QZgdq2NFrp7ZOQkiiZ7afjIwI09@9mPMDNTRNGDBYTMC6BFV3yZRd8VCrvY0/nTvD6jC6QhFnC4f9ea/0B "Wolfram Language (Mathematica) – Try It Online") 1-9 takes 1 min
[Answer]
# JavaScript (ES6), ~~150~~ 145 bytes
This is quite inefficient for \$n>8\$.
```
n=>(g=a=>(P=a=>a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]))(a).some(a=>a[n-1]*P(a).every(([a,b,c,d])=>d|b-a!=c-b))?k:g([...a,++k]))([k=1])
```
[Try it online!](https://tio.run/##JYxBDoIwFET3nqImLP6X0oSdUatXYN804VMKUbQ1oASCnB1p2LxJJjPvQT11pr2/P4nzpV0quTh5hVrSyiyQRGvLr7EAxAeUVyWEIB4gXvSGcWtGPmjUXCmtEYFQdP5lIdyVS1J9yEJne9uOAIp4wQ0v9Worf0VCe2mSAvHWnGrY9HHcBI9qZKpxqXwLjkmWnpljF8mOa8YxTjvGjHedf1rx9DXkBNHkZlyX0VSBwznH3bz8AQ "JavaScript (Node.js) – Try It Online")
## Commented
### Helper function
Since we don't have any combinatorial function available as a built-in, we're going to define just one: \$P\$ is a helper function that computes the powerset of a given array.
```
P = a =>
  a.reduce((a, x) =>
    [...a, ...a.map(y => [...y, x])],
    [[]]
  )
```
### Main function
```
n => (                  // n = input
  g = a =>              // g is a recursive function taking a range a[]:
    P(a).some(a =>      //   for each array a[] in the powerset of a[]:
      a[n - 1] *        //     make sure that the length of a[] is at least n
      P(a)              //     compute the powerset of a[]
      .every(           //     for each quad [a,b,c,d] in there,
      ([a, b, c, d]) => //     the test is successful if either:
        d |             //       - d is defined (meaning that this array has
                        //         more than 3 entries)
        b - a != c - b  //       - or a,b,c is not an arithmetic progression
      )                 //     end of every()
    )                   //   end of some()
    ?                   //   if truthy:
      k                 //     success: return k
    :                   //   else:
      g([...a, ++k])    //     try again with k+1 appended to a[]
)([k = 1])              // initial call to g with k = 1 and a = [1]
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 22 bytes
```
`@:GXN!"@IXN!ddA]va~}@
```
[Try it online!](https://tio.run/##y00syfn/P8HByj3CT1HJwRNIpqQ4xpYl1tU6/P9vAQA) Or [verify test cases `1`‒`8`](https://tio.run/##y00syfmf8D/Bwco9wk9RycETSKakOMaWJdbVOvyPdYmqCPlvyGXEZcxlwmXKZcZlzmUBAA) (test case `9` times out online).
### Explanation
```
`       % Do...while
  @:    %   Push range [1 2 ... k] where is the current iteration index
  G     %   Push input, n
  XN    %   Combinations of the elements [1 2 ... k] taken n at a time. This
        %   gives an n-column matrix where each row is a combination
  !     %   Transpose. Each combination is now a column
  "     %   For each column
    @   %     Push current column
    I   %     Push 3
    XN  %     Combinations of the elements of the current column taken n at
        %     a time. This gives a 3-column matrix
    !   %     Transpose. Each combination is now a column
    dd  %     Consecutive differences along each column, twice. This gives a
        %     row vector containing 0 for columns whose three elements form
        %     an arithmetic progression
    A   %     All. This gives true if all entries of the vector are non-zero;
        %     that is, if there were no arithmetic progressions of length 3
  ]     %   End
  v     %   Concatenate the stack into a column vector
  a~    %   Any, negate. Gives false if any entry from the above vector is
        %   non-zero. This will be used as loop condition; that is, if false
        %   the loop will end
}       % Finally (execute on loop break)
  @     %   Push latest k
        % End (implicit). The top of the stack is used as loop condiion
        % Display (implicit)
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~40~~ 37 bytes
```
≔⁰ηＷ∨⁻Σ⍘η²ＩθΦη＆η＆×ηＸ²⊕λ×ηＸ⁴⊕λ≦⊕ηＩＬ↨η²
```
[Try it online!](https://tio.run/##ZY5BCsIwEEX3niLLCUSQoquuWkEQLBbqBUI7NANpqklqjx@b2IXUWc38/xheq6RtR6lDKJyj3sBBMMXz3axII4O7hYrM5KCZBiilw8ZbMj0owTLOBTtL5@EVtwtpjzYWJfmZHBam21wPGtDFrB7nBc0Eu5rW4oDGYweaxzcb5vjPpGGVfK7CP/1XvV4MPSSzG5reqyS@KnOeh3AK@7f@AA "Charcoal – Try It Online") Link is to verbose version of code. Edit: Saved 3 byte by porting @SurculoseSputum's method. Now too slow for `n>6`. Explanation:
```
≔⁰η
```
Start with an empty bitmask.
```
Ｗ∨⁻Σ⍘η²Ｉθ
```
Repeat while the bitmask contains the wrong number of bits...
```
Φη＆η＆×ηＸ²⊕λ×ηＸ⁴⊕λ
```
... or it contains three terms in arithmetic progression...
```
≦⊕η
```
... increment the bitmask.
```
ＩＬ↨η²
```
Output the the length (in base 2) of the bitmask, which is necessarily equal to `k`.
At a cost of 2 bytes, I can replace `Φη` with `⊙↨η²`, which makes the code fast enough to compute up to `n=9`:
```
≔⁰ηＷ∨⁻Σ⍘η²Ｉθ⊙↨η²＆η＆×ηＸ²⊕λ×ηＸ⁴⊕λ≦⊕ηＩＬ↨η²
```
[Try it online!](https://tio.run/##ZY/BCsIwEETvfkWOG4ggxYPQU@tJsFioPxDapQmkW01Si18fm9RD0TntzgzL21ZJ247ShFA4p3uCg2CK57tZaYMMbhYqTZODZhqglA4bbzX1oATLOBfsLJ2HZ5wKeqfCGglWaj9rhwV10dlsdz2gi149zmghE@xCrcUByWMHhsdjP53jfyeJVfLxxd7k6wP1wukh8V2Req82dIvyEE5h/zIf "Charcoal – Try It Online") Link is to verbose version of code. (Link only computes `n=8` to avoid unnecessarily overloading TIO.)
Looping over the odd numbers is slightly faster still, but not enough to be able to compute `n>9` on TIO. (It also gives the wrong answer for `n=0`, although that's not required by the question.)
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 91 bytes
```
.+
*_¶
/^(_)*¶(?<-1>10*)*(?(1)$|1)|1(.)*1(?<-2>.)*(?(2)$)1/{`¶(1*)$
¶0$1
)T`10`d`01*$
r`.\G
```
[Try it online!](https://tio.run/##HcshDsJAEAVQP@cYMX8I2/1VCNJKLoBs6JCAwCAaHD3XHmAvtoXql7c8P6/3na2lg/hci3Q3m@G12Hg@cmB2uI1G6EqstATnn/oh7dBDwe4bv0CHSi1ZKbgGczwi01WWSNOltdMG "Retina – Try It Online") Uses @SurculoseSputum's method, but too slow for `n>8`. Explanation:
```
.+
*_¶
```
Convert `n` to unary, and add a working area for the bitmask.
```
/^(_)*¶(?<-1>10*)*(?(1)$|1)|1(.)*1(?<-2>.)*(?(2)$)1/{`
)`
```
Repeat while the number of bits in the bitmask is not `n`, or there are three bits in the bitmask with identical spacing...
```
¶(1*)$
¶0$1
```
If the bitmask contains no zeros then prefix one.
```
T`10`d`01*$
```
Increment the bitmask.
```
r`.\G
```
Output the length of the bitmask, which is necessarily equal to `k`.
The bitmask computations involve .NET balancing groups.
```
^(_)*¶
```
This captures the unary value of `n`. Since the `*` is outside of the `(_)`, the group is captured `n` times. .NET records each capture as a stack, so `$1` now has a depth of `n`.
```
(?<-1>10*)*
```
This attempts to match the regex `10*`. Each successful match pops one of the captures from the `$1` stack. This continues until the stack is empty or there are no matches.
```
(?(1)$|1)
```
A conditional expression now checks whether the stack is empty. If it is not, then we want this to be because we ran out of `1` bits to match, which will be at the end of the string. If the stack is empty, then we want this to be because there are too many `1` bits, so we should be able to match one.
Note that while Retina will try to backtrack if it fails to match, this necessarily means both that the stack is not empty and that the match is not at the end of the string, i.e. this condition will never succeed in the case where the number of bits is correct.
```
1(.)*1(?<-2>.)*(?(2)$)1
```
In a similar way, we capture a variable number of bits between two `1` bits, and then require that the same number of bits exists between the latter and another `1` bits. Here the condition for a non-empty stack is a logical impossibility (`$` before a `1`) thus requiring the stack to be empty at this point, indicating that the number of bits is the same.
]