(12 votes, average: 5.00 out of 5)

## Common Functions and Routines for Project Euler

Helpful tools used to solve problems in Project Euler:

A list of prime numbers from 2 to a billion.
Anytime we deal with problems involving prime numbers we use our file of primes instead of generating them each time they’re called for. This is a reasonable practice since prime generation has been around for centuries.

We also use a module of routines that are used often in solving problems. Euler.py is included as needed. The example below shows typical Python usage:

`from Euler import is_prime, is_perm`

Here is the contents of Euler.py

```from math import sqrt, ceil import random   def factorial(n): return reduce(lambda x,y:x*y,range(1,n+1),1)   def is_perm(a,b): return sorted(str(a)) == sorted(str(b))   def is_palindromic(n): return str(n)==str(n)[::-1]   def is_pandigital(n, s=9): n=str(n);return len(n)==s and not '1234567890'[:s].strip(n)   #by timwarnock; http://www.anattatechnologies.com/q/2011/05/python-fibonacci-list/ class Fibonacci(object): """lazy loading Fibonacci sequence""" def __init__(self): self.fib = [0,1]   def __getitem__(self, n): self._fib(n) return self.fib[n]   def __getslice__(self, start, end): self._fib(max(start,end,len(self.fib))) return self.fib[start:end]   def __call__(self, n): return self.__getitem__(n)   def _fib(self, n): for i in range(len(self.fib), n+1): self.fib.insert(i, self.fib[i-1] + self.fib[i-2]) return self.fib[n]   def sos_digits(n): #sum of squares of the digits of an integer by Po s = 0 while n: s += (n % 10) ** 2 n=n//10 return s   def is_prime(n): if n == 2 or n == 3: return True if n < 2 or n%2 == 0: return False if n < 9: return True if n%3 == 0: return False r = int(sqrt(n)) f = 5 while f <= r: if n%f == 0: return False if n%(f+2) == 0: return False f +=6 return True   # Copyright (c) 2010 the authors listed at the following URL, and/or # the authors of referenced articles or incorporated external code: # http://en.literateprograms.org/Miller-Rabin_primality_test_(Python)?action=history&offset=20101013093632 def miller_rabin_pass(a, s, d, n): a_to_power = pow(a, d, n) if a_to_power == 1: return True for i in range(s-1): if a_to_power == n - 1: return True a_to_power = (a_to_power * a_to_power) % n return a_to_power == n - 1   def miller_rabin(n): d = n - 1 s = 0 while d % 2 == 0: d >>= 1 s += 1 for repeat in range(20): a = 0 while a == 0: a = random.randrange(n) if not miller_rabin_pass(a, s, d, n): return False return True   def trial_division(n, bound=None): if n == 1: return 1 for p in [2, 3, 5]: if n%p == 0: return p if bound == None: bound = n dif = [6, 4, 2, 4, 2, 4, 6, 2] m = 7; i = 1 while m <= bound and m*m <= n: if n%m == 0: return m m += dif[i%8] i += 1 return n   def factor(n): if n in [-1, 0, 1]: return [] if n < 0: n = -n F = [] while n != 1: p = trial_division(n) e = 1 n /= p while n%p == 0: e += 1; n /= p F.append((p,e)) F.sort() return F   def gcd(a, b): if a < 0: a = -a if b < 0: b = -b if a == 0: return b if b == 0: return a while b != 0: (a, b) = (b, a%b) return a   def perm(n, s): if len(s)==1: return s q, r = divmod(n, factorial(len(s)-1)) return s[q] + perm(r, s[:q] + s[q+1:])   def binomial(n, k): nt = 1 for t in range(min(k, n-k)): nt = nt*(n-t)//(t+1) return nt   def catalan_number(n): nm = dm = 1 for k in range(2, n+1): nm, dm = ( nm*(n+k), dm*k ) return nm/dm   def prime_sieve(end): assert end > 0, "end must be >0" lng = ((end // 2) - 1 + end % 2) sieve = [False] * (lng + 1)   x_max, x2, xd = int(sqrt((end-1)/4.0)), 0, 4 for xd in range(4, 8*x_max + 2, 8): x2 += xd y_max = int(sqrt(end-x2)) n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1 if not (n & 1): n -= n_diff n_diff -= 2 for d in range((n_diff - 1) << 1, -1, -8): m = n % 12 if m == 1 or m == 5: m = n >> 1 sieve[m] = not sieve[m] n -= d   x_max, x2, xd = int(sqrt((end-1) / 3.0)), 0, 3 for xd in range(3, 6 * x_max + 2, 6): x2 += xd y_max = int(sqrt(end-x2)) n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1 if not(n & 1): n -= n_diff n_diff -= 2 for d in range((n_diff - 1) << 1, -1, -8): if n % 12 == 7: m = n >> 1 sieve[m] = not sieve[m] n -= d   x_max, y_min, x2, xd = int((2 + sqrt(4-8*(1-end)))/4), -1, 0, 3 for x in range(1, x_max + 1): x2 += xd xd += 6 if x2 >= end: y_min = (((int(ceil(sqrt(x2 - end))) - 1) << 1) - 2) << 1 n, n_diff = ((x*x + x) << 1) - 1, (((x-1) << 1) - 2) << 1 for d in range(n_diff, y_min, -8): if n % 12 == 11: m = n >> 1 sieve[m] = not sieve[m] n += d   primes = [2, 3] if end <= 3: return primes[:max(0,end-2)]   for n in range(5 >> 1, (int(sqrt(end))+1) >> 1): if sieve[n]: primes.append((n << 1) + 1) aux = (n << 1) + 1 aux *= aux for k in range(aux, end, 2 * aux): sieve[k >> 1] = False   s = int(sqrt(end)) + 1 if s % 2 == 0: s += 1 primes.extend([i for i in range(s, end, 2) if sieve[i >> 1]])   return primes```

