Project Euler 32

32番
パンデジタルといって1から9までの数字を1回ずつ使って掛け算の式を成立させる問題
できたもののイマイチ…

今回は順列を求めるのにitertoolsを使った
またリストやタプルの数字列を一つの数値にするためにreduceを使った
例 reduce(lambda x,y: x*10+y, [1,2,3]) →123

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools

num_list = [1,2,3,4,5,6,7,8,9]
ans = 0
ans_list = []
#積は4桁しかない
#掛けられる数>掛ける数としたとき、掛けられる数は4桁か3桁
for i in [4,3]:
	now_num_list = num_list[:]
	for left_list in itertools.permutations(num_list,i):
		now_num_list = num_list[:]
		for k in left_list:
			now_num_list.remove(k)
		for right_list in itertools.permutations(now_num_list,5-i):
			new_now_num_list = now_num_list[:]
			for k in right_list:
				new_now_num_list.remove(k)
			answer = reduce(lambda x,y:10*x+y,left_list) * reduce(lambda x,y:10*x+y,right_list)
			if sorted(map(lambda x:int(x),list(str(answer)))) == new_now_num_list and not answer in ans_list:
				ans_list.append(answer)
				ans += answer
print ans

Project Euler 30, 31

30番
各桁を5乗して足すと同じになる数を求める
N桁の数の5乗和の最大値は
9^5*N

#!/usr/bin/env python
# -*- coding: utf-8 -*-

summary = 0
for i in range(2,9**5*6):
	right = 0
	left = i
	while left > 0:
		right += (left % 10)**5
		left /= 10
	if i == right:
		summary += i
print summary

31番
1,2,5,10,20,50,100,200ポンド硬貨でちょうど200ポンドは何通りできるか
再帰使うのがやっぱり楽かな

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def count_variety(sum_money,money_list):
	count = 0
	if money_list == [1]:
		return count + 1
	for i in range(0,sum_money/money_list[0]+1):
		new_money_list = money_list[:]
		if sum_money - i*money_list[0] == 0:
			count += 1
		elif sum_money - i*money_list[0] > 0:
			new_money_list.pop(0)
			count += count_variety(sum_money - i*money_list[0],new_money_list)
		else:
			break
	return count

money_list = [200,100,50,20,10,5,2,1]
print count_variety(200,money_list)

Project Euler 28, 29

28番
数字を渦巻状に配置して対角に来る数字の和を求める問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-
summary = 0
for i in range(1,1001+1,2):
	summary += 4*i*i - 6*i + 6
print summary-3

29番
a^bをa,bそれぞれ2~100に変えた時何個違う数字ができるか数える問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-
ans = []
for i in range(2,101):
	for j in range(2,101):
		ans.append(i**j)
print len(set(ans))

どっちも簡単だった

Project Euler 26, 27

26番
最長の循環小数を求める問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-
max_ite = 0
max_d = 0
for i in range(2,1000):
	iterate = 0
	rest = 1
	rest_list = []
	while 1:
		rest = rest * 10 % i
		iterate += 1
		if rest == 0 or rest in rest_list:
			break
		rest_list.append(rest)
	if iterate > max_ite:
		max_ite = iterate
		max_d = i

print max_d

27番
二次式で素数が続く際の係数を求める問題
aは奇数,bは素数という条件のもとブルートフォースで解いたけどなんかもっといい方法ないかなあ

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#aは奇数,bは素数
def f(n,a,b):
	return n * n + a * n + b

def issosu(x):
	for i in range(3,x,2):
		if x % i == 0:
			return False
	return True

def make_b(n):
	b_list = range(2,n)
	b = []
	while b_list != []:
		sosu = b_list[0]
		b.append(b_list[0])
		sub_list = []
		for i in b_list:
			if i % sosu != 0:
				sub_list.append(i)
		b_list = sub_list[:]
	return b

max_len = 0
b_list = make_b(1000)
max_a = 0
max_b = 0
for a in range(-999,1001,2):
	for b in b_list:
		n = 1
		while f(n,a,b) > 0 and issosu(f(n,a,b)):
			n += 1
		if n > max_len:
			max_a = a
			max_b = b
			max_len = n
print max_a*max_b

Project Euler 24, 25

24番
0~9の順列の100万番目を求める問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-

