Problem38

30分プログラム、その311。Problem38 - ProjectEuler。

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と掛け連結することでPanditital数918273645が得られる. これは9と(1,2,3,4,5)との連結積である.
整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPanditital数の中で最大のものを答えよ.

wikipediaのwikipedia:パンデジタル数では0も含んでいるけれども、ここでは含まないらしい。最初に適当に987654321を答えにいれてみたら、やっぱり違っていた。

使い方

$ time python problem38.py
932718654
python problem38.py  0.30s user 0.09s system 39% cpu 1.006 total

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem38.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/05/26 21:01:03
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

def mul(n,xs):
    return ''.join(map(lambda x: str(n*x),xs))

def isPanditital(n):
    return all([str(x) in n for x in range(1,9)])

def solve():
    max = 0
    for n in xrange(8):
        xs = range(1,n+3)
        i = 0
        while True:
            x = mul(i,xs)
            if len(x) > 9:
                break
            elif isPanditital(x) and max < int(x):
                max = int(x)
            i += 1
    print max

if __name__ == '__main__':
    solve()

参考

• 過去の30分プログラム
• Problem 38 - PukiWiki