Project Euler 238 - inamori’s diary

Q238.
省略

まず、一回りの数字の列を作る。頭から足していくと、その数をkとすれば、p(k) = 1となる。その次から足していくと、p(k) = 2となる。kが大きいときは、最初に作った数字の列の和で割ったときのあまりに置き換えればよい。こうしていくとすべてのkについてp(k)が求まる。求まらないときは必ず出てこないことを証明しなければならなかったが、その必要はなかった。



from itertools import count
def encode(n):

    a = [ ]

    while n:

        a.append(n % 10)

        n /= 10

    a.reverse()

    return a
def add_digits(a, n):

    a.extend(encode(n))
def make_string(s0):

    a = [ ]

    add_digits(a, s0)

    s = s0

    while True:

        s *= s

        s = int(s % 20300713)

        if s == s0:

            break

        add_digits(a, s)

    return a
def gen_number(k0, n):

    for k in xrange(k0, n):

        yield k

    for k in xrange(k0):

        yield k
N = 2 * 10 ** 15

s0 = 14025256

a = make_string(s0)

n = len(a)

sum_all = sum(a)

res_all = sum_all

rep = N / sum_all

res = N % sum_all

b = [ 0 ] * ( (sum_all + 15) / 16)

result = 0

for k0 in count():

    if k0 > 0 and a[k0-1] == 0:

        continue

    num = 0

    num_res = -1

    s = 0

    for k in gen_number(k0, n):

        ak = a[k]

        if ak == 0:

            continue

        s += ak

        if s > res and num_res == -1:

            num_res = num

        bit = 1 << (s & 15)

        if (b[s>>4] & bit) == 0:

            b[s>>4] |= bit

            num += 1

    result += (num * rep + num_res) * (k0 + 1)

    res_all -= num

    if res_all == 0:

        break
print result