今日は休日だったので子供の面倒をみつつ、Project Eulerをはじめてみた。pythonで解いてる。今日一日で17問程解いたらjapan ranking 200位丁度になった。

ちょっと悩んだのはproblem 10で200万以下の素数の総和を求めるという問題。

最初は素数リストで割り算してみて割り切れるものがなかったら素数リストにappendという単純な方法でやってみたけど、10万くらいで遅くなってしまった。

というわけで篩で。200万までの奇数リストをつくって篩にかけていく。終了条件は最も大きい素数の二乗が200万を超えるかどうか。 で、できた素数のリストをreduceで畳んでprint

numlist = range(3,2000000,2)

def sieve(nums):
    prime_list = [2]
    while 1:
        prime = nums[0]
        prime_list.append(prime)
        if prime * prime > max(nums):
            prime_list = prime_list + nums[1:]
            break
        else:
            nums = [x for x in nums if x%prime != 0]
    return prime_list

print reduce(lambda x,y: x+y, sieve(numlist))

Project Eulerを解いていくには篩とか素因数分解とか組み合わせ発生用の関数を良く使う。

permutation用のジェネレータを見つけた。

def permutations(L):
    if len(L) == 1:
        yield [L[0]]
    elif len(L) >= 2:
        (a, b) = (L[0:1], L[1:])
        for p in permutations(b):
            for i in range(len(p)+1):
                yield p[:i] + a + p[i:]

再帰の中でyieldが使われている場合の動きのイメージがまだピンとこないなぁ。

それから、インデックスの範囲外は空リストが返ってくるからlispとかhaskellっぽく書けるのか。

>>> a = [1,2,3,4]
>>> a[1:]
[2, 3, 4]
>>> a[2:]
[3, 4]
>>> a[3:]
[4]
>>> a[4:]
[]
>>> a[5:]
[]
>>> a[:0]
[]

大きい数字の下位10桁を求める。桁溢れとかそんなんで数字があわなくなるので、欲しい桁以上の数字は捨てる。48(1^1+2^2...1000^1000)と97(大きい素数)はこれで解ける。

Problem 48

sum = 0
for i in range(1,1000):
    sum += reduce(lambda x,y: x*y%10000000000,[i] * i)

print sum % 10000000000

Problem 97

def fact2():
    num = 1
    for i in range(7830457):
        num = num * 2 % 10000000000
    return num

print (1 + 28433 * fact2() ) % 10000000000

25問解いてレベル1

多面体ゲット

pythonのyieldって呼ばれるとメインに戻ってくるようなイメージがあったので再帰の終了条件でyieldがあると気持ち悪かったのだけど、呼び出し側に返されるらしい。

というわけで、やっと理解したので、再帰でyieldをガンガンつかう。

あと、状態の凍結と継続の違いがちょっとあやふやかも。

def permute(item):
    if len(item) == 1: yield item
    for i in range(len(item)):
        for x in  permute(item[:i]+item[i+1:]):
            yield item[i] + x

c=0
for i in permute("0123456789"):
    c += 1
    if c == 1000000:
        print i
        break

1からnまでの連続した数をおのおの一つだけ桁にもつ素数のうち最大のものを探せ

987654321から数を減らしながら素直に見つけていくという安直なコードを書いてサブミット。

import math

def make_primes(n):
    primes = [2]
    nums = range(3,n+1,2)
    while 1:
        prime = nums[0]
        if prime ** 2 > n:
            primes += nums
            return primes
        else:
            primes.append(prime)
            nums = [x for x in nums if x%prime != 0]
    return list(set(primes))

def permute(item):
    if len(item) == 1: yield item
    for i in range(len(item)):
        for x in  permute(item[:i]+item[i+1:]):
            yield item[i] + x

def is_prime(n):
    for j in primes:
        if j*j > n: return True
        if n%j == 0: return False
    return True

if __name__ == "__main__":
    num = 7654321
    primes = make_primes(int(math.sqrt(num)))

    for i in permute(str(num)):
        x = int(i)
        if x%2 != 0:
            if is_prime(x):
                print x
                break

それよりもみずぴー日記のコメントが参考になった。

「各桁の数を足した和が3の倍数ならその数自身も3の倍数」って性質から、素数のPanditital数はあるとすれば1桁か4桁か7桁に絞られるんじゃないでしょうか。

えーなんでなんでー？？？？

３の倍数のANo3をみてなるほどなーと感心した。

連続する素数リスト和が素数になるもののうち、100万までのなかからその並びが最も大きいものを探す。

2,3,5...と和をとって100万までの素数の最大値を超えたところが並びの最大。ここからwindowをずらして和をもとめ素数が見つかったらそれが最大。見つからなかったらwindowサイズを一つ小さくしながら同じ事を繰り返す。

def make_primes(n):
    primes = [2]
    nums = range(3,n+1,2)
    while 1:
        prime = nums[0]
        if prime ** 2 > n:
            primes += nums
            return primes
        else:
            primes.append(prime)
            nums = [x for x in nums if x%prime != 0]
    return primes

def c_sum(i,n):
    return reduce(lambda x,y:x+y,primes[i:i+n+1])

def check_max():
    for i in range(1,len(primes)):
        if c_sum(0,i) > primes[-1]:
            return len(primes[:i])

if __name__ == "__main__":
    primes = make_primes(1000000)
    print "primes are %d" % len(primes)

    cm = check_max()
    print "max windowsize %d" % cm

    max = 0
    pl = cm
    for x in range(1,pl):
        window = pl - x
        print "checking length %d..." % window
        for j in reversed(range(x)):
            num = c_sum(j,window)
            if num in primes:
                max = num
                print num
                print primes[j:j+window+1]
                if max > 0: break
        if max > 0: break

problem 63

n乗したらn桁がなるような数字はいくつあるか?

10以上は考えなくてよいのだけど、一応100まで数えてみた。

count = 0
for i in range(1,100):
    if len(str(i)) > 1: break

    j = 1
    while(1):
        n = i ** j
        if len(str(n)) < j: break
        # print n,i,j
        j += 1
        count += 1

print count

problem 99

対数変換して比較するだけなのでlog10で。

import math
f = open("base_exp.txt")

n    = 0
max  = 0
maxn = 0
for l in f:
    n += 1
    a,b = l[:-2].split(',')
    x = math.log(int(a)) * int(b)
    if max < x:
        max = x
        maxn = n
print maxn,max

これで、level2の六面体に昇進

Triangle, pentagonal, and hexagonal numbersを同時に満たす数をもとめる。

Triangleとhexagonalの関係は一個おきだとすぐにわかるので、数字を比較して小さいほうの数をnextさせるようにしてみた。

def tri():
    i = 1
    while(1):
        yield i*(i+1)/2
        i += 2

def penta():
    j = 1
    while(1):
        yield j*(3*j-1)/2
        j += 1

t = tri()
p = penta()

thn = t.next()
pn  = p.next()

while(1):
    if thn > pn:
        pn  = p.next()
    elif pn > thn:
        thn = t.next()
    else:
        print thn
        pn  = p.next()
        thn = t.next()