### sum: Sum an Array

Add the elements of an array and return the sum.

`sub sum { my \$s=0; \$s+=\$_ for @_; return \$s }`

Explanation: Add the elements of an array. Used mostly to make a program more readable.

### dec2bin: Convert a Decimal Number to Binary

Convert decimal (base 10) numbers to binary (base 2)

`sub dec2bin { sprintf "%b", shift) }`

Explanation: Converts a decimal number < 1015 to a binary string.

### min_n & max_n: Minimum & Maximum of a Numerical List

`sub max_n { return (sort {\$a<=>\$b} grep {defined} @_)[-1] }`
`sub min_n { return (sort {\$a<=>\$b} grep {defined} @_)[0] }`

Explanation: Simple routine to accept a list of numerical values and return the minimum/maximum. The technique is fast and simple; sort the list ascending numerically and return the last element [-1] for the maximum or the first element [0] for the minimum. Undefined values are not considered.
For example: print min_n(5,7,0,-8,100) would print -8.

### rotate: Rotate a String Left One Character

`sub rotate { @_[0]=~s/(\d)(\d+)/\2\1/ }`

Explanation: This function accepts a string as its single argument and puts the first character and remaining characters into \1 and \2 as a regular expression. They are then reassembled in reverse order effecting a left-wise rotation.
NOTE: This function DOES change the argument.
For example: print rotate(‘abcdef’) would print bcdefa.

### fact: Calculate Factorial

This hash must first be defined:

`my %fact = (0,1,1,1);`
```sub fact {
my \$n = shift;
return \$fact{\$n} if exists \$fact{\$n};
return (\$fact{\$n} = fact(\$n-1) * \$n)
}
```

Explanation: Memoization helps this recursive function calculate factorials especially for frequent calls in the same program.

## Discussion

### 33 Responses to “Common Functions and Routines for Project Euler”

1. xrange has been removed from Python 3.0 onwards. range has been implemented as xrange now. You may want to update the code

