wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Adding to a power of 2
        
(Message started by: Barukh on Mar 14th, 2013, 12:04am)
Title: Adding to a power of 2
Post by Barukh on Mar 14th, 2013, 12:04am
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?

[hide]I am not sure such an algorithm exists...[/hide]

Source: Konstantin Knop.
Title: Re: Adding to a power of 2
Post by towr on Mar 14th, 2013, 11:31am
[hide]I don't believe there are solutions for odd powers of 2, so that would rule out 22013[/hide]
Title: Re: Adding to a power of 2
Post by Barukh on Mar 14th, 2013, 11:06pm

on 03/14/13 at 11:31:29, towr wrote:
[hide]I don't believe there are solutions for odd powers of 2, so that would rule out 22013[/hide]

Proof?
Title: Re: Adding to a power of 2
Post by towr on Mar 14th, 2013, 11:17pm
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.
Title: Re: Adding to a power of 2
Post by Barukh on Mar 14th, 2013, 11:28pm

on 03/14/13 at 23:17:48, 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. [hide]I believe I've got a proof.[/hide]
Title: Re: Adding to a power of 2
Post by Grimbal on Mar 15th, 2013, 10:08am

on 03/14/13 at 23:28:01, Barukh wrote:
Correct. [hide]I believe I've got a proof.[/hide]


Fermat played the same trick.
Title: Re: Adding to a power of 2
Post by Barukh on Mar 17th, 2013, 10:49am

on 03/15/13 at 10:08:13, Grimbal wrote:
Fermat played the same trick.

It took me some time to understand the meaning of this remark. :D

Here's my departure from Fermat: [hide]mod-3[/hide]  
Title: Re: Adding to a power of 2
Post by towr on Mar 17th, 2013, 11:32am
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..
Title: Re: Adding to a power of 2
Post by Barukh on Mar 17th, 2013, 11:29pm
Ok. So, that settles the 22013 case (and infinitely many others).

What about 22014?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board