Problem 169

[harshanagesh]

Can anybody post values for f(10^15) and f(10^20) ? I think I know the approach, but somehow my final answer does not seem to be the correct answer.

Thanks

[stijn263]

Problem 169 (View Problem)

It shouldn't be hard to brute force some of the first 10^6 f(n) and check your algorithm against these values

[harshanagesh]

that would be harder than the code that I have written. I didn't write that as I think that would give out the trick underlying this question. how about confirming this ?

f(10^6) = xxxxx
f(10^10) = xxxxx
f(10^15) = xxxxx

[hk]

Why don't you check your value for 10^25 on the website??

[harshanagesh]

I did. Its saying its not correct. This problem IMO, is not hard once you know <snip>. But I am perplexed as to why this simple recursion is not tieing out to the solution...

So, I need something to debug...I did look at the first 15 values (n <= 15) of this series and my code matches it correctly..

[hk]

Did you realise yourself that 10^25>2^63-1??

[harshanagesh]

yes. I am using BigInteger and so that is not an issue. Infact I can compute upto f(10^308) before running into stack overflow. It computes this in under a second. I get f(10^26) as xxxxxxx.
I am not sure where is the problem, until I get another data point to debug against (say f(10^2) which I get as 19)

[harshanagesh]

I solved the problem. Algorithm was correct. but implementation had a bug. I had used double for n and using mod with a double in java breaks down for higher values of n. In fact I could even verify f(n) given in Problem 175 when using n as a double and that threw me off. I changed it to BigInteger and everything works well. It now makes sense that mod of a double may not be appropriate, but can anybody explain why it works for small values of n and does not somewhere for higher values of n ?

Perhaps you can delete this entire thread, if the moderators feel this reveals too much about the solution.

[stijn263]

Congrats

Your problem is probably a precision one, try to avoid using doubles when dealing with integer problems

[hk]

Removed parts that might reveal something.
The real cause of the problen can however be grasped from what remains and is meaningful, so that can be kept.
From the values you gave I concluded that the algoritm was correct but there would be a precision problem. I preferred you to discover that yourself as that is more instructive.
Doubles are accurate to about 52 bits.
Int64 is accurate upto 63 bits.
10^25 exceeds both.

For more information about floating point datatypes see: http://en.wikipedia.org/wiki/Floating_point

[mctrafik]

I'm not understanding the problem correctly.
Number of ways to write a number using powers of two at most twice looks like a sum of two numbers (which in binary representation will contain only powers of two and since there are two numbers each power will only occur at most twice).

This is largely supported by f(10) = 5 since that's how many ways you can write 10 as a sum of two distinct numbers.

Can someone give a counter-example with low numbers like f(20)?

[jaap]

I'm not understanding the problem correctly.
Number of ways to write a number using powers of two at most twice looks like a sum of two numbers (which in binary representation will contain only powers of two and since there are two numbers each power will only occur at most twice).

This is largely supported by f(10) = 5 since that's how many ways you can write 10 as a sum of two distinct numbers.

Can someone give a counter-example with low numbers like f(20)?

Try f(7).

[amidar1]

Before I dive into this problem, I was hoping to get a little clarification on the function f(n).
I see that f(0) is defined to be 1.
What are f(1) and f(2)?
I would think f(1) = 1 (because there is one way to express 1 using powers of 2... namely just 1) and f(2) = 2 (because 2 is 2, and 2 is also 1 + 1). However, I know that "trivial" sums involving only one summand have been excluded from consideration in other Project Euler problems. If we exclude trivial sums, then f(1) = 0 and f(2) = 1.

It may not end up mattering once I get into coding a solution, since 10^25 is not a power of 2. But I figured it would be worthwhile to try to fully understand the problem before trying to solve the problem.

Thanks for any clarification you can provide!

[thundre]

I know that "trivial" sums involving only one summand have been excluded from consideration in other Project Euler problems. If we exclude trivial sums, then f(1) = 0 and f(2) = 1.

Trivial sums aren't excluded here. 1=2⁰ and 2=2¹ count.

[PrimeRing]

This problem has a phrasing error.

It says "sum of integer powers of 2", but that allows you to break up a single 1 as $2^{-1}+2^{-1}$ in any decomposition. I suggest rephrasing it to "nonegative integer powers".

[PrimeRing]

This problem has a phrasing error.

It says "sum of integer powers of 2", but that allows you to break up a single 1 as $2^{-1}+2^{-1}$ in any decomposition. I suggest rephrasing it to "nonegative integer powers".

[hk]

Yep, but the example for 10 shows you that it is not allowed to split up 1 into a sum of negative powers of 2.
So all should be clear when you look at the example.