0%

Problem 558


Problem 558


Irrational base

Let r be the real root of the equation x3=x2+1.
Every positive integer can be written as the sum of distinct increasing powers of r.
If we require the number of terms to be finite and the difference between any two exponents to be three or more, then the representation is unique.
For example, 3=r-10+r-5+r-1+r2 and 10=r-10+r-7+r6.
Interestingly, the relation holds for the complex roots of the equation.

Let w(n) be the number of terms in this unique representation of n. Thus w(3)=4 and w(10)=3.

More formally, for all positive integers n, we have:
n = $\displaystyle \sum_{k=-\infty}^{\infty}$ bkrk
under the conditions that:
bk is 0 or 1 for all k;
bk+bk+1+bk+2≤1 for all k;
w(n) = $\displaystyle \sum_{k=-\infty}^{\infty}$ bk is finite.

Let S(m)= $\displaystyle \sum_{j=1}^{m}$w(j2).
You are given S(10) = 61 and S(1000) = 19403.

Find S(5 000 000).


无理数进制

记r为方程x3=x2+1的实根。
每一个正整数都能表示成r的不同幂的和。
如果我们要求级数只有有限项,而且任意两项的指数至少相差3,这样的表示是唯一的。
例如,3=r-10+r-5+r-1+r2,而10=r-10+r-7+r6
有趣的是,这个关系对于上述方程的复根也成立。

记w(n)为n的上述唯一表示中的项数,因此w(3)=4而w(10)=3。

更正式地,对于所有正整数n,我们有:
n = $\displaystyle \sum_{k=-\infty}^{\infty}$ bkrk
其中:
对于所有k,bk要么是0要么是1;
对于所有k,bk+bk+1+bk+2≤1;
w(n) = $\displaystyle \sum_{k=-\infty}^{\infty}$ bk是有限的。

记S(m)= $\displaystyle \sum_{j=1}^{m}$w(j2)。
已知S(10) = 61以及S(1000) = 19403。

求S(5 000 000)。