第５問「10/16数」問題 解答

「10/16数」問題の解法です。
問題文はこちら。
他の問題の解法は、第１問、第２問、第３問、第４問。

自然数 n を 16 進数のように読んで 10 進数で表したものを F(n) とするときの、
F(n) が n の整数倍となる n を探す問題です。

F(n) を単純にコーディングするだけなら、さほど難しくありません。
n を一つ一つ調べていくコードは次のようになります。

def f(n):
    r, t = 0, 1
    while n > 0:
        r += t * (n % 10)
        n, t = n / 10, t * 16
    return r

def g(m):
    c, n = 0, 1
    while c < m:
        if f(n) % n == 0:
            c += 1
            if c == m: return n
        n += 1

print g(100)

ただこれだと、100 番目の 10/16 数を求めるには長い時間がかかってしまいます。
10/16 数というのがなかなかにレアな存在なためです。

うまく候補を絞り込んで探索する必要があります。
そこでまず、桁数を d とし、n の各桁を a₁a₂・・a_d と表します。
さらに F(n)÷n の値を r とします。

例えば d = 4，r = 3 のとき、a₁, a₂, a₃, a₄ が満たすべき等式は何でしょうか。
それは次の式です。

整理するとこうなります。

a₁ の係数が大きいことがポイントです。
例えば a₁ = 1 としてみます。第 1 項の値は 1096 です。
a₂, a₃, a₄ は 0～9 の自然数ですから、左辺の第 2 項以降は、どれだけ小さくとも －64・9－14・9－2・9 = －720 にしかなりません。第 1 項の値を打ち消すには足りません。
したがって、具体的な a₁, a₂, a₃, a₄ の値を実際に試してみるまでもなく、この等式は決して解を持たないと分かります。

このように、上の桁（a₁）から数字を仮決めして、以下の項でどうやっても等式を成立（辺の値をゼロにする）させられないと分かれば、以降の探索を中断する、という枝刈りのアプローチです。

コード例は以下です。ちょっとややこしいです。
始めに桁数 d と、F(n)÷n の値 r を固定します。
次に深さ優先探索で、上の桁から順に数字を仮決めしながら探索していきます。
探索の途中で、都度、途中までの値と、残りの項で作れる最大の数（配列 u）とを比較し、後者の方が小さければ、残りの項でどうやってもゼロにすることは不可能とみなします。

def search(x, n, i, s, v, u):
    if i == len(v):
        if x == 0: s.add(n)
        return
    if abs(x) > u[i]: return # 探索を打ち切り
    for a in range(10):
        if i == 0 and a == 0: continue
        search(x + v[i] * a, 10 * n + a, i + 1, s, v, u)

def g(m):
    s, d = set(), 1
    while True:
        r = 1
        while True:
            # v[i]: 等式の係数, u[i]: 第i項以下で作れる最大の数
            v, u = [0]*d, [0]*d
            for i in range(d):
                v[i] = r * 10**(d - i - 1) - 16**(d - i - 1)
            if v[0] > 0: break
            for i in range(d):
                u[d - i - 1] = 10 * v[d - i - 1]
                if i != 0: u[d - i - 1] += u[d - i]
            for i in range(d):
                u[i] = abs(u[i])
            search(0, 0, 0, s, v, u)
            r += 1
        if len(s) >= m:
            return sorted(list(s))[m-1]
        d += 1

print g(100)

短時間勝負のコンテストでは、この手の全探索＋枝刈りの問題はほとんど出題されないかもしれません。
ゆえにか結構難しめだったと思います。