Project Euler 169 / ある数を2のべき乗の和で表せる方法の数の探査

問題概略

整数 を 2 のべき乗の和で表すことを考える。ただし各数は高々 2 回しか使ってはいけないものとする。
この表し方の数を とする。 と定義する。

例として を考える。
\begin{align*}
10=1+1+8=1+1+4+4=1+1+2+2+4=2+4+4=2+8
\end{align*}

5 通りの異なる表し方があるので である。
を求めよ。

https://projecteuler.net/problem=169

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

2 進法表示の桁数字に注目

の 2 進法表示を考えます。普通は桁数字に 0 と 1 しか使えませんが，この問題では 2 も使えます。

これはたとえば という部分があったら 1 を右にずらして と変更できるということです。右に 1 があるときはこういう操作はできません。

の偶奇で場合分けして の位の桁数字に注目します。

が奇数のとき の 2 進法表示の右端は 1 で，ここは変更できません。他の桁数字の表し方は の表し方と同じだけあります。

が偶数のとき の 2 進法表示の右端は 0 です。ここを変更しない表し方が 通りあります。

この他に の位の桁数字を減らすかわりに の位の桁数字を 2 に変更する表し方もあります。この部分は正直ちょっとわかりにくく，少し実験が必要でした。

• より
• より

偶数だからといって の位の桁数字は 1 とは限りませんが，この問題の設定では上の位の数字を右にずらしていって の位の桁数字を 1 または 2 にすることができます。これをもう 1 回右にずらすわけです。

この表し方は の表し方と同じ 通りあります。

以上を の形に直して dp すれば解けます。

\begin{align*}
f(n)=\begin{cases}
f\left(\dfrac{n-1}{2}\right)& (\text{$n$が奇数のとき})\\[11pt]
f\left(\dfrac{n}{2}\right)+f\left(\dfrac{n}{2}-1\right)& (\text{$n$が偶数のとき})
\end{cases}
\end{align*}

実装

python で解く

はかなり大きいので python では LRU キャッシュを効かせないと固まったようになります。キャッシュの効果は絶大で，効かせたら瞬時に答えが出ました。

    import time
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(n):
        if n <= 1:
            return 1
        if n % 2 == 1:
            return dp((n - 1) // 2)
        else:
            return dp(n // 2) + dp(n // 2 - 1)
    
    if __name__ == '__main__':
        start = time.time()
        print(dp(10 ** 25))
        elapsed_time = time.time() - start
        print("elapsed_time: {0} [sec]".format(elapsed_time))

mathematica で解く

mathematica でも解きました。こちらもメモ化して高速化しています。計算時間は 0.0007 秒でした。

    f[0] = 1; f[1] = 1;
    f[n_] := f[n] = If[OddQ[n], f[(n - 1)/2], f[n/2] + f[n/2 - 1]];
    ans = f[10^25]