List of integers without any arithmetic progression of n terms Let's consider a positive integer $n$ and the list of the $n^2$ integers from $1$ to $n^2$. What is the minimum number $f(n)$ of integers to be cancelled in this list so that it is impossible to form  any arithmetic progression of $n$ terms with the remaining integers?
 A: Extending my comment to an answer for small $n$: a brute force program gives
$$
\begin{align}
f(1)&=1 &&\{1\}  \\ 
f(2)&=3 &&\{1,2,3\} \\
f(3)&=4 &&\{3,4,5,7\} \\
f(4)&=6 &&\{3,4,5,6,10,13\} \\
f(5)&=7 &&\{3, 7, 9, 10, 11, 16, 21\} \\
f(6)&=9 &&\{5, 8, 12, 14, 15, 16, 21, 26, 31\} \\
f(7)&=11 &&\{3, 9, 11, 12, 13, 14, 15, 22, 29, 36, 43\} \\
f(8)&=13 &&\{7, 10, 16, 18, 19, 20, 21, 22, 29, 36, 43, 50, 57\}
\end{align}
$$
A: EDIT: The original values of $f$ that I reported were the result of a buggy program, as noted by Wolfgang in the comments.  I have fixed the bug and corrected the results.

This problem is easily coded up as an integer linear program.  For $1\le i\le n^2$, let $x_i$ be a 0-1 variable indicating whether $i$ is chosen.  Minimize $\sum_i x_i$ subject to the constraints $\sum_{a\in A} x_a \ge 1$ for every arithmetic progression $A$ of interest.
Assuming no bugs in my program, it took CPLEX only a few minutes to extend JiK's list of small values to:
$$
\begin{align}
f(8)&=13 &&\{6,13,18,23,28,36,37,38,39,40,43,50,57\} \\
f(9)&=15 &&\{8,15,22,29,32,41,42,43,44,45,46,54,61,68,75\} \\
f(10)&=16 &&\{10,15,22,29,36,43,53,55,56,57,58,68,73,74,84,91\}\\
f(11)&=18 && \{11,22,33,44,55,60,66,68,72,76,77,85,92,97,99,102,106,111\}
\end{align}
$$
The last of these took less than 15 minutes on a six-core machine (about 400,000 "ticks" in CPLEX parlance).
I'm sure that cleverer techniques could push the computation further, but this is already enough to show that the OEIS doesn't already know about this sequence.
A: This is not a complete answer, but a reasonable estimate.
Fix a prime $(1-o(1))n<p<n$. Every length-$n$ arithmetic progression with the difference co-prime with $p$ contains an element divisible by $p$; hence, removing all multiples of $p$ from $[1,n^2]$, we kill all such progressions. Now, every progression with the difference $d<n$ not co-prime with $p$ actually has $d=p$ (recall that $2p>n$). The set of all integers from $[1,n^2]$, not divisible by $p$, splits into $p-1$ progressions with difference $p$, each of these progressions having length $n^2/p+O(1)<2n$; removing just one element in the middle of every such progression kills all length-$n$ progressions with difference $p$. Altogether, we have removed $(n^2/p)+p+O(1)<2(1+o(1))n$ elements from $[1,n^2]$. As a result,
  $$ n\le f(n) < (2+o(1))n, $$
the lower bound following from the trivial observation that one must remove at least one element from every subinterval $[kn+1,(k+1)n],\ 0\le k<n$.
A: For the first values of n my best estimates of f(n) are the following:
f(1) = 1,
f(2) = 3 and for example the remaining integer is 1,
f(3) = 4 and for example the remaining integers are 1,2,6,8,9
f(4) = 6 and for example the remaining integers are 1,2,3,5,8,9,12,14,15,16
f(5) = 8 and for example the remaining integers are 1,2,3,4,6,7,8,12,14,15,18,19,20,22,23, 24,25
f(6) = 10
f(7) = 12
....
I wonder if the conjecture f(n) = 2n - 2 for n>2 is appropriate and can be demonstrated or not.
