Project Euler 206

プロジェクトオイラー
http://projecteuler.net/index.php

Q206.
平方すると1_2_3_4_5_6_7_8_9_0の形になる自然数を求めよ。それぞれの"_"は一つの数字。

最後の桁は0、その前は3か7であることがわかるが、そのように6までは一致する自然数を再帰的に生成する。そうして、最後に完全に一致するか調べる。

from math import sqrt
def int_sqrt(n):

    return int(sqrt(n + 0.5))
def is_square(n):

    m = int_sqrt(n)

    return m * m == n
def decode(a):

    n = 0

    for d in reversed(a):

        n = n * 10 + d

    return n
def encode(n):

    a = [ ]

    while n:

        a.append(n % 10)

        n /= 10

    return a
def is_valid(n):

    a = encode(n * n)

    for i in range(10, 20, 2):

        if a[i] != 10 - i / 2:

            return False

    

    return True
def is_valid2(n, i):

    k = i / 2

    return (n / 10 ** i) % 10 == (10 - k) % 10
def gen_digit(n, i = 0):

    if i == 9:

        yield 10 ** 9 + n

    else:

        for d in range(10):

            m = n + d * 10 ** i

            m2 = m * m

            if i % 2 != 0 or is_valid2(m2, i):

                for k in gen_digit(m, i + 1):

                    yield k
for n in gen_digit(0):

    if is_valid(n):

        print n