読者です 読者をやめる 読者になる 読者になる

Problem 38

Project Euler

Problem 38

192を1, 2, 3で掛けてみよう.
   192 × 1 = 192
   192 × 2 = 384
   192 × 3 = 576
積を連結することで1から9のPandigital数 192384576 が得られる.
192384576を 192と(1,2,3)の連結積と呼ぶ.

同じようにして, 9を1,2,3,4,5と掛け連結することで
Pandigital数918273645が得られる.
これは9と(1,2,3,4,5)との連結積である.

整数と(1,2,...,n) (n > 1) との連結積として得られる
9桁のPandigital数の中で最大のものを答えよ.


たいして面白くもないので、
何も考えず安直に実装してみる。

import string

def get_concatenated_product(m, n):
    return int(''.join(map(lambda x: str(m * x), xrange(1, n + 1))))

def is_pandigital(n):
    return 9 == len(set(str(n))) and not '0' in str(n)

def is_9digits_pandigital(n):
    return is_pandigital(n) and len(str(n)) == 9

max_pandigital = 0
for n in xrange(2, 10):
    for m in xrange(1, 10 ** (10 / n)):
        concatenated_product = get_concatenated_product(m, n)
        if concatenated_product >= 10 ** 9:
            break
        if is_9digits_pandigital(concatenated_product):
            print '%d × (%s) = %d' % \
                (m, ', '.join(map(str, range(1, n + 1))), concatenated_product)
            max_pandigital = max(concatenated_product, max_pandigital)
print 'answer is %d' % max_pandigital


実行結果はこちら。

6729 × (1, 2) = 672913458
6792 × (1, 2) = 679213584
6927 × (1, 2) = 692713854
7269 × (1, 2) = 726914538
7293 × (1, 2) = 729314586
7329 × (1, 2) = 732914658
7692 × (1, 2) = 769215384
7923 × (1, 2) = 792315846
7932 × (1, 2) = 793215864
9267 × (1, 2) = 926718534
9273 × (1, 2) = 927318546
9327 × (1, 2) = 932718654
192 × (1, 2, 3) = 192384576
219 × (1, 2, 3) = 219438657
273 × (1, 2, 3) = 273546819
327 × (1, 2, 3) = 327654981
9 × (1, 2, 3, 4, 5) = 918273645
1 × (1, 2, 3, 4, 5, 6, 7, 8, 9) = 123456789
answer is 932718654

0.172 [sec] の計算時間で答えを求めることができました。
求められてもいないのに最大ではない9桁のPandigital数を
全て出力してしまいました。