Author |
Topic: Adding to a power of 2 (Read 4231 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 |
|
|
|
|