How do I make a function that generates nth natural number that isn't a perfect square?

Question

So I want to make a function such that for every n that you input it generates nth natural number that isn't a perfect square, like {2, 3, 5,...}? I tried recurrance relation and I can't seem to find the proper relation between the members of sequence. Then I tried making a function but I don't know what to use actually... Any help?

Answer 1

OEIS to the rescue.

It gives the formula $$ n+\left\lfloor\frac12+\sqrt n\right\rfloor. $$ where $\lfloor{}\cdot{}\rfloor$ is the floor function.

Answer 2

Update:

If you want to get a closed-form formula for the OP's function, the starting point found below would 'force you' to discover the floor function and to be examining the class of functions of the form

$$ f(n) = n + \lfloor \alpha + \sqrt n \rfloor \; \text{ where } 0 \le \alpha \lt 1 $$

Notice that the domain of any such function can be naturally partitioned into the maximal intervals (singletons OK) where the function has the pattern

$$ f(n + 1) = f(n) + 1 \; \text{ both } n \text{ and } n + 1 \text{ belong to the interval}$$

For the problem at hand, you might 'guess' that $\alpha = \frac{1}{2}$ works. Using logic and the formula

$$ (a+b)^2 = a^2 + 2ab + b^2$$

you can show that it is indeed the function that 'fits onto' the 'action'.

---

Let $\Bbb N = \{1,2,3,\dots\}$.

Let $\pi_1$ and $\pi_2$ be the two coordinate projection mappings on $\Bbb N \times \Bbb N$.

We will define a function $f$ using recursion.

Define $f(1) = (2,2)$.

For $n \ge 1$ define

$$ f(n+1) = \left\{\begin{array}{lr} \left ( \, \pi_1(f(n)) + 1 ,\pi_2(f(n))\, \right ) & \text{when } \pi_1(f(n)) + 1 \lt {[\pi_2(f(n))]}^2 \\ \left ( \, \pi_1(f(n)) + 2 ,\pi_2(f(n))+1 \, \right ) & \text{else } \end{array}\right\} $$

The function $\pi_1 \circ f$ has the desired properties.