「ちょうど \(3\) つのレピュニットの和として表せる整数」は、\( a \ge b \ge c \ge 0\) なる \((a, b, c)\) を用いて \(a - b\) 個の '1'、\(b - c\) 個の '2'、\(c +1\) 個の '3' をこの順に並べてできる数として一意的に表せ、それらの大小は組 \((a, b, c)\) の辞書式順序による大小と一致します。ところでこの順序で \((a, b, c)\) よりも小さな組の個数は

\[ \frac{a (a + 1) (a + 2)}{6} + \frac{b(b+1)}{2} + c \]

ですから \((a, b, c)\) をそれぞれ線形探索することで、\(O( N^{1/3} )\) 時間で解くことができます。（出力の長さが \(\Theta( N^{1/3} )\) のため、出力時間を含めるとこれが定数倍を除いて漸近的に最速です。）