Project Euler 13〜24

数学 Python

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

Q13.
与えられた100個の整数の和の上位10桁

Q14.
コラッツ列が最も長い100万未満の自然数

Q15.
20×20のグリッドの左上から右下へのルートの数

ただの組合せ。

Q16.
21000の各桁の和

Q17.
1〜1000を英語で表したときの総文字数

英語で数を表すことの非効率さがよく分かる。

Q18.
三角形状に並べられた数が与えられたとき、上から下へ降りるルート上の数の和の最大

ルートは2進数で表せる。

Q19.
20世紀内で、月の最初の日が日曜日である回数

Q20.
100!の各桁の和

Q21.
10000より小さい友愛数の総和

Q22.
省略

Q23.
過剰数の総和

Q24.
0〜9の並び替えからなる数を辞書順に並び替えたときの100万番目の数




# Q13

a = [

    37107287533902102798797998220837590246510135740250,

    46376937677490009712648124896970078050417018260538,

    74324986199524741059474233309513058123726617309629,

    91942213363574161572522430563301811072406154908250,

    23067588207539346171171980310421047513778063246676,

    89261670696623633820136378418383684178734361726757,

    28112879812849979408065481931592621691275889832738,

    44274228917432520321923589422876796487670272189318,

    47451445736001306439091167216856844588711603153276,

    70386486105843025439939619828917593665686757934951,

    62176457141856560629502157223196586755079324193331,

    64906352462741904929101432445813822663347944758178,

    92575867718337217661963751590579239728245598838407,

    58203565325359399008402633568948830189458628227828,

    80181199384826282014278194139940567587151170094390,

    35398664372827112653829987240784473053190104293586,

    86515506006295864861532075273371959191420517255829,

    71693888707715466499115593487603532921714970056938,

    54370070576826684624621495650076471787294438377604,

    53282654108756828443191190634694037855217779295145,

    36123272525000296071075082563815656710885258350721,

    45876576172410976447339110607218265236877223636045,

    17423706905851860660448207621209813287860733969412,

    81142660418086830619328460811191061556940512689692,

    51934325451728388641918047049293215058642563049483,

    62467221648435076201727918039944693004732956340691,

    15732444386908125794514089057706229429197107928209,

    55037687525678773091862540744969844508330393682126,

    18336384825330154686196124348767681297534375946515,

    80386287592878490201521685554828717201219257766954,

    78182833757993103614740356856449095527097864797581,

    16726320100436897842553539920931837441497806860984,

    48403098129077791799088218795327364475675590848030,

    87086987551392711854517078544161852424320693150332,

    59959406895756536782107074926966537676326235447210,

    69793950679652694742597709739166693763042633987085,

    41052684708299085211399427365734116182760315001271,

    65378607361501080857009149939512557028198746004375,

    35829035317434717326932123578154982629742552737307,

    94953759765105305946966067683156574377167401875275,

    88902802571733229619176668713819931811048770190271,

    25267680276078003013678680992525463401061632866526,

    36270218540497705585629946580636237993140746255962,

    24074486908231174977792365466257246923322810917141,

    91430288197103288597806669760892938638285025333403,

    34413065578016127815921815005561868836468420090470,

    23053081172816430487623791969842487255036638784583,

    11487696932154902810424020138335124462181441773470,

    63783299490636259666498587618221225225512486764533,

    67720186971698544312419572409913959008952310058822,

    95548255300263520781532296796249481641953868218774,

    76085327132285723110424803456124867697064507995236,

    37774242535411291684276865538926205024910326572967,

    23701913275725675285653248258265463092207058596522,

    29798860272258331913126375147341994889534765745501,

    18495701454879288984856827726077713721403798879715,

    38298203783031473527721580348144513491373226651381,

    34829543829199918180278916522431027392251122869539,

    40957953066405232632538044100059654939159879593635,

    29746152185502371307642255121183693803580388584903,

    41698116222072977186158236678424689157993532961922,

    62467957194401269043877107275048102390895523597457,

    23189706772547915061505504953922979530901129967519,

    86188088225875314529584099251203829009407770775672,

    11306739708304724483816533873502340845647058077308,

    82959174767140363198008187129011875491310547126581,

    97623331044818386269515456334926366572897563400500,

    42846280183517070527831839425882145521227251250327,

    55121603546981200581762165212827652751691296897789,

    32238195734329339946437501907836945765883352399886,

    75506164965184775180738168837861091527357929701337,

    62177842752192623401942399639168044983993173312731,

    32924185707147349566916674687634660915035914677504,

    99518671430235219628894890102423325116913619626622,

    73267460800591547471830798392868535206946944540724,

    76841822524674417161514036427982273348055556214818,

    97142617910342598647204516893989422179826088076852,

    87783646182799346313767754307809363333018982642090,

    10848802521674670883215120185883543223812876952786,

    71329612474782464538636993009049310363619763878039,

    62184073572399794223406235393808339651327408011116,

    66627891981488087797941876876144230030984490851411,

    60661826293682836764744779239180335110989069790714,

    85786944089552990653640447425576083659976645795096,

    66024396409905389607120198219976047599490197230297,

    64913982680032973156037120041377903785566085089252,

    16730939319872750275468906903707539413042652315011,

    94809377245048795150954100921645863754710598436791,

    78639167021187492431995700641917969777599028300699,

    15368713711936614952811305876380278410754449733078,

    40789923115535562561142322423255033685442488917353,

    44889911501440648020369068063960672322193204149535,

    41503128880339536053299340368006977710650566631954,

    81234880673210146739058568557934581403627822703280,

    82616570773948327592232845941706525094512325230608,

    22918802058777319719839450180888072429661980811197,

    77158542502016545090413245809786882778948721859617,

    72107838435069186155435662884062257473692284509516,

    20849603980134001723930671666823555245252804609722,

    53503534226472524250874054075591789781264330331690

]
print str(reduce(lambda x, y: x + y, a))[:10]



