Skip to main content

n-th non-square

Problem:
Find the n-th non-square number.

(Adapted from Problem Solving Strategies, Arthur Engel)


If you have CS background, I invite you to come up with an O(log N) solution.

Done? Good. Below I present the O(1) approach.

Solution:
The n-th non-square number is given by \( F(n) = \left \lfloor n + \sqrt{n} + 1/2  \right \rfloor \).

Proof:
Let G(n) be the same as F(n) except for the floor function.

Investigate \( m \neq F(n) \). There is the largest \( n \) s.t. \( F(n) < m \). Hence \( m+1 \leq F(n+1) \).
We conclude that \(G(n) < m \) and \(m+1 \leq G(n+1) \).

Rearranging the terms and squaring the inequalities, we get:
\( n < (m-n-1/2)^2 \) and \( (m-n-1/2)^2 < n+1 \), or
\( n - 1/4 < (m-n)^2 - (m-n) < n + 3/4 \).
Since the middle term is an integer, we see that \( (m-n)^2 - (m-n) = n \). Simplifying, we get \(m = (m-n)^2\), showing that m is a square.

In other words, F(n) skips all squares.

Now, we will show that F(n) is the n-th non-square number. The proof is by counting.
Fix k. We note that \(F(k^2) = k^2 + k\). Hence There are \(k^2\) terms of F(n) \( \leq k^2 + k \).
On the other hand, we know that there are k squares \( \leq k^2 + k \). Hence F(n) iterates through all the non-square numbers \( \leq k^2 + k \). Therefore we conclude that F(n) is the n-th non-square.

QED

Comments

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED

232 | 20^n + 16^n - 3^n - 1

Problem: If \(n\) is even, then \( 323 | 20^n + 16^n - 3^n - 1 \). Solution: Let \( n = 2k \). We have \( 17 | 400^k - 9^k \) and \( 17 | 256^k - 1 \). Hence \( 17 | 20^n + 16^n - 3^n - 1 \). Also \( 19 | 20^n -1 \) and \( 19 | 256^k - 9^k \). Hence  \(19 | 20^n + 16^n - 3^n - 1 \). Hence it is divisible by \( 17 \times 19 = 323 \). QED