0

Attempting to solve this problem:

For a positive number n, define S(n) as the sum of the integers x, for which 1 < x < n and x^3 ≡ 1 mod n.

When n=91, there are 8 possible values for x, namely : 9, 16, 22, 29, 53, 74, 79, 81. Thus, S(91)=9+16+22+29+53+74+79+81=363.

Find S(13082761331670030).

Of course, my code works for S(91) and when attempting to find S(13082761331670030) I get two different errors.

Here is my code:

 def modcube(n):
     results = []
     for k in range(1,n):
            if k**3%n==1:
             results.append(k)
     return results

This produces Overflow error: range has too many items. When I try using 'xrange' instead of 'range' I get an error stating python int too large to convert to c long. I have also just tried several other things without success.

Can anyone point me in the right direction, without telling me exactly how to solve it?
No spoilers please. I've been at it for two days, my next option is to try implementing this in Java since I'm new to Python.

Melody
  • 141
  • 5
  • this may help. the errors you are encountering are the result of numbers too large to store in static types. http://stackoverflow.com/questions/1386604/handling-big-numbers-in-code . hope this is the level of detail you were looking for. – Frank Thomas Mar 21 '13 at 03:32
  • 4
    13 quadrillion is REALLY huge. I suggest that you look for a more efficient way to code your solution by looking for mathematical patterns ;) – Patashu Mar 21 '13 at 03:34
  • 1
    You won't be able to solve this problem using brute force. If you somehow managed to run through one trillion numbers per second, it'd take you three hours. – Blender Mar 21 '13 at 03:37

2 Answers2

2

I think you need to understand two concepts here:

1. integer representation in C and in Python

The implementation of Python you use is called CPython, because it is written using the C language. In C, long integers (usually) are 32 bits long. It means it can work with integers between -2147483647 and 2147483648. In Python, when an integer exceeds this range, it converts them to arbitrary precision integers, where the size of the integer is limited only by the memory of your computer. However, operation on those arbitrary integers (called long integers in Python) are order of magnitude slower than operation on 32 bits integers.

2. The difference between range and xrange:

range produces a list. If you have range(10), it stores the list [0, 1, ... 9] entirely in memory. This is why storing a list of 13082761331670030 items in memory is too mush. Assuming each number is 64 bits, it would need 93 TB of RAM to store the entire list!

xrange produces an iterator. It returns each number one by one. This way, it allows to perform operations on each number of the list without needing to store the entire list in memory. But again, performing calculations on 13082761331670030 different numbers could take more time that you think... The other thing about xrange is that it doesn't work with Python long integers; it is limited (for speed reasons) to 32 bits integers. This is why your program doesn't work using xrange.

The bottom line: Project Euler problems are (more or less) classified by degree of difficulty. You should begin by lower problems first.

Charles Brunet
  • 21,797
  • 24
  • 83
  • 124
1

You wanted hints, not a solution.

Hints:

  1. Consider that the prime factors of 13082761331670030 is equal to the following primes: 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43

  2. Chinese remainder theorem

  3. Just because x^3 ≡ 1 mod n does not mean that there are not other values other than 3 that satisfy this condition. Specifically, prime1 ** (prime2 - 2) % prime2

My Python solution is 86 milliseconds...

dawg
  • 98,345
  • 23
  • 131
  • 206