Project Euler 25〜32

プロジェクトオイラー
http://projecteuler.net/index.php

Q25.
フィボナッチ数列で最初に1000桁になるのは何項目か

Q26.
1〜1000の逆数で最も長い循環の周期は

10倍して割り算して余りを得る。これを繰り返して、同じ余りになるまでが周期。

Q27.
n2 + an + b |a| < 1000, |b| < 1000の形でn = 0,1,...で最も長く素数であるaとbの組合せの積

n = 0で素数とn = 1で2以上でまずふるい落とす。

Q28.
1を原点にスパイラル状に自然数を1001*1001個並べたときの、対角線上にある数の和

まず2次元状の配列に自然数をセットする。スパイラルのステップをジェネレータにする。

Q29.
abの形(2 ≤ a ≤ 100, 2 ≤ b ≤ 100)の整数の数

Q30.
桁ごとに5乗して和を取ると元に戻る自然数の和

桁数をNとすると、10N-1 ≥ N95でなければならないからNの上限が決まる。

Q31.
200ペンスを1,2,5,10,20,50,100,200ペンス硬貨で払う場合、何通りあるか

分割数と同じように再帰で。

Q32.
a * b = cで、3つ数をあわせて各桁が1〜9の並び替えになるようなcの総和

cが同じでa,bが違う組合せがあり、それは重複して数えてはいけない。



# Q25
from itertools import takewhile

def fib():
a, b = 1, 1
while True:
yield a
a, b = b, a + b

counter = 0
for f in fib():
counter += 1
if len(str(f)) == 1000:
print counter
break


# Q26
def get_cycle_length(n):
counter = 0
m = { }
mod = 1
while not m.has_key(mod):
m[mod] = counter
counter += 1
mod = mod * 10 % n
return counter - m[mod]

def max_len(x, y):
if x[1] <= y[1]:
return y
else:
return x

N = 1000
a = reduce(max_len, map(lambda n: (n, get_cycle_length(n)), range(1, N)))
print a[0]


# Q27
from itertools import count

def prime_candidate():
yield 2
yield 3
p = 5
while True:
yield p
p += 2
yield p
p += 4

def is_prime(n):
if n < 2:
return False
for p in prime_candidate():
if p * p > n:
return True
if n % p == 0:
return False

def generate_coeff():
for b in range(2, N):
if not is_prime(b):
continue
for a in range(1 - b, N):
yield [ a, b ]

def get_length(coeff):
a = coeff[0]
b = coeff[1]
for n in count(1):
if not is_prime((n + a) * n + b):
return n

def max_length(x, y):
if x[1] < y[1]:
return y
else:
return x

N = 1000
a = reduce(max_length, map(lambda c: [ c, get_length(c) ], generate_coeff()))
print a
print a[0][0] * a[0][1]


# Q28
from itertools import cycle

def step():
x = [ [ 1, 0 ], [ 0, 1 ], [ -1, 0 ], [ 0, -1 ] ]
rep = 0
for i in cycle(range(4)):
if (i & 1) == 0:
rep += 1
for k in range(rep):
yield x[i]

def spiral(N):
A = [ [ 0 for i in range(N) ] for j in range(N) ]
x = N / 2
y = N / 2
s = step()
for n in range(1, N * N + 1):
A[y][x] = n
st = s.next()
x += st[0]
y += st[1]
return A

N = 1001
A = spiral(N)
def add(x, y): return x + y
sum = reduce(add, map(lambda i: A[i][i], range(N)))
sum = reduce(add, map(lambda i: A[i][N-1-i], range(N)), sum)
sum -= A[N/2][N/2]
print sum


# Q29
N = 100
pows = set()
for a in range(2, N + 1):
for b in range(2, N + 1):
pows.add(a ** b)

print len(pows)


# Q30
from itertools import count
from math import log

N = 5

def f(n):
return 10 ** (n - 1) - n * 9 ** N

def calc_max_digits():
for i in count(1):
if f(i) > 0:
return i - 1

def add(x, y): return x + y
def pow(x): return x ** N

sum = reduce(add, filter(
lambda n: reduce(add, map(pow, map(int, str(n)))) == n,
range(2, 10 ** calc_max_digits())))
print sum


# Q31
coins = [ 1, 2, 5, 10, 20, 50, 100, 200 ]

def divide(n, min_c = -1):
if n == 1:
return [ [ 1 ] ]
if min_c == -1:
min_c = n

d = [ ]
for c in coins:
if c == n:
d.append([ c ])
break
if c > n or c > min_c:
break
for a in divide(n - c, c):
if a[-1:][0] <= c:
d.append(a + [ c ])
return d

print len(divide(200))


# Q32
from itertools import permutations
from math import factorial

def partial_perm(m, n):
g = permutations(range(1, m + 1))
fac = factorial(m - n)
for a in g:
yield a[:n]
for i in range(fac - 1):
g.next()

def divide(n):
a = [ ]
while n > 0:
a.append(n % 10)
n /= 10
return a

def join(a):
n = 0
for i in reversed(a):
n = n * 10 + i
return n

def check(a, b):
if a[0] == 1 or a[0] == 5:
return False
if b[0] == 1 or b[0] == 5:
return False
m = join(a)
n = join(b)
p = m * n
if p >= 10000:
return False
c = divide(p)
d = [ False for i in range(10) ]
for i in a:
d[i] = True
for i in b:
d[i] = True
for i in c:
if i == 0 or d[i]:
return False
d[i] = True
return True

s = set()
for a in partial_perm(9, 5):
for i in range(1, 3):
if check(a[:i], a[i:]):
m = join(a[:i])
n = join(a[i:])
s.add(m * n)
print m, n, m * n
print reduce(lambda x, y: x + y, s)