Posted by M | July 23, 2009, 3:31 PM
• Thanks M, I have replaced the xrange statements with range. Thanks for the heads up!

Posted by Mike | September 1, 2009, 5:38 PM
2. Why do you complicate your is_prime function that way? Just do it like that:

def is_prime(n):
for i in range(2, int(n**0.5)):
if n % i == 0: return False
return True

Posted by Klemens Nanni | January 25, 2010, 4:18 AM
• This is a good question. I am a advocate for easy and concise code as are you. But having to check millions of 15 digit numbers for primality in under a minute requires a very fast algorithm.

Here is a program you can run and play with to get a feel for how the algorithms compare. The one we use is much faster and can handle much bigger numbers.

Also, your code returns true for zero (0) as a prime number which is incorrect.

```def is_prime(n):
if n == 2 or n == 3: return True
if n < 2 or n%2 == 0: return False
if n < 9: return True
if n%3 == 0: return False
r = int(n**.5)
f = 5
while f <= r:
if n%f == 0: return False
if n%(f+2) == 0: return False
f +=6
return True

def is_prime2(n):
for i in range(2, int(n**0.5)):
if n % i == 0: return False
return True

n = 8765777656546579;
print is_prime(n);
print is_prime2(n);
```

Posted by Mike | January 25, 2010, 4:48 PM
3. What about the digital sum of a number/string?
I bet, you can do it better, but nevertheless:

def SumOfDigits(n):
nums = list(str(n))
return sum(int(c) for c in nums)

Posted by Klemens Nanni | January 30, 2010, 2:38 PM
• There is a more concise way to solve this problem such as:
def SumOfDigits(n):
return sum(map(int,str(n)))

But your way is easier to understand and just as fast.

Posted by Mike | February 8, 2010, 3:15 AM
4. def fact(n): return reduce(lambda x,y:x*y,range(1,n+1),1)

in python 3 there is no such argument ‘reduce’ anymore.
by the way, could you explain in one or two short sentences how this function works?
I love your doing here and want to understand as much as possible.

Posted by Klemens Nanni | February 20, 2010, 5:43 AM
5. In your ‘is_pandigital’ function there is only the possibilty to proof 9-pandigital numbers.

Here is a version which allows p-pandigital numbers:

def is_pand(n, p):
x = ”
for i in range(1,p+1):
x += str(i)
x += ’0′
return len(str(n)) == p and not x[:p].strip(str(n))

Posted by Klemens Nanni | March 3, 2010, 3:03 PM

1. [...] information is available for is_pandigital and [...]

2. [...] 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485 } Total: 25846868 Check here for more information on palindromic(). Check here for more information on [...]

6. [...] information on the Euler module can be found on the tools page. for [...]

7. [...] More information on the Euler module can be found on the tools page. [...]

8. [...] important to have a decent is_prime() function to achieve a better run [...]

9. [...] More information on the Euler module can be found on the tools page. [...]

10. [...] More information on the Euler module can be found on the tools page. [...]

11. [...] More information on the Euler module can be found on the tools page. [...]

12. [...] More information on the Euler module can be found on the tools page. [...]

13. [...] More information on the Euler module can be found on the tools page. [...]

14. [...] More information on the Euler module can be found on the tools page. [...]

15. [...] More information on the Euler module can be found on the tools page. [...]

16. [...] More information on the Euler module can be found on the tools page. [...]

17. [...] More information on the Euler module can be found on the tools page. [...]

18. [...] More information on the Euler module can be found on the tools page. [...]

19. [...] The gcd function is listed on the tools page. [...]

20. [...] The prime_sieve function is listed on the tools page. [...]

21. [...] More information on the Euler module can be found on the tools page. [...]

22. [...] More information on the Euler module can be found on the tools page. [...]

23. [...] More information on the Euler module can be found on the tools page. [...]

24. [...] The is_palindromic routine is listed on the tools page. [...]