Reputation:
Project euler problem #255 is quite mathematical. I figured out how it is done for given example. Since I am a newbie in Python, I am not sure how to handle long range values. Below is the solution I have. But how does it work for 10^13 and 10^14?
def ceil(a, b):
return (a + b - 1) / b;
def func(a, b):
return (b + ceil(a, b)) / 2;
def calculate(a):
ctr = 1;
y = 200;
while 1:
z = func(a, y);
if z == y:
return ctr;
y = z;
ctr += 1;
result = sum(map(calculate, xrange(10000, 100000))) / 9e4;
print "%.10f" % result;
This gives 3.2102888889.
Upvotes: 4
Views: 1181
Reputation: 3022
"3.6.3 XRange Type
The xrange type is an immutable sequence which is commonly used for looping. The advantage of the xrange type is that an xrange object will always take the same amount of memory, no matter the size of the range it represents. There are no consistent performance advantages.
XRange objects have very little behavior: they only support indexing, iteration, and the len() function."
maybe ... optimize your floor and ceiling functions? :P
Upvotes: 0
Reputation: 304393
Even a very fast calculation for each number will take too long. To satisfy the 1 minute rule you'd need to solve/add 1.5 Trillion numbers per second.
I think there must be a way to compute the result more directly.
Upvotes: 1
Reputation:
90,000,000,000,000 is a lot of numbers to check, I tried checking every millionth number and thought the average would be close enough, but to no avail.
Upvotes: 0
Reputation: 223072
Don't use map
. It generates a big list in memory.
Don't use xrange
. It is limited to short integers.
Use generators instead.
# No changes on `ceil()`, `func()` and `calculate()`
def generate_sequence(start, stop):
while start < stop:
yield start
start += 1
result = sum(calculate(n) for n in generate_sequence(10**13, 10**14))
print "%.10f" % result;
That will run. But it will take a long time to sum 10**14 - 10**13 = 90,000,000,000,000
results. Maybe there's something else you can do to optimize (hint, hint)
Upvotes: 4