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

Post a Comment

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
Post a Comment
Read more

Derive e

Prove that \( \left( 1 + \frac{1}{n} \right)^n \) converges. Solution Let \( G(n) =  \left( 1 + \frac{1}{n} \right)^n \). Binomial expansion, \( G(n) = \sum_{k = 0}^{n} \frac{ \binom{n}{k} }{n^k} \). By simple inequality argument, \( \frac{ \binom{n}{k} }{n^k} < \frac{1}{k!} \). So if we let \( F(n) = \sum_{k = 0}^{n} \frac{1}{k!} \), we have \( G(n) < F(n) \). By simple inequality argument, \( F(n) < 1 + \sum_{k = 1}^{n} \frac{1}{2^{k-1}} < 3 \). So G and F are bounded above. By AM-GM, \( \frac{G(n-1)}{G(n)} = \left( \frac{ n^2 }{ n^2 - 1} \right)^{(n-1)} \frac{ n}{n+1} < \left(  \frac{ \frac{ n^2 }{ n^2 - 1} (n-1) + \frac{ n}{n+1} }{n} \right)^n = 1 \). So \( G(n-1) < G(n) \). Since G is monotonic increasing and bounded above, G converges. Similarly F converges. Let's also prove that G and F converges to the same limit. By studying individual terms in \( F(n) - G(n) \) and making simple inequality arguments, we can show that for each \( \epsilon > 0 \) w...
Post a Comment
Read more

12 coins

Problem: There are 12 identical coins. There might be one that is a counterfeit, which is either heavier or lighter than the rest. Can you identify the counterfeit (if any) using a balance at most 3 times? Solution: I think this is one of the most difficult variations of the coins weighing problem. The main idea is to "mark" the coins after weighing them. Step 1. Divide the coins into groups of 4. Weigh the first two. If they have the same weight, go to step 4. Otherwise, mark the coins belonging to the heavier group 'H', lighter group 'L', and the unweighted ones 'S'. We know that the counterfeit is either in L or H. Step 2. Now we have 4 Hs, 4 Ls, and 4 Ss. We now form 3 groups: HHL, LLH, and HLS. Step 3. Weigh HHL against HLS. Case 3.1: HHL is lighter than HLS. Then either the L in HHL or the H in HLS is the counterfeit. Simply weigh one of them against S and conclude accordingly. Case 3.2: HHL is heavier than HLS. Then the counterfeit ...
Post a Comment
Read more