Project Euler # 255

Question

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.

Answer 1

Python does automatically convert big numbers to its long format, which provides unlimited precision. (At least until memory runs out.)

Answer 2

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)

Answer 3

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.

Answer 4

can any one do it in c or c++.....

Answer 5

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.

Answer 6

3.6.3 XRange Type :

"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