Permalink
Switch branches/tags
Nothing to show
Find file Copy path
0c2c9ff Jul 10, 2017
1 contributor

Users who have contributed to this file

34 lines (26 sloc) 775 Bytes
#
# Solution to Project Euler problem 169
# Copyright (c) Project Nayuki. All rights reserved.
#
# https://www.nayuki.io/page/project-euler-solutions
# https://github.com/nayuki/Project-Euler-solutions
#
import eulerlib, sys
def compute():
sys.setrecursionlimit(3000)
NUMBER = 10**25
ans = count_ways(NUMBER, NUMBER.bit_length() - 1, 2)
return str(ans)
@eulerlib.memoize
def count_ways(number, exponent, repetitions):
if exponent < 0:
return 1 if number == 0 else 0
else:
result = count_ways(number, exponent - 1, 2)
power = 1 << exponent
upper = power * (repetitions + 2)
if repetitions > 0 and power <= number < upper:
result += count_ways(number - power, exponent, repetitions - 1)
return result
if __name__ == "__main__":
print(compute())