num_list = range(0,10)
#0から数え始める
Order = 1000000
Order -= 1
ans = 0
for i in range(0,10):
	tmp = 1
	for j in range(1,10 - i):
		tmp *= j
	ans = ans * 10 + num_list[Order / tmp]
	num_list.pop(Order / tmp)
	Order = Order % tmp
print ans

25番
1000桁になるフィボナッチ数列の番目を求める問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-

Fn = [1]
Fn_1 = [1]

iterate = 2
while 1:
	C = 0
	save = Fn[:]
	for i in range(0,len(Fn_1)):
		Fn[i] = Fn[i] + Fn_1[i] + C
		C = Fn[i] / 10
		Fn[i] = Fn[i] % 10
	if len(save) > len(Fn_1):
		Fn[len(Fn)-1] += C
		C = 0
	if C > 0:
		Fn.append(C)
	Fn_1 = save
	iterate += 1
	if len(Fn) >= 1000:
		break

print iterate

リストをコピーするには
a = b
じゃなくて
a = b[:]
でやらないとbの値変えた時aの中身も変化してしまう

変数に1000桁入らないんじゃないかと思ってリストでやったけどそんなことなかったみたい。だから

def f(n):
	x = 1
	y = 1
	z = 2
	while 1:
		x,y,z = x+y,x,z+1
		if len(str(x)) >= n:
			break
	return z

print f(1000)

の方が簡単だし速い

Project Euler 22, 23

今回もProject Euler

22番
テキストファイルの名前を並び替えてスコア計算

pythonでテキスト分解するのは結構簡単
sort()もかなり便利

#!/usr/bin/env python
# -*- coding: utf-8 -*-

line = open('names.txt').read()
itemList = line[:-1].split(',')
newitemList = map(lambda x: x.strip(" \" "),itemList)
newitemList.sort()

score = 0
iterate = 0
for item in newitemList:
	iterate += 1
	subscore = 0
	for j in item:
		subscore += (ord(j) - 64)
	subscore *= iterate
	score += subscore

print score

23番
2つの過剰数の和で表せない整数の和

過剰数かどうかは前回の関数を使いまわした
時間は22秒とちょっとかかってしまった...なんかうまい方法ないかなあ

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def yakusu(num):
	row_num = num
	yakusu_list = []
	sosu = 2
	while num != 1:
		sosu_count = 0
		while num % sosu == 0:
			sosu_count += 1
			num /= sosu
		if sosu_count > 0:
			yakusu_list.append((sosu,sosu_count))
		sosu += 1
	insu_wa = 1
	for i in map(lambda x: (x[0]**(x[1]+1)-1)/(x[0]-1),yakusu_list):
		insu_wa *= i
	return insu_wa - row_num

kajyo = []
for i in range(1,28124):
	if i < yakusu(i):
		kajyo.append(i)

kajyo_wa_list = []
for i in kajyo:
	for j in kajyo:
		if i + j < 28124:
			kajyo_wa_list.append(i+j)

print sum(range(1,28124)) - sum(set(kajyo_wa_list))

Project Euler 20, 21

前々から少しずつ解いてきたProject Euler(https://projecteuler.net/)の自分なりの解答をここに残しておく。

20番
100の階乗の各桁の和を求める問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-
ans = [1]
for i in range(1,101):
	C = 0
	for j in range(0,len(ans)):
		ans[j] = ans[j] * i + C
		C = ans[j] / 10
		ans[j] = ans[j] % 10
	while C > 0:
		ans.append(C%10)
		C = C / 10
print sum(ans)

21番
10000未満の友愛数の和を求める問題

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def yakusu(num):
	row_num = num
	yakusu_list = []
	sosu = 2
	while num != 1:
		sosu_count = 0
		while num % sosu == 0:
			sosu_count += 1
			num /= sosu
		if sosu_count > 0:
			yakusu_list.append((sosu,sosu_count))
		sosu += 1
	insu_wa = 1
	for i in map(lambda x: (x[0]**(x[1]+1)-1)/(x[0]-1),yakusu_list):
		insu_wa *= i
	return insu_wa - row_num

def isyuai(num):
	yuai = False
	if num == yakusu(yakusu(num)) and num != yakusu(num):
		yuai = True
	return yuai

ans = 0
MAX = 10000
for i in range(2,MAX):
	if isyuai(i):
		ans += i

print ans

19番までもいつか残しとこう