# Q14

def collatz(n):

    if (n & 1) == 0:

        n >>= 1

    else:

        n += n + n + 1

    return n
def get_collatz_length(n):

    length = 1

    while n > 1:

        n = collatz(n)

        length += 1

    return length
N = 1000000

max_length = 0

max_n = 0

for n in range(1, N):

    length = get_collatz_length(n)

    if length > max_length:

        max_length = length

        max_n = n
print max_n, max_length



# Q15

def combination(n, m):

    if m == 0:

        return 1

    return combination(n, m - 1) * (n - m + 1) / m
n = 20

m = 20

print combination(n + m, n)



# Q16

N = 1000

print reduce(lambda x, y: x + y, map(int, str(1 << N)))



# Q17

digits = "zero,one,two,three,four,five,six,seven,eight,nine,ten"

d = map(len, digits.split(','))

digits11 = "eleven,twelve,thirteen,fourteen,fifteen"

d.extend(map(len, digits11.split(',')))

digits16 = "sixteen,seventeen,eighteen,nineteen"

d.extend(map(len, digits16.split(',')))

digits20 = "twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety"

d20 = map(len, digits20.split(','))

d100 = len("hundred")

d1000 = len("thousand")
def get_length(n):

    length = 0

    if n == 1000:

        length = d[1] + d1000

    elif n >= 100:

        div = n / 100

        mod = n % 100

        length = d[div] + d100

        if mod > 0:

            length += 3 + get_length(mod)

    elif n >= 20:

        div = n / 10

        mod = n % 10

        length = d20[div-2]

        if mod > 0:

            length += d[mod]

    else:

        length = d[n]

    return length
N = 1000

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

print reduce(add, map(get_length, range(1, N + 1)))



# Q18

a = [

    "75",

    "95 64",

    "17 47 82",

    "18 35 87 10",

    "20 04 82 47 65",

    "19 01 23 75 03 34",

    "88 02 77 73 07 63 67",

    "99 65 04 28 06 16 70 92",

    "41 41 26 56 83 40 80 70 33",

    "41 48 72 33 47 32 37 16 94 29",

    "53 71 44 65 25 43 91 52 97 51 14",

    "70 11 33 28 77 73 17 78 39 68 17 57",

    "91 71 52 38 17 14 91 43 58 50 27 29 48",

    "63 66 04 68 89 53 67 30 73 16 69 87 40 31",

    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"

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

N = len(A)
def sum_route(n):

    sum = A[0][0]

    x = 0

    for y in range(1, N):

        x += n & 1

        n >>= 1

        sum += A[y][x]

    return sum
print reduce(max, map(sum_route, range(1 << (N - 1))))



# Q19

from datetime import date

from itertools import *
def gen():

    for y in range(1901, 2001):

        for m in range(1, 13):

            yield date(y, m, 1)
counter = 0

for d in ifilter(lambda x: x.weekday() == 6, gen()):

    counter += 1

print counter



# Q20

def factorial(n):

    if n == 0:

        return 1

    else:

        return n * factorial(n - 1)
N = 100

print reduce(lambda x, y: x + y, map(int, str(factorial(N))))



# Q21

def prime_candidate():

    yield 2

    yield 3

    p = 5

    while True:

        yield p

        p += 2

        yield p

        p += 4
def factorize(n):

    a = { }

    for p in prime_candidate():

        if p * p > n:

            break

        while n % p == 0:

            add(a, p)

            n /= p

    if n > 1:

        add(a, n)

    return a
def add(a, n):

    if a.has_key(n):

        a[n] += 1

    else:

        a[n] = 1
def d(n):

    a = factorize(n)

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

    def sum(p): return (p ** (a[p] + 1) - 1) / (p - 1)

    return reduce(lambda x, y: x * y, map(sum, a.keys()), 1) - n
def is_amicable(n):

    m = d(n)

    if n == m:

        return False

    return d(m) == n
print reduce(lambda x, y: x + y, filter(is_amicable, range(2, 10000)))



# Q22

def sum(name):

    return reduce(add, map(lambda c: ord(c) - ord('A') + 1, name))
def add(x, y): return x + y
f = open("names.txt")

s = f.read()

f.close()

names = map(lambda e: e[1:-1], s.split(','))

names.sort()

print reduce(add, map(lambda i: (i + 1) * sum(names[i]), range(len(names))))

print sum(names[937])



# Q23

limit = 28123
def prime_candidate():

    yield 2

    yield 3

    p = 5

    while True:

        yield p

        p += 2

        yield p

        p += 4
def factorize(n):

    a = { }

    for p in prime_candidate():

        if p * p > n:

            break

        while n % p == 0:

            add(a, p)

            n /= p

    if n > 1:

        add(a, n)

    return a
def add(a, n):

    if a.has_key(n):

        a[n] += 1

    else:

        a[n] = 1
def d(n):

    a = factorize(n)

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

    def sum(p): return (p ** (a[p] + 1) - 1) / (p - 1)

    return reduce(lambda x, y: x * y, map(sum, a.keys()), 1) - n
def is_abundant(n):

    return n < d(n)
def is_sum(n, a):

    for i in range(1, n / 2 + 1):

        if a[i] and a[n-i]:

            return True

    return False
a = map(is_abundant, range(limit + 1))

print reduce(lambda x, y: x + y,

filter(lambda x: not is_sum(x, a), range(limit + 1)))



# Q24

from itertools import permutations
N = 1000000

counter = 0

for n in permutations(range(10)):

    counter += 1

    if counter == N:

        print "".join(map(str, n))

        break