Prove that: there exists a positive constant $K$, and an integer series $\{a_n\}$, satisfying: $(1)$ $0<a_1<a_2<\cdots <a_n<\cdots $; $(2)$ For any positive integer $n$, $a_n<1.01^n K$; $(3)$ For any finite number of distinct terms in $\{a_n\}$, their sum is not a perfect square.
Problem
Source: 2013 China TST Quiz 2 Day 1 P2
Tags: limit, modular arithmetic, quadratics, number theory proposed, number theory
02.04.2013 16:03
a solution not mine let p be a prime satisfy $\ p^{\frac{2}{p}} \le1.01$ let $\ K=p^3$ $\ a_{np+i}=(ip+1)p^{2n-1}$ $0\le i\le p-1$
05.04.2013 21:20
This is similar to duanby's solution. Let $p$ be a prime such that $p^{2/p} \le 1.01$. Clearly this exists since $\lim_{p \to \infty} p^{2/p} = 1$. Note that $a_i = p^{2i-1}$ works due to any sum of terms have odd $p$-adic evaluation, however this does not satisfy the exponential bound. This motivates setting $v_p(a_i)$ as odd numbers. Define $a_{np + k} = p^{2n-1}b_k$ for $k=1,2,...,p$ and $b_1,b_2,...,b_k$ are positive integers not divisible by $p$. If we make the $b_i$ equivalent modulo $p$ we have that $v_p$ of the sum of any subset of $a_{np+1}, ..., a_{np + p}$ is exactly $2n-1$ unless we include all of them. Thus condition 3 is satisfied already for all sequences $b_i$ whenever we do not select terms such that the $p$ terms with lowest index in the sum are $a_{np+1}, ..., a_{np+p}$. OK, so we are motivated to set $b_k = kp + z$ for some fixed positive integer $z$. Note that then $\sum_{i=1}^p b_k = pz + \frac{p^2(p+1)}{2}$ so it follows that \[\sum_{i=1}^p a_{np+i} \equiv p^{2n}z \pmod{p^{2n+1}}\] Thus set $z$ as a quadratic nonresidue modulo $p$ and we get the sum of terms is not a square modulo $p^{2n+1}$. It follows the sum of terms is not a square. Set $K$ as a large integer ($p^{9001}$ works) so we are done.
02.04.2015 23:05
Here is an alternate solution my friend and I came up with: Let $ p $ be a prime (that we will choose later) and let $ r $ be the largest integer that satisfies $ r^2 + r < 2p. $ Define $ a_{rn + k} = kp^{2n + 1} $ for all nonnegative integers $ n $ and integers $ k \in [0, r). $ It is clear that the highest power of $ p $ that divides any possible sum of the $ a_i $'s is odd, which implies that this sequence satisfies the second condition. Moreover, it is clear that $ a_n = O\left(p^{\frac{2n}{r}}\right) $ which satisfies the third condition when $ p $ is sufficiently large.
22.10.2020 20:28
Solution: We take a prime $p$ such that $p^2 <1.01^p$. Note that such prime numbers exist since the function $f(x) = x^{\frac{2}{p}}$ is strictly decreasing. So now, we will let $m = pi+n$, and let $a_m = a_{pi+n} = p^{2i+1}+ n*p^{2i+2}$. Also, as others showed above, we will let $K = p^3$. But since $p^2 < 1.01^p$, we get that $a_m <p^{2i+3} = (p^2)^m * p^3 <1.01^{pm}*p^3 < 1.01^m*K$. Moreover, it is trivial to see that the sum of every finite subset of this set contains an odd power of $p$, hence, no sum is a perfect square, as claimed. $\square$
16.05.2021 09:16
Probably in the same spirit with the Solutions above. In short, the most accessible way to $\textbf{\textit{not}}$ make perfect squares both $\textit{numerically}$ and $\textit{algebraically}$ is to specify some $q$ so $v_q(\text{the terms})$ is odd. $\color{blue} \rule{4.7cm}{2pt}$ $\color{blue} \diamondsuit$ $\color{blue} \boxed{\textbf{Direct Construction.}}$ $\color{blue} \diamondsuit$ $\color{blue} \rule{4.7cm}{2pt}$ Select $k$ so that \[ (1.01)^k > [k \cdot (k+1)]^2 \]and $q$ prime so that $\dfrac{k(k+1)}{2} < q < k(k+1)$. We Claim that the sequence \[ a_i = bq^{2a+1}, \ \text{for} \ i = ak+b, 1 \leq b \leq k \]works, with $q > \dfrac{k(k+1)}{2}$. $\color{blue} \rule{25cm}{0.2pt}$ It's clear that this sequence satisfies the first condition. We first prove that $\{a_i\}$ satisfies the more tricky and selective third condition. Let $N = a_{i_1}+a_{i_2}+\ldots+a_{i_m}$ for some different indices $i_1,i_2,\ldots,i_m$. Consider the smallest index among them (say $a_i$) and say that \[ v_q(a_i) = 2l+1 \]After this, we can prove that $N$ is in the form $L \cdot q^{2l+1}$ with $q \nmid L$. Indeed, we know that $q^{2l+1} \mid a_{i_j}$ for all $j$, and the terms with exactly $2l+1$ $q$-power contributes exactly $1,2,\ldots,k$ towards the value \[ \dfrac{N}{q^{2l+1}} \equiv \dfrac{a_{i_1}+a_{i_2}+\ldots+a_{i_m}}{q^{2l+1}} \pmod q \]rendering $L \leq \dfrac{k(k+1)}{2}$. This implies that $q \nmid L$. $\color{blue} \rule{25cm}{0.2pt}$ Next, to prove the second statement, we let $K = q^2$. So, we would like to prove the inequality \[ b \cdot q^{2a+1} < (1.01)^i \cdot q^2 \]since $b \leq k$, we can reduce this into \[ q^{2a} < (1.01)^{ak+b} \]Eliminating the bounded $(1.01)^b$ out, it remains to prove \[ q^2 < (1.01)^k \]This is obvious since \[ q^2 < [k \cdot (k+1)]^2 < (1.01)^k \]We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
14.04.2023 16:03
对于某个固定的素数 $p,$ 考虑集合 $A=\left\{p^{2m-1}+r\cdot p^{2m}\mid r\in\{0,1,\cdots ,p-2\},m\in\mathbb Z_+\right\}.$ 我们证明 $A$ 中任意有限多个不同元素之和不是完全平方数$.$ 事实上$,$ 设这些元素中形如 $p^{2m_t-1}+r\cdot p^{2m_t}$ 的有 ${s_i}$ 个$,$ 其中 $1\leq t\leq l,1\leq m_1< m_2<\cdots <m_l.$ 因为 $r\in\{0,1,\cdots ,p-2\},$ 有$1\leq s_t\leq p-1.$ 这些元素的和 $S=p^{2m_1-1}\left(s_1+pH\right),$ 其中 $H\in\mathbb Z.$ 因为 $p\nmid s_1,$ 所以 $p^{2m_1-1}||S,$ 从而 ${S}$ 不是完全平方数$.$ 将 ${A}$ 中元素从小到大排列为 $a_1<a_2<\cdots.$ 我们证明当 ${p}$ 充分大时$,\exists K,a_n<K\cdot(1.01)^n.$ 事实上$,$ 设 $a_n=(k-1)(p-1)+r,$ 其中 $k\in\mathbb Z_+,0\leq r\leq p-2.$ 则 $a_n=a_{(k-1)(p-1)+r}=p^{2k-1}+r\cdot p^{2k}<p^{2k+1}=p^{\frac{2(n-r)}{p-1}+3}\leqslant p^3\cdot\left(p^{\frac{2}{p-1}}\right)^n.$ 因为 $\lim_{n\to +\infty}n^{\frac 2{n-1}}=1,$ 因此存在充分大的 ${p}$ 满足 $p^{\frac{2}{p-1}}<1.01.$ 此时取 $K=p^3$ 即可$.\blacksquare$