Given a positive integer k≥2, set a1=1 and, for every integer n≥2, let an be the smallest solution of equation x=1+n−1∑i=1⌊k√xai⌋ that exceeds an−1. Prove that all primes are among the terms of the sequence a1,a2,…
Problem
Source:
Tags: floor function, induction, number theory
03.03.2013 11:29
03.03.2013 21:58
03.03.2013 22:05
First, remark that if we plug in x=an−1 the RHS and you get the RHS is 1 too large. Thus an=an−1+1 if there does not exist positive integers i,j such that ai⋅jk=an. This motivates us to conjecture the sequence of ai is all numbers such that for all primes p we have pk does not divide them. We prove this by induction. Suppose for all i≤n−1 we have the ai are the set of above described numbers. Call numbers n such that vp(n)≥k for some p a ksunish number. Remark that each ksunish number can be uniquely decomposed into the product of a kth power and a non-ksunish number. Now consider the numbers x above an−1. First set x=an−1+1. Remark that x is a solution to the equation iff x is not a ksunish number. If x is a ksunish number, due to the unique decomposition statement above the RHS only increments up by 1 due to the inductive hypothesis. Thus the RHS remains 1 higher. Continue incrementing x by 1 and by the same logic we get x is a solution iff x is not a ksunish number due to the difference between the two sides staying at 1. Thus an is the first non-ksunish number after an−1 so we have completed our induction. Now note that all primes are non-ksunish numbers so we are done.
16.02.2015 19:16
05.03.2016 18:33
Take bn as the set of numbers that are k-power free. We claim an=bn which proves the problem. We use strong induction. The base cases are trivial. The main claim is that ∑ni=1⌊k√cbi⌋=c, where bn≤c<bn+1. Partition S={1,2,⋯c} by Si={ak⋅bi|a∈N} for 1≤i≤n. Then, we have |Si|=⌊k√cbi⌋, giving the desired statement. Therefore, assuming that am=bm for all m≤n−1, we have bn=n∑i=1⌊k√bnbi⌋=1+n−1∑i=1⌊k√bnbi⌋so an≤bn. If an<bn, we would have an=1+n−1∑i=1⌊k√anbi⌋=1+anby our previous lemma. This gives us that an=bn, as required.
09.03.2016 04:55
The bulk of the solution is contained in the following lemma: Lemma: The quotient am/an is never the kth power of a rational number for m>n≥1. Proof of Lemma: We go by strong induction on m. Assume the claim true for 1,2,⋯,m and we'll prove it true for m+1. For m∈N, introduce the function fm:N↦N defined by fm(x)=x−∑mi=1⌊k√xai⌋. We claim that fm(x)+1≥fm(x+1)≥fm(x)(⋆)for all x. Moreover, fm(x+1)≠fm(x) iff (x+1)/an is not a perfect kth power of a rational number for all 1≤n≤m.(†) The left inequality is obvious. To prove the right inequality, observe that fm(x+1)−fm(x)=1−m∑i=1(⌊k√x+1ai⌋−⌊k√xai⌋).Each term in the above summation is equal to 1 if (x+1)/ai is a perfect kth power and equal to 0 otherwise. However, if two terms were equal to 1, then (x+1)/ai and (x+1)/aj would both be perfect kth powers for some 1≤i<j≤m. Hence, their quotient ai/aj would be a kth power of a rational number, impossible. Thus, at most one term in the summation is equal to 1 and both (⋆) and (†) follow. Now, by definition, fm(am)=0 and am+1 is the minimal x>am such that fm(x)=1. Thus, (⋆) implies that fm(x)=0 for all x∈[am,am+1) and fm(am+1)=1. Then f(am+1)≠f(am+1−1), so according to (†),am+1/an is never the kth power of a rational number for m+1>n≥1, completing the induction. ◼ _________________________________________________________________________________________________________________ Back to the problem at hand, suppose by way of contradiction that am<p<am+1 for some prime p and m∈N. Then as p∈(am,am+1), it follows from the above that fm(p)=fm(p−1)=0. Thus by (†),p/an is the perfect kth power of a rational number for some 1≠n≤m. However, this is clearly impossible since p∤ due to p > a_m \ge a_n and therefore the exponent of p in p / a_n is not a multiple of k. This contradiction completes the proof. \square
14.02.2017 15:47
Hmm... Interesting So we get for every natural number n there is unique i,j that n=a_{i}j^{k}
17.03.2020 08:01
We claim a_m is the m'th k'th power free number. We induct on m, with m=1 clear. Suppose a_1,\ldots,a_{m} is the sequence of k'th power free numbers. We know when x=a_m, the LHS and RHS are equal by induction. Notice that if a_m+1 is k'th power free, then the LHS increases by 1, while the RHS increases by 2; 1 since we have added one more term, and 1 since one of the existing terms increase from what they were at x=a_m (note that it increases exactly by 1 since every number can be uniquely written as a k'th power times a k'th power free number). After this, at each step where we don't have a k'th power free number, both the LHS are RHS will increase by 1. We can keep continuing in this logic, which means we know that unless a_{m+1} is divisible by some k'th power, the LHS and RHS cannot be equal. This process will only stop when a_{m+1} is k'th power free; in that case, the LHS will increases by 1 and the RHS will stay the same as it was with x=a_{m+1}-1. This completes the induction. Obviously, primes are k'th power free, so we are done.
21.07.2020 06:55
Weird problem. For positive integers u and v, let f_u(v) be the number of integers m such that 1\le m\le u and v/a_m is a perfect kth power. Note that for all n, a_{n+1} is the smallest integer solution to x=1+\sum_{i=a_n+1}^{x}f_n(i). \textbf{Claim: } a_n is the nth integer that is kth-power free. \textbf{Proof: } Induct on n, the base case being clear. Suppose the numbers a_1,a_2,\dots,a_i are the first i positive integers that are kth-power free. This implies that for all integers x>a_i, we have f_i(x)\in\{0,1\}. Hence, by our observation above, a_{i+1} is the smallest integer x greater than a_i for which f_i(x)=0. But this implies that a_{i+1} is the next kth-power free integer, completing the induction. \blacksquare The problem statement is a natural corollary of our above claim.
01.10.2020 05:08
I claim that for each positive integer k \geq 2, the sequence a_i is the increasing sequence of kth power free positive integers. We will use proof via induction on n for fixed k. The base case of n = 1 is clear; a_1 = 1. Next, for the inductive hypothesis, suppose that a_1 < a_2 < \ldots < a_m are the m smallest kth power free positive integers. We need to show that a_{m+1} is the next largest kth power free positive integer. Consider the equationx = 1 + \left\lfloor\sqrt[k]{\frac{x}{a_1}}\right\rfloor + \ldots + \left\lfloor\sqrt[k]{\frac{x}{a_n}}\right\rfloor. If x = a_m + 1 is k-th power free, then from x = a_m, the LHS increases by 1 and the RHS by 2, one from one new term and one from an already existing term. If x = a_m + 1 is not kth power free, then the LHS and RHS similarly both increase by 1. This implies that a_m + 1 is the next kth power free positive integer, as desired. \square Since all primes are kth power free for all k \geq 2, we are done. \blacksquare
.
06.12.2020 06:31
02.01.2021 23:23
I claim the sequence a_1, a_2, \dots is exactly the sequence of integers not divisible by any k-th power besides 1; call these integers k-free. Induct with base case obvious; assume a_1, a_2, \dots , a_m are the m smallest k-free integers, and we show a_{m+1} is the next smallest one. Denote f(x)=1+\displaystyle\sum\limits_{i=1}^{m} \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor Note f(x+1)-f(x) is equal to the number of a_i with 1 \le i \le m such that \frac{x+1}{a_i} is a k-th power. If x+1 is k-free then this is zero. Otherwise, since the a_i are k-free, there is exactly one such a_j satisfying the condition. Since f(a_m) is clearly equal to a_m+1, we get a_{m+1} must be the next smallest k-free integer as desired.
04.10.2023 02:23
Let f(x) := 1+\displaystyle\sum\limits_{i=1}^{m} \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor. Note that f(x)-f(x-1) is the number of 1 \le i \le m such that \sqrt[k]{\tfrac{x}{a_i}} is integral. Thus, f(x)-f(x-1)=0 if and only if x is k-free, so inductively we have that a_n is the nth integer which is k-free, as desired.
12.11.2023 16:47
wait f(x+1) - f(x) is a thing oops In fact, we have the following characterization of a_n: Claim: a_n is the n^{th} k-free integer, that is the n^{th} integer that is not divisible by any perfect k^{th} power. (This is clearly sufficient.) Proof. Induct, base case n = 1 with a_1 = 1 and a_2 = 2. Let f(x) = 1 + \sum_{i=1}^{n-1} \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor. Note that as we increase f(x) from a_n to a_{n+1} (the next integer that is k-free), f(x) increases by 1 and x increases by 1 until we hit a_{n+1} - as x is not k-free, there exists a unique representation \sqrt[k]{x} = b_x\sqrt[k]{c_x} where c_x is k-free, and thus the term \left \lfloor \sqrt[k]{\frac{x}{c_k}} \right \rfloor in the definition of f(x) will increase by 1, and all others will remain the same as in the definition of f(x-1). However, at x = a_{n+1}, f(x) does not increases while x increases by 1, so x will "catch up" to f(x) and thus f(x) = x, while all numbers smaller than x do not have this property. This completes the induction and we're done. \square
22.12.2024 01:52
Fix k \ge 2, we provide the following characterization for a_i which implies the problem. Lemma. a_i is the increasing sequence of the non k-th powers. Proof. This is straightforward. \Box For concreteness, we provide a small chart \begin{array}{c|cccccccccc} & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & \\ \hline 2 & 1 & 2 & \color{red}3 & \color{red}5 & 6 & 7 & \color{red}8 & \color{red}10 & \\ \hline 3 & 1 & 2 & 3 & 4 & 5 & 6 & \color{red}7 & \color{red}9 & \\ \end{array} Where the numbers painted in red are consecutive to some perfect power that are skipped in the cases k=2 and k=3.