Problem 38 - Project Euler

• Problem 38 - Project Euler

安易に考えましょう．

918273645, which is the concatenated product of 9 and (1,2,3,4,5)と言ってるので求める数は918273645より大きい．ってことで上一桁が9．

91～98までの数の2倍，3倍，4倍あたりまで確認すればわかりますが9xと(1,2,3,…)の連結で9桁にならないので基本数(1をかけるやつ)は2桁ではない，と．同様にして3桁も除外．5桁以上は2倍するだけで9桁超えるので無視．なので基本数は4桁．

9xxxの2倍が5桁なので求める連結数は9xxxと(1,2)の組合せ．

def perm(num, lst):
    if lst == []:
        return [num]
    else:
        new_list = []
        for i in lst:
            buf_list = []
            for j in range(len(i) + 1):
                buf_list.append(i[:j] + num + i[j:])
            new_list.extend(buf_list)
        return new_list

pandigitals = []
sublist = []
for i in range(1,9):
    sublist = perm(str(i),sublist)
sublist.sort()
sublist.reverse()
for i in sublist:
    pandigitals.append("9"+i)

for i in pandigitals:
    base = int(i[:4])
    if base * 2 == int(i[4:]):
        print i
        break

1～8までの順列を降順で並べて，頭に9つけた数を大きい方からチェックしていって，9xxxと(1,2)の組合せがでた段階でbreak．