Message96190
'''
This brute [possibly a] solution to
http://projecteuler.net/index.php?section=problems&id=159
causes segmentation fault.
$ p3 # an AMD 64 bit build.
Python 3.1.1 (r311:74480, Oct 2 2009, 12:29:57)
[GCC 4.3.3] on linux2
Type "help", "copyright", "credits" or "license" for more
information.
>>>
The block between "load_primes" and "print(result)" can be written
as a single statement using various comprehensions. sum(max(...))
The program does not seg-fault this way, but the result was wrong.
I unrolled the code to fix my algorithm, disclosing the segmentation
fault.
'''
import functools
import operator
import itertools
import array
PrimeQ = Primes = 'use load_primes(n) function'
def load_primes(n):
global PrimeQ,Primes
PrimeQ = sieve(1+n)
Primes = array.array('L',(i for (i,Q,) in enumerate(PrimeQ) if Q))
def sieve(n):
a = array.array('b',(True,))*n
a[0] = a[1] = False
for (i,j) in enumerate(a):
if j:
for k in range(i**2,n,i):
a[k] = False
return a
def PrimeRange(a):
'''
see "load_primes"
'''
n = 1+int(a**(1/2))
for p in Primes:
if n < p:
raise StopIteration
yield p
def PrimeFactor(a):
'''
see "load_primes"
>>> load_primes(30)
>>> print([PrimeFactor(x)for x in (6,7,)])
[[2, 3], [7]]
'''
if (a < len(PrimeQ)) and PrimeQ[a]:
return [a]
for p in PrimeRange(a):
(q,r,) = divmod(a,p)
if not r:
return [p]+PrimeFactor(q)
return [a]
def product(a):
return functools.reduce(operator.mul,a,1)
def digital_root(n):
while 9 < n:
n = sum(map(int,str(n)))
return n
def partition(L, chain=itertools.chain):
'''
python recipe by Ray Hettinger
'''
s = L
n = len(s)
first, middle, last = [0], range(1, n), [n]
return [[L[a:b] for (a,b) in zip(chain(first, div), chain(div,
last))]
for i in range(n) for div in itertools.combinations(middle,
i)]
load_primes(1000)
s = 0
for n in range(2,10**6):
factorizations = [
[product(p)for p in group]for group in
partition(PrimeFactor(n))]
mx = 0
for factorization in factorizations:
digital_roots = tuple(map(digital_root,factorization))
sdr = sum(digital_roots)
mx = max(mx,sdr)
s += mx
print('result!',s) |
|
Date |
User |
Action |
Args |
2009-12-10 02:21:10 | LambertDW | set | recipients:
+ LambertDW |
2009-12-10 02:21:10 | LambertDW | set | messageid: <1260411670.47.0.11581679094.issue7466@psf.upfronthosting.co.za> |
2009-12-10 02:21:07 | LambertDW | link | issue7466 messages |
2009-12-10 02:21:05 | LambertDW | create | |
|