- All Contests
- ProjectEuler+
- Project Euler #169: Exploring the number of different ways a number can be expressed as a sum of powers of 2.
- Discussions

# Project Euler #169: Exploring the number of different ways a number can be expressed as a sum of powers of 2.

# Project Euler #169: Exploring the number of different ways a number can be expressed as a sum of powers of 2.

+ 2 comments My math sucks but I still figure out how to do this. Search Stern's Diatomics Series and try to understand it. For those friends who have timeout problem in python, try to build up a dictionary and extend it as far as you can(remember dic[2**N] = 1 for diatomic series) and add few more other elements like dic[3] = 2 or dic[5] = 3. Recursively use the function and remember to update your dic everytime(important, otherwise timeout). You should see that you program solve all cases in seconds.

+ 6 comments How would you do this in a language like C++, where there is no simple way to store an integer value of 10^27? Please advise.

+ 3 comments I was wondering should the

fn(10) be 12 like below

I dont understand what I am doing wrong here

+ 0 comments Python: just figure out // is floor division and / is float division. When n are very large, / will round your result and // will result in integer. Try the following code to see the difference print(10 ** 25 / 2, 10 ** 25 // 2)

+ 0 comments Can be solved more efficiently by dynamic programming. https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

Sort 29 Discussions, By:

Please Login in order to post a comment