S 34

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

S 34

G H J

Reveal topic tags

modular arithmetic

Miscellaneous Problems

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

3615 posts

Peter

#1 h May 25, 2007, 12:26 AM • 3 Y

Y by narutomath96, Adventure10, Mango247

Let $S_{n}$ be the sum of the digits of $2^n$ . Prove or disprove that $S_{n+1}=S_{n}$ for some positive integer $n$ .

Z K Y

The post below has been deleted. Click to close.

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

17 posts

#2 h May 25, 2007, 12:26 AM • 3 Y

Y by narutomath96, Adventure10, Mango247

Peter wrote:

Let $S_{n}$ be the sum of the digits of $2^n$ . Prove or disprove that $S_{n+1}=S_{n}$ for some positive integer $n$ .

Let $2^n = a_{m}10^m + a_{m-1}10^{m-1} + ... +a_{1}10 + a_0$
with $a_i$ being integers.
Then $2^n \equiv a_m + a_{m-1} + ... + a_1 + a_0\equiv S(n) (mod3)$
So $S(n+1)\equiv 2^{n+1}\equiv 2.2^n\equiv 2S(n) (mod3)$
So if $S(n+1) = S(n)$ then $S(n)\equiv 0 (mod3)$ and thus $2^n\equiv 0 (mod3)$ which is impossible. Thus $S(n+1)$ cannot equal $S(n)$ for any positive integer $n$ .

Z K Y

The post below has been deleted. Click to close.

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

49 posts

Woett

#3 h Jun 4, 2010, 1:53 PM • 3 Y

Y by narutomath96, Adventure10, Mango247

Analysing the above proof, we see that it shows that $S_{n+a} = S_n$ implies that a is even. While this is clearly enough to proof the impossibility of $S_{n+1} = S_n$ , we might be able to deduce a little more when we work modulo 9 instead of 3. Also, since I guess that the only reason to use powers of 2 in the statement of the problem is to not give away the method of solving, the, imo, ideal proof of the impossibility of $S_{n+1} = S_n$ should (explicitly) show the following: Let $x$ be a given integer with $\gcd(x, 9) = b$ . Let $S(x)$ be the sum of digits of $x$ . Let $y$ be such that $S(x) = S(xy)$ . Then $y \equiv 1 \bmod \displaystyle \left(\frac{9}{b}\right)$ . The fact that both the proof of this and deducing the solution of our initial problem are (almost) trivial, is a good sign. Even more, since $2^a \equiv 1 \pmod 9$ implies $6 | a$ , this shows that $S(2^{n+a}) = S(2^n)$ implies $6 | a$ . And, since $S(2^3) = S(8) = 8 = 5 + 1 + 2 = S(512) = S(2^9)$ , we *can't* do better. Btw, problem S3 (Is there a power of 2 such that it is possible to rearrange the digits giving another power of 2?) becomes an easy consequence of this.

PS, in no way am I trying to criticise the proof of Winged Potato, because his might very well be the easiest and shortest proof of the theorem, I'm just trying to point out the possible merits of a proof written in a more general setting.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a