Author |
Topic: Adding to a power of 2 (Read 4212 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Adding to a power of 2
« on: Mar 14th, 2013, 12:04am » |
 Quote  Modify
|
Devise an algorithm to generate a sequence of natural numbers a1, ..., an with the following properties:
1. a1 = 1.
2. ai+1 = ai+1 or ai+1 = 2ai for i = 1, ..., n-1.
3. a1 + ... + an = 22013.
How efficient such an algorithm may be?
I am not sure such an algorithm exists...
Source: Konstantin Knop.
|
| « Last Edit: Mar 14th, 2013, 1:49am by Barukh » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Adding to a power of 2
« Reply #1 on: Mar 14th, 2013, 11:31am » |
Quote Modify
|
I don't believe there are solutions for odd powers of 2, so that would rule out 22013
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Adding to a power of 2
« Reply #2 on: Mar 14th, 2013, 11:06pm » |
Quote Modify
|
on Mar 14th, 2013, 11:31am, towr wrote:| I don't believe there are solutions for odd powers of 2, so that would rule out 22013 |
|
Proof?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Adding to a power of 2
« Reply #3 on: Mar 14th, 2013, 11:17pm » |
Quote Modify
|
Not yet, no. It's a conjectured based on observation; but if it's true, it may easier to proof than solving the general problem.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Adding to a power of 2
« Reply #4 on: Mar 14th, 2013, 11:28pm » |
Quote Modify
|
on Mar 14th, 2013, 11:17pm, towr wrote:| Not yet, no. It's a conjectured based on observation; but if it's true, it may easier to proof than solving the general problem. |
|
Correct. I believe I've got a proof.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Adding to a power of 2
« Reply #5 on: Mar 15th, 2013, 10:08am » |
Quote Modify
|
on Mar 14th, 2013, 11:28pm, Barukh wrote:| Correct. I believe I've got a proof. |
|
Fermat played the same trick.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Adding to a power of 2
« Reply #6 on: Mar 17th, 2013, 10:49am » |
Quote Modify
|
on Mar 15th, 2013, 10:08am, Grimbal wrote:
Fermat played the same trick. |
|
It took me some time to understand the meaning of this remark. 
Here's my departure from Fermat: mod-3
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Adding to a power of 2
« Reply #7 on: Mar 17th, 2013, 11:32am » |
Quote Modify
|
Yup, that should fit in a margin*). Nice, I wish it had occurred to me.
*) provided it hasn't been glued and cut as poorly as a certain book I'm reading these days, it's missing parts of the words on some pages, nevermind the margin. Eh, cheap paperbacks, whatchagonnado..
|
| « Last Edit: Mar 17th, 2013, 11:33am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Adding to a power of 2
« Reply #8 on: Mar 17th, 2013, 11:29pm » |
Quote Modify
|
Ok. So, that settles the 22013 case (and infinitely many others).
What about 22014?
|
| « Last Edit: Mar 18th, 2013, 1:11am by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print