n=a_1^2+a_2^4+a_3^8+\ldots+a_k^{2^k}

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

n=a_1^2+a_2^4+a_3^8+\ldots+a_k^{2^k}

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Estonia TST 2023

The post below has been deleted. Click to close.

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

170 posts

#1 h Aug 3, 2023, 9:49 AM

Y by

For any natural number $n{}$ and positive integer $k{}$ , we say that $n{}$ is $k-good$ if there exist non-negative integers $a_1,\ldots, a_k$ such that $n=a_1^2+a_2^4+a_3^8+\ldots+a_k^{2^k}.$ Is there a positive integer $k{}$ for which every natural number is $k-good$ ?

Z K Y

The post below has been deleted. Click to close.

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

381 posts

Davsch

#2 h Aug 3, 2023, 10:37 AM

Y by

The answer is no. Assume such a $k$ exists and let $N$ be a large integer. Then every number from $\{1,2,\dots,N\}$ can be written as $a_1^2+a_2^4+\dots+a_k^{2^k}$ . Each such representation must have $a_1^2\leq N$ , i.e. $0\leq a_1\leq\sqrt N$ . Hence, there are at most $\sqrt N+1$ choices for $a_1$ . Analogously, there are at most $\sqrt[4]N+1$ choices for $a_2$ , etc.

All in all, this shows that we have at most $\prod\limits_{j=1}^k\left(N^{2^{-j}}+1\right)$ possibilities. Since each number in $\{1,2,\dots,N\}$ must have such a representation, this must be at least $N$ . However, multiplying out all terms shows that the largest power of $N$ which occurs is $N^{\frac 12+\frac 14+\dots+\frac{1}{2^k}}=N^{1-\frac{1}{2^k}}$ . Hence, this function grows slower than the function $N\mapsto N$ , resulting in a contradiction if we take $N$ sufficiently large.

Z K Y

The post below has been deleted. Click to close.

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

1188 posts

#3 h Jan 2, 2024, 2:15 AM

Y by

The same result (and proof idea) holds more generally when the exponents $b_1, b_2, \ldots, b_k$ are such that $\sum_{i=1}^k \frac{1}{b_i} < 1$ .
(In our case $\sum_{i=1}^{k} \frac{1}{2^i} = 1 - \frac{1}{2^k}$ ).

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a