← 完整题目索引

PROJECT EULER · #0175

分数与二的幂之和

Fractions and Sum of Powers of Two

仅题目 · 已解决原题 ↗

定义 f(0)=1f(n) 为将 n 写为 2 的幂总和的方法数,其中幂出现次数不超过两次。

例如,f(10)=5,因为 10 有五种不同的表达方式:
10=8+2=8+1+1=4+4+2=4+2+2+1+1=4+4+1+1.

可以证明,对于每个分数 p/q (p>0, q>0),至少存在一个整数 n 使得 f(n)/f(n1)=p/q

例如,f(n)/f(n1)=13/17 的最小 n241
241 的二进制展开为 11110001
从最高有效位到最低有效位读取该二进制数,有 4 个、3 个零和 1 个。我们将字符串 4,3,1 称为 241缩短的二进制扩展

求最小 n 的缩短二进制展开式,其中 f(n)/f(n1)=123456789/987654321

以逗号分隔的整数形式给出您的答案,不带任何空格。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。