Question: find the size of a maximal subset $A$ of $[n]=\{1,\cdots,n\}$ satisfying that for any distinct elements $x,y\in A$, $x+y$ is not a perfect square.
Consider a graph with $n$ vertices: $x$ and $y$ are adjacent if $x+y$ is a perfect square. The question is equivalent to finding the size of a maximum independent set (a collection of non-adjacent vertices of the largest size). Note that each vertex is adjacent to as few as about $(\sqrt{2}-1)\sqrt{n}$ vertices (at vertex $n$) and as many as about $\sqrt{n}$ vertices (at vertex $1$).
I run a code using the greedy algorithm: take $1$; for each subsequent integer, take it if the sum of it and any taken integer is not a perfect square. The first few are \begin{equation*} 1,2,4,6,9,11,13,17,18,20... \end{equation*} There seems to be some patterns, but they fade away very quickly as the numbers get larger.
For $n=100$, the size given by the above algorithm is $31$; for $n=1000$, the size is $221$; for $n=4000$, the size is $845$; for $n=10000$, the size is $2172$; for $n=20000$, the size is $4461$.
Is it possible to estimate the size of a maximum independent set?
