MHB What is the solution to this challenging number theory problem?

AI Thread Summary
The discussion focuses on a number theory problem involving a set of natural numbers, S, defined by specific membership rules. It is established that if a number x is in S, then both 4x and the floor of the square root of x are also in S, leading to the conclusion that S encompasses all natural numbers, or S = ℕ. Additionally, the conversation explores how this conclusion changes if the multiplication factor in the first rule is replaced with a variable k. Participants discuss the implications of this substitution, noting that the solution for k must allow for all natural numbers to still be included in S. The thread emphasizes the logical steps required to reach these conclusions in number theory.
Nono713
Gold Member
MHB
Messages
615
Reaction score
4
Let $S$ be a nonempty set of natural numbers, equipped with the following membership rules:
$$\text{if} ~ ~ x \in S ~ ~ \text{then} ~ ~ 4x \in S \tag{1}$$
$$\text{if} ~ ~ x \in S ~ ~ \text{then} ~ ~ \lfloor \sqrt{x} \rfloor \in S \tag{2}$$
Show that $S = \mathbb{N}$, and find all the natural numbers $k$ for which this still holds if rule $(1)$ becomes $x \in S \implies kx \in S$ (i.e. substituting $k$ instead of $4$).
 
Last edited:
Mathematics news on Phys.org
This is a fun problem! :D I have, or I think I have, a solution for the first part of the problem.

We are given that $\Bbb N \supseteq S \neq \emptyset$, thus there is a $k \in \Bbb N$ such that $k \in S$. By rule $(2)$, $\lfloor \sqrt{k} \rfloor \in S$. Repeatedly applying rule $(2)$ in this fashion $n$ times, we see that there is an integer smaller than $k^{1/2^n}$ and (not strictly) greater $1$ in $S$. However, it is clear there exists a large $n$ for which $k^{1/2^n} \leq 2$. As $S \subseteq \Bbb N$ and since the only integer in $[1, 2)$ is $1$, we conclude that $1 \in S$.

By rule $(1)$, $4 \cdot 1$ is in $S$ and by rule $(2)$, $\lfloor \sqrt{4} \rfloor = 2$ is in $S$. It is thus clear that all of the powers of $2$ are in $S$. Now note that as $\Bbb Q$ is dense in $\Bbb R$, there are (well, countably) infinitely many rationals in the interval $[\log_2(n), \log_2(n+1)]$ for some integer $n$. We can thus cutoff the two ends of this interval to produce some interval $[a_0/b_0, a_1/b_1] \subseteq [\log_2(n), \log_2(n+1)]$ with rational limit points. As $a_0/b_0 < a_1/b_1$, i.e., $a_0 b_1 < a_1b_0$, we can always produce an integer $x$ inside $(a_0 b_1 \cdot 2^k, a_1 b_0 \cdot 2^k)$ for some proper choice of $k$. Thus $x/2^k \in [a_0/b_0, a_1/b_1] \subseteq [\log_2(n), \log_2(n+1)]$, i.e., $n^{(2^k)} \leq 2^x \leq (n + 1)^{(2^k)}$. As $2^x \in S$, applying rule $(2)$, $k$ times, on $2^x$ results $n \in S$. As this procedure can be applied to any integer $n$, we have $S = \Bbb N$.
 
Last edited:
Well done mathbalarka for participating and correctly answering the first part of the challenge! (though I believe extending it to also solve the second part is reasonably straightforward with some minor changes). My own original solution is given below, it follows the same major steps as mathbalarka's solution but uses different tools to arrive at the result:

I will immediately prove the second part of the challenge, the first part being a special case.

We first prove the lemma that if $[a, b)$ is an interval with $ka < b$ for integers $a, b, k > 1$ then $[a, b)$ contains a power of $k$. We first note that $k^0 = 1 < a$. Now suppose $k^r < a$ for any $r \in \mathbb{N}$. Then there are three possibilities: either $k^{r + 1} < a$, $k^{r + 1} \geq b$, or $k^{r + 1} \in [a, b)$. Now $k^{r + 1} \geq b$ is impossible, since $ka < b$ and $k^r < a$ hence $k(k^r) = k^{r + 1} < b$. If $k^{r + 1} < a$, then we can repeat the argument until $k^{r + s} \in [a, b)$ for some $s > 0$, which will happen as the sequence $(k^n)_{n = 0}^\infty$ is strictly increasing.

Since $\lfloor \sqrt{1} \rfloor = 1$ and $\lfloor \sqrt{x} \rfloor < x$ for $x > 1$ since $\lfloor \sqrt{x} \rfloor^2 \leq x$, it follows that repeatedly applying rule $(2)$ starting from any integer will eventually yield 1. Since $S$ is nonempty, there exists at least one element in $S$, and thus $1 \in S$ by the above reasoning. It therefore suffices to show that $1 \in S \implies x \in S$ for all $x \in \mathbb{N}$ to prove the claim. Denote $I_n$ the interval $[x^{2^n}, (x + 1)^{2^n})$. This interval $I_n$ can be made arbitrarily large by increasing $n$, as:
$$\lim_{n \to \infty} \frac{(x + 1)^{2^n}}{x^{2^n}} = \lim_{n \to \infty} \left ( \frac{x + 1}{x} \right)^{2^n} = \infty$$
In other words, the upper bound of the interval grows faster than the lower bound, and hence $I_n$ is asymptotically unbounded in size.

Now let $k \in \mathbb{N}$ such that $x \in S \implies kx \in S$. Since $1 \in S$, repeatedly applying this rule amounts to saying that $k^r \in S$ for all $r \in \mathbb{N}$. We have seen that $I_n$ can be made arbitrarily large, thus there exists an $n$ such that $kx^{2^n} < (x + 1)^{2^n}$ for any $k$. Hence by the lemma, $k^r \in [ x^{2^n}, (x + 1)^{2^n} )$ for some $r \in \mathbb{N}$. At this point, since $k^r \in S$, it suffices to repeatedly apply rule $(2)$ on $k^r$ which is guaranteed to eventually yield $x$ by monotonicity of the square root floor function, and we conclude that $x \in S$. We have only needed $k > 1$ (for the lemma) and therefore $S = \mathbb{N}$ for all (integer) $k > 1$, including $k = 4$. $\blacksquare$​
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...

Similar threads

Back
Top