range and xrange for 13-digit numbers in Python? [duplicate]

Question

range() and xrange() work for 10-digit-numbers. But how about 13-digit-numbers? I didn't find anything in the forum.

Berndt

Related: https://mcmap.net/q/753014/-python-len-and-size-of-ints – Monologue

What exactly are you trying to do? Why do you need such large ranges? – Monologue

I try to solve euler-project number 15. Maybe I should ask a new question. – Berndt

Brute force is not the way to solve projecteuler #15! You would be waiting a long time - more than a day if you can try 1000000 routes per second – Duodecimo

Yes, you might have trouble with the 60 second project Euler guideline this way. – Behemoth

Do you think software isn't always important to solve the euler-project-questions? – Berndt

You might be surprised how many projecteuler problems can be solved with paper and pencil. #15 is probably a bit hard to do that way unless you really enjoy multiplication by hand, but you can solve it easily with just a basic scientific calculator. – Duodecimo

@gnibbler Cancel factors when solving #15 on paper, and it's quite easy. – Hey

Related: #1482980 – Krissykrista

Answer 1

You could try this. Same semantics as range:

import operator
def lrange(num1, num2 = None, step = 1):
    op = operator.__lt__

    if num2 is None:
        num1, num2 = 0, num1
    if num2 < num1:
        if step > 0:
            num1 = num2
        op = operator.__gt__
    elif step < 0:
        num1 = num2

    while op(num1, num2):
        yield num1
        num1 += step

>>> list(lrange(138264128374162347812634134, 138264128374162347812634140))
[138264128374162347812634134L, 138264128374162347812634135L, 138264128374162347812634136L, 138264128374162347812634137L, 138264128374162347812634138L, 138264128374162347812634139L]

Another solution would be using itertools.islice, as suggested inxrange's documentation

Rusert

Answer 2

No problems with creating the range, as long as you don't want 10**13 elements, e.g.

range(10**14,10**15,10**14)

gives

[100000000000000, 200000000000000, 300000000000000, 400000000000000, 500000000000000, 600000000000000, 700000000000000, 800000000000000, 900000000000000]

Behemoth

This doesn't work with xrange, which only works on 32-bit numbers (on 32-bit systems). – Novah

That's true. My system is 64-bit, so xrange only works up to sys.maxint = 2^63-1 approx 10^19. – Behemoth

Answer 3

if you need enumerating integer try using itertools:

itertools.count(1000000000000)

it should not allocate memory for a list of 1000000000000 elements

Pedestal

Answer 4

On 64-bit Python:

>>> xrange(9999999999999)
xrange(9999999999999)

I would not use range() for a 13-digit number. My poor machine would not be able to hold the resultant list.

Stigmasterol

I get 'OverflowError: long int too large to convert to int' on Python 2.5 if I try this. – Monologue

Interesting. I'm running 2.6 here. Updated. – Stigmasterol

I get OverflowError in 2.6.2. – Piecemeal

Ah, maybe it's because I'm running 64-bit Python then. – Stigmasterol

Answer 5

I don't think it will work. Functions like len expect the result to fit into a 4 byte integer, due to restrictions in the cPython implementation.

In Python 3.0:

>>> range(9999999999999)
range(0, 9999999999999)

It looks like it works, but...

>>> len(range(9999999999999))
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    len(range(9999999999999))
OverflowError: Python int too large to convert to C ssize_t

See here for a related question.

Monologue

Answer 6

range(x) returns a list.Python lists cant contain that many elements. You should use xrange() to iterate through those digits if you need to do trillions of cycles.?

Greenman

Answer 7

range() and xrange() work in recent enough versions of Python; however, in 2.5 or less you'll need to work around the int to long conversion.

def irange(start, stop=None, step=1):
    if stop is None:
        stop = long(start)
        num = 1L
    else:
        stop = long(stop)
        num = long(start)
    step = long(step)
    while num < stop:
        yield num
        num += step

This isn't a complete solution (it doesn't handle negative steps), but it should get you going.

Rest

Answer 8

The difference between range() and xrange() is that the first returns the entire list, while the second returns a generator that generates each number as it is needed. The second one should work for any number, no matter how large.

In Python 3.0, xrange() has disappeared and range() behaves like xrange() did previously.

Popover

Unfortunately xrange (in Python 2.7) doesn't support long integers either. For example: the expression xrange(sys.maxint, sys.maxint+10) raises OverflowError: Python int too large to convert to C long – Penang

Answer 9

For sollution of this problem you don't need such long numbers, because you need only prime factors, you can use square root:

for i in xrange(2, int((n+1)**0.5)):

Hypso