21
In [179]: def divisors(n):
...: ret = []
...: for i in range(1, int(n**0.5+2), 1):
...: if n%i == 0:
...: if int(n/i) == i:
...: ret += [i]
...: else:
...: ret += [i, int(n/i)]
...: return list(set(ret))
まずは約数のユニークなリストを出す
In [180]: lst = []
...: for i in range(2, 10000, 1):
...: ami = sum(divisors(i)) - i
...: if i != ami and i == sum(divisors(ami)) - ami:
...: lst += [i, ami]
...: int(sum(lst)/2)
Out[180]: 31626
友愛数のリストを作って合計する
重複するので2で割っておく
22
In [192]: score = 0
...: with open("p022_names.txt") as f:
...: lst = sorted(f.readlines()[0].strip().replace('"', '').split(","))
...: i = 1
...: for name in lst:
...: score += i * sum([ord(x)-64 for x in name])
...: i+=1
...: score
Out[192]: 871198282
Pythonのsortedはアルファベット順に並び替えてくれるのでそのまま使える
あとは文字をforで切り出してordでASCIIコードに変えると簡潔に記述できる
23
In [197]: def isAbundant(n):
...: if n < sum(divisors(n)) - n:
...: return True
...: else:
...: return False
上記の関数でabundant number＝過剰数というのを判定させる
28123 - 12以下のすべてのnに対して、過剰数リストを作る
In [236]: abundantList = []
...: for i in range(12, 28124, 1):
...: if isAbundant(i):
...: abundantList.append(i)
ついで、1から28123までで、過剰数の和で表せるものをユニークなリストにする
ここで、i = j となる12+12=24のような数も含まれるのでrangeの条件式に注意（見事にハマりました）
In [282]: lst = []
...: for i in range(len(abundantList)):
...: for j in range(i, len(abundantList), 1):
...: n = abundantList[i]+abundantList[j]
...: if n < 28123:
...: lst.append(n)
...: lst = sorted(list(set(lst)))
最後に、総数から過剰数の和で表せる数の合計を引けばOK
In [283]: sum([x for x in range(28123)]) - sum(list(set(lst)))
Out[283]: 4179871
24
先に問題を整理する
1th 0123456789 ←下1桁の入れ替えは1!=1パターン（実質入れ替えなし）
2nd 0123456798 ←下2桁の入れ替えは1th, 2ndの2!=2パターン
3rd 0123456879
4th 0123456897
5th 0123456978
6th 0123456987 ←下3桁の入れ替えは1st-6thの3!=6パターン
つまり、n! < 1000 < (n+1)!のところを探せばかなり範囲が絞れる
このとき、n!thの数字は、下n桁が逆転した数値になる
2ndなら8,9が逆転で、3!＝6thなら7,8,9が987になっている
In [291]: [factorial(x) for x in range(2,13,1)]
Out[291]: [2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600]
これより、9! - 10!の間を探せばよい
362,880thは9桁逆転なので、0987654321となる
362,881thは1023456789で、そこから8!=40,320進むとここから下8桁が逆転になる
つまり403,300thは1098765432
362,880thから9!進んだときも、同様に362,880thのうち下9桁が逆転するので、
9!*2thは1987654320となるはず
上記より、1Mthが階乗の和で表して、各桁の状態を推定する
In [313]: factorial(9)*2+factorial(8)*6+factorial(7)*6+factorial(6)*2+factorial(5)*5+factorial(4)+factorial(3)*2+factorial(2)*2
Out[313]: 1000000
つまり、9!x2+8!x6+7!x6+6!x2+5!x5+4!+3!x2+2!+1!=999,999
まず、9!x2thは1987654320, 9!x2+1th = 2013456789
ここから8!x6なので2798654310, 9!x2+8!x6+1th = 2
こうしてみると、各i!の係数aがi+1桁目の数に対応しているとわかる
n番目の数を求めるとき、n!=sigma i! x A(i)と表すと、i=10桁から順番に、i桁目には残った0-9の数字の中でA(i-1)+1番目に小さい数を当てはめていく
In [338]: n=""
...: nums = [0,1,2,3,4,5,6,7,8,9]
...: for i in [2,6,6,2,5,1,2,1,1,0]:
...: n+=str(nums[i])
...: nums.remove(nums[i])
...: int(n)
Out[338]: 2783915460
25
In [341]: a, b = 1, 1
...: i = 2
...: while len(str(b)) < 1000:
...: a, b = b, a+b
...: i+=1
...: i
Out[341]: 4782
関数を作らなくても、Whileで回すだけで十分
26
In [398]: def countDivLoop(n):
...: ans = "0.0"
...: lst = [10]
...: divided = 100
...: while True:
...: a = int(divided / n)
...: ans += str(a)
...: divided = divided % n
...: if divided == 0 or lst.count(divided) > 0:
...: break
...: lst.append(divided)
...: divided *= 10
...: return ans, lst
普通の割り算ではだめなので、割り算のループが発生するまでのリスト長さを図る関数を作成
In [403]: countDivLoop(12)
Out[403]: ('0.083', [10, 4])
In [404]: 1/12
Out[404]: 0.08333333333333333
In [405]: countDivLoop(13)
Out[405]: ('0.0769230', [10, 9, 12, 3, 4, 1])
In [406]: 1/13
Out[406]: 0.07692307692307693
In [407]: countDivLoop(14)
Out[407]: ('0.0714285', [10, 2, 6, 4, 12, 8])
In [408]: 1/14
Out[408]: 0.07142857142857142
うまく動いたので、あとは11 - 1000で最長を求める
In [412]: maxNum = 0
...: maxLst = []
...: for i in range(11, 1000, 1):
...: n, lst = countDivLoop(i)
...: if len(lst) > len(maxLst):
...: maxNum, maxLst = i, lst
...: maxNum, len(maxLst)
Out[412]: (983 982)
27
In [416]: 999**2+999*999+1000
Out[416]: 1997002
この2次関数の最大値は1997002なので、それ以下の素数の列を作っておく
毎回素数判定で割り算するのはもったいないので
In [420]: def PrimeNumList(n):
...: primeNumList = [2]
...: i = 3
...: while primeNumList[-1] < n:
...: for d in primeNumList:
...: if i%d == 0:
...: i+=2
...: break
...: if i**0.5<d:
...: primeNumList.append(i)
...: i+=2
...: break
...: return primeNumList
これに最大値を入れてリスト化しておく
これで愚直に解こうとしたけど、計算が遅すぎて断念
また練り直します
