Project Euler 3〜12 - inamori’s diary

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

切りがないので、素直に解いたものはまとめて載せるようにした。
数学的な考察のある解法は別途。

Q3.
600851475143の最大の素因数

Q4.
3桁×3桁で最大の回文数

Q5.
1〜20で割り切れる最小の自然数

Q6.
100までの総和の自乗と自乗和の差

Q7.
10001番目の素数

Q8.
与えられた大きな整数のうち連続する5つの数字の積が最大のもの

Q9.
ピタゴラスの数の組合せで、和が1000ときの積

Q10.
2000000までの素数の和

Q11.
20×20の表の中で5つの連続した積で最大のもの（斜めもOK）

Q12.
三角数で約数の個数が500を超える最小の数



# Q3

N = 600851475143

n = N
def prime():

    yield 2

    yield 3

    p = 5

    while True:

        yield p

        p += 2

        yield p

        p += 4
a = [ ]

for p in prime():

    if p * p <= n:

        while n % p == 0:

            n /= p

            a.append(p)

    else:

        break

a.append(n)
print str(N) + " = " + " * ".join(map(str, a))



# Q4

def is_palindromic(n):

    digits = [ ]

    while n > 0:

        mod = n % 10

        digits.append(mod)

        n = n / 10

    length = len(digits)

    for i in range(length / 2):

        if digits[i] != digits[length-i-1]:

            return False

    return True
def gen_palindrome():

    for x in range(100, 1000):

        for y in range(100, 1000):

            n = x * y

            if is_palindromic(n):

                yield n
print reduce(max, gen_palindrome())



# Q5

import fractions
N = 20

n = 1

for i in range(2, N + 1):

    n *= i / fractions.gcd(i, n)
print n



# Q6

N = 100

def add(x, y): return x + y

sum = reduce(add, range(1, N + 1))

sum_sq = reduce(add, map(lambda x: x * x, range(1, N + 1)))

print sum ** 2 - sum_sq



# Q7

def prime_candidate():

    yield 2

    yield 3

    p = 5

    while True:

        yield p

        p += 2

        yield p

        p += 4
def prime():

    for p in prime_candidate():

        for q in prime_candidate():

            if q * q > p:

                yield p

                break

            if p % q == 0:

                break
N = 10001

counter = 0

for p in prime():

    counter += 1

    if counter == N:

        print p

        break

# Q8
def product(s, N):
n = len(s)
for i in range(n - N + 1):
yield reduce(lambda x, y: x * y, map(int, s[i:i+N]))

a = [
"73167176531330624919225119674426574742355349194934",
"96983520312774506326239578318016984801869478851843",
"85861560789112949495459501737958331952853208805511",
"12540698747158523863050715693290963295227443043557",
"66896648950445244523161731856403098711121722383113",
"62229893423380308135336276614282806444486645238749",
"30358907296290491560440772390713810515859307960866",
"70172427121883998797908792274921901699720888093776",
"65727333001053367881220235421809751254540594752243",
"52584907711670556013604839586446706324415722155397",
"53697817977846174064955149290862569321978468622482",
"83972241375657056057490261407972968652414535100474",
"82166370484403199890008895243450658541227588666881",
"16427171479924442928230863465674813919123162824586",
"17866458359124566529476545682848912883142607690042",
"24219022671055626321111109370544217506941658960408",
"07198403850962455444362981230987879927244284909188",
"84580156166097919133875499200524063689912560717606",
"05886116467109405077541002256983155200055935729725",
"71636269561882670428252483600823257530420752963450"
]

s = "".join(a)
print reduce(max, product(s, 5))



# Q9

def gen(n, m):

    if m == 1:

        yield [ n ]

    else:

        for a in range(1, n / m + 1):

            for b in gen(n - a, m - 1):

                if a < b[0]:

                    yield [ a ] + b
N = 1000

for a in gen(N, 3):

    if a[0] ** 2 + a[1] ** 2 == a[2] **2:

        print reduce(lambda x, y: x * y, a)



# Q10

from itertools import takewhile
def prime_candidate():

    yield 2

    yield 3

    p = 5

    while True:

        yield p

        p += 2

        yield p

        p += 4
def prime():

    for p in prime_candidate():

        for q in prime_candidate():

            if q * q > p:

                yield p

                break

            if p % q == 0:

                break
N = 2000000

def add(x, y): return x + y

print reduce(add, takewhile(lambda x: x < N, prime()))



# Q11

def sequence(A, n, step):

    nrows = len(A)

    ncols = len(A[0])

    for y in range(nrows):

        for x in range(ncols):

            x1, y1 = x + step[0] * (n - 1), y + step[1] * (n - 1)

            if 0 <= x1 and x1 < ncols and 0 <= y1 and y1 < nrows:

                def mult(x, y): return x * y

                def val(i): return A[y+step[1]*i][x+step[0]*i]

                yield reduce(mult, [ val(i) for i in range(n)])
def down(A, n):

    return sequence(A, n, [ 0, -1 ])
def right(A, n):

    return sequence(A, n, [ 1, 0 ])
def right_down(A, n):

    return sequence(A, n, [ 1, 1 ])
def right_up(A, n):

    return sequence(A, n, [ 1, -1 ])
a = [

    "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08",

    "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00",

    "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65",

    "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91",

    "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80",

    "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50",

    "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70",

    "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21",

    "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72",

    "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95",

    "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92",

    "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57",

    "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58",

    "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40",

    "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66",

    "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69",

    "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36",

    "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16",

    "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54",

    "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

]
n = 4

A = [ map(int, s.split(' ')) for s in a ]

print A

p = reduce(max, down(A, n))

p = reduce(max, right(A, n), p)

p = reduce(max, right_down(A, n), p)

p = reduce(max, right_up(A, n), p)

print p



# Q12

def prime():

    yield 2

    yield 3

    p = 5

    while True:

        yield p

        p += 2

        yield p

        p += 4
def factorize(n):

    a = { }

    for p in prime():

        if p * p <= n:

            while n % p == 0:

                n /= p

                add(a, p)

        else:

            break

    if n > 1:

        add(a, n)

    return a
def add(a, p):

    if a.has_key(p):

        a[p] += 1

    else:

        a[p] = 1
def divisors(n):

    i = 1

    while True:

        primes_all = { }

        primes = factorize(i * (i + 1) / 2)

        m = reduce(lambda x, y: x * y, map(lambda x: x + 1, primes.values()), 1)

        if m > n:

            return i * (i + 1) / 2

        i += 1
N = 500

print divisors(N)