N |N^N|=|R|

\(0 \lt r\leq 1\) を満たす実数 \(r\) の∞進小数表現を、以下を満たす無限長の正整数列 \(A=(A_1,A_2,\dots)\) のうち以下の条件を満たすもの (一意に存在する) として定義します。

• \(A_i\geq 2~(1\leq i)\)
• \(r=\sum_{i=1}^{\infty}\prod_{j=1}^{i-1}\frac{1}{A_j(A_j-1)}\cdot \frac{1}{A_i}=\frac{1}{A_1}+\frac{1}{A_1(A_1-1)A_2}+\frac{1}{A_1(A_1-1)A_2(A_2-1)A_3}+\cdots\)

• \(\frac{1}{2}=\frac{1}{3}+\frac{1}{3\cdot 2\cdot 2}+\frac{1}{3\cdot 2\cdot 2\cdot 1\cdot 2}+\frac{1}{3\cdot 2\cdot 2\cdot 1\cdot 2\cdot 1\cdot 2}+\cdots\) より、\(\frac{1}{2}\) の∞進小数表現は \((3,2,2,2\dots)\)。
• \(\frac{5}{11}=\frac{1}{3}+\frac{1}{3\cdot 2\cdot 2}+\frac{1}{3\cdot 2\cdot 2\cdot 1\cdot 3}+\frac{1}{3\cdot 2\cdot 2\cdot 1\cdot 3\cdot 2\cdot 2}+\cdots\) より、\(\frac{5}{11}\) の∞進小数表現は \((3,2,3,2,\cdots)\)。

有理数の∞進小数表現は必ず循環節を持ちます。\(q\) の∞進小数表現の循環節の長さを \(f(q)\) とします。 より厳密には、以下の条件を満たすような正の整数 \(p\) の最小値を \(f(q)\) とします。

• \(q\) の∞進小数表現を \(A=(A_1,A_2,\dots)\) とする。命題「ある正整数 \(i_0\) が存在して、\(i\geq i_0\) ならば \(A_{i+m}=A_{i}\)」を真にするような正整数 \(m\) のうち最小のものを \(f(q)\) とする。

正の整数 \(N\) が与えられます。\(\sum_{d=1}^{N}\sum_{n=1}^{d}f(\frac{n}{d})\) を求めてください。