Project Euler – Powers of Two

Problem 686 has a bit of a cryptic explanation:

Maybe that’s done on purpose because the math behind the challenge is not very complicated. But I’ll get back to that in a minute.

Problem 686 is all about the powers of two:

21 = 2
22 = 4
23 = 8
24 = 16


Some of these powers will start with “123…” For example 290 = 1.23794003928538e27.
This is actually the first power of two having that exact property.

Unfortunately, it is not the first number you have to find, but the 678919th one.
And just calculating powers of two is definitely not an option. So, what’s the “trick” here?

If I had payed closer attention to my calculator, I would have been on track right from the start.
As my binary friend does not show me a big number like 1237940039285… but 1.23794003928538e27 instead.
A base of 1.23 is small enough to handle. I just have to figure out how to deal with the exponential part.

If I just had…

In the end I was stuck on some “pattern” I discovered regarding the rise of the exponent, and had to ask on math.stackexchange.com for help. Just waiting to get insulted for my sheer stupidity and lack of basic math skills.

Instead, I received two very nice responses, which you can find here.

The coding itself was just a couple of lines.

So, what are the key lessons learned?

1. Keep reading the problem and play with the given examples. You will figure it out!
2. When dealing with large numbers, listen to your calculator. It tells you perfectly how to handle them.
3. Don’t be shy, just ask for help.You will actually learn something. Otherwise you might be stuck forever.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s