Problem of sum

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Problem of sum

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: CFMO 1.1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

XAN4

#1 h Mar 1, 2025, 12:10 PM

Y by

Prove that for any $2\leq t,$ $t,m\in{\mathbb{Z}},$ there exists infinitely many n which cannot be expressed as $\sum_{i=1}^tx_i^{a_i},$ where $x_i,$ $a_i\in\mathbb Z^+$ and $\forall i,$ $a_i>t.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1484 posts

#2 h Mar 9, 2025, 4:37 PM • 2 Y

Y by MS_asdfgzxcvb, XAN4

Fun intro to density?

Claim: For sufficiently large $n$ , the number of $t$ th powers less than $n$ is more than all numbers less than $n$ which are a $k$ th power for $k > t$ .
Proof: It's equivalent to show that
$2 + \sum_{k=t+1}^\infty \left\lfloor \sqrt[k]{n} \right\rfloor < \sqrt[t]{n}$ and so it thus suffices to show that say
$\sum_{k\ge K}^\infty 2^k \cdot \left\lfloor \sqrt[2^k]{n} \right\rfloor < 0.99 \sqrt[t]{n}$ starting at any sufficiently large $K$ . Then, at which point we can prove that for any $C$
$2^k \cdot \left\lfloor \sqrt[2^k]{n} \right\rfloor < \frac{1}{1434k^2} \sqrt[t]{n} \iff 2^k \cdot a < \frac{1}{Ck^2} a^{2^k/t} \iff 2^k \cdot Ck^2 < a^{2^k/t - 1} \iff 2^{k+1} C k^2 < a^{2^k/t}$ so since $2^{2^k/t} > 2^{k+1} \cdot C \cdot k^2$ holds for all large $k$ the result follows.

The gist of the above is that there are less than $\sqrt[t]{n}$ of the numbers of the form $x_i^{a_i}$ less than $n$ , so summing $t$ copies of these numbers can't cover all numbers less than $n$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a