All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Power of two (Posted on 2010-05-12) Difficulty: 4 of 5
Given a sequence of of natural numbers a1, a2, a3, ... such that a1 is not a multiple of 5 and a(n+1)=a(n)+(the last digit of a(n)).

Prove that this sequence contains infinitely many integer powers of 2.
Ex: 33,36,42,44,48,56,62, 64,....128,.....256 etc

See The Solution Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Proof. Comment 1 of 1
1.  only a1 can be odd.   a2,... will always be even.
2.  we only need to consider sequences starting with an even.
3.  no number in a sequence ever ends in zero.
4.  any sequence increases

5.  any starting number ends up becoming one of two sequences:  one has a1=2 and the other has a1=6.

proof:
the last digit of the sequence with a1=2 follows the cycle 2,4,8,6
call this sequence X
the last digit of the sequence with a1=6 follows the cycle 6,2,4,8
call this sequence Y
each cycle advances increases by 20, they do not contain the same number and they don't miss any even numbers (except those ending in 0)

6.  what is left to prove is that sequences X and Y each contain infinitely many powers of 2.

Looking closer at the digit in the tens place of the sequences.
With sequence X if the last digit is 2, 4 or 8 the tens place is even, odd if the last is 6.
With sequence Y if the last digit is 6 the tens place is even, odd if the last is 2,4,8.

Looking at the powers of 2.
The last digit cycles 2,4,8,6.
If the last digit is 4 or 8 the tens place is even, odd if the last is 2 or 6.

Specifically the powers of 2 cycle as follows
Ends in 2, 10s place is odd.  Sequence Y contains it.
Ends in 4, 10s place is even.  Sequence X contains it.
Ends in 8, 10s place is even.  Sequence X contains it.
Ends in 6, 10s place is odd.  Sequence X contains it.

Therefore,
If a sequence becomes sequence X it will contain 3/4 of the powers of 2 higher than a1.
If a sequence becomes sequence Y it will contain 1/4 of the powers of 2 higher than a1.


  Posted by Jer on 2010-05-12 15:26:52
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information