1

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?

Adnan C
  • 63
  • 1
    It's worth noting that the phrase "the nth natural number that isn't a perfect square" is a perfectly good function already; it just happens to be a function that's written in English instead of the usual numbers and symbols. But I think what you're looking for is a way of writing this function using the usual numbers and symbols; that way of writing a function is called a "closed form". – Tanner Swett May 02 '19 at 01:41

2 Answers2

8

OEIS to the rescue.

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

Arthur
  • 199,419
  • I gotta admit, I did not expect a closed form answer, and certainly not one as simple as this. – JonathanZ May 02 '19 at 13:51
  • 1
    @JonathanZ If you would like some more reading, I asked a question a while back about how one could construct such a formula for a sequence which is given as the complement of some other sequence. The paper linked in the answer is, if I recall correctly, very informative on the subject. (On a side note, I have no idea why I have a different formula for the non-square numbers in that question. Might be a typo.) – Arthur May 02 '19 at 14:42
0

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.

CopyPasteIt
  • 11,366