# 题目

Problem 473: Phigital number base

Let φ be the golden ratio: φ $=\frac{1+\sqrt{5}}{2}$.

Remarkably it is possible to write every positive integer as a sum of powers of φ even if we require that every power of φ is used at most once in this sum.

Even then this representation is not unique.

We can make it unique by requiring that no powers with consecutive exponents are used and that the representation is finite.

E.g: 2=φ+φ−2 and 3=φ2−2

To represent this sum of powers of φ we use a string of 0's and 1's with a point to indicate where the negative exponents start.

We call this the representation in the phigital numberbase.

So 1=1φ, 2=10.01φ, 3=100.01φ and 14=100100.001001φ.

The strings representing 1, 2 and 14 in the phigital number base are palindromic, while the string representating 3 is not. (the phigital point is not the middle character).

The sum of the positive integers not exceeding 1000 whose phigital representation is palindromic is 4345.

Find the sum of the positive integers not exceeding 1010 whose phigital representation is palindromic.

2014年5月25日中午11时（北京时间）该题放出，我是第48位提交正确答案的。

# 斐氏数列与斐的幂

..., -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...


φ4 = F3 + F4 φ = 2 + 3φ

φ2 = F1 + F2 φ = 1 + φ

φ1 = F0 + F1 φ = 0 + φ

φ-1 = F-2 + F-1 φ = -1 + φ

φ-2 = F-3 + F-2 φ = 2 - φ

φ-4 = F-5 + F-4 φ = 5 - 3φ

# 正整数表为斐的幂的和式

1 = φ-1 + φ-2

2 = φ1 + φ-2

3 = φ2 + φ-2

7 = φ4 + φ-4

4 = 3 + 1 = φ2 + φ0 + φ-2

8 = 7 + 1 = φ4 + φ0 + φ4

# 斐基数

709.0310 = 7x102 + 9x100 + 3x10-2

4 = φ2 + φ0 + φ-2 = 101.01φ

φn = φn-1 + φn-2

# 正整数表为规范序列

2 = 1φ + 1.00φ

= 1φ + 0.11φ（施行了“向右扩展”）

= 01.11φ

= 10.01φ（施行了“向左收缩”）

1. 如果小数点左边那一位是 0，把 0 替换为 1 ，转第3步；
2. 施行“向右扩展”，如果扩展得到的 1 的位置原先是 1 ，继续向右扩展；
3. 施行“向左收缩”，直到无可收缩（这一步是为了消除相邻的 1）。

# 暴力破解

using System;

class ProjectEuler473
{
const  int    n = 96;
const  int    k = 47;
static bool[] a = new bool[n];

static void Increase()
{
if (!a[k]) a[k] = true;
else Expand(k);
Reduce();
}

static void Expand(int i)
{
a[i + 1] = true;
if (!a[i + 2]) a[i + 2] = true;
else Expand(i + 2);
}

static void Reduce()
{
for (bool m = true; m;)
{
m = false;
for (int i = 0; i < n - 2; i++)
if (a[i + 1] && a[i + 2])
{
m = a[i] = true; a[i + 1] = a[i + 2] = false;
}
}
}

static bool IsPalindromic()
{
for (int i = 0, j = n - 1; i < j; i++, j--)
if (a[i] != a[j]) return false;
return true;
}

static void Main()
{
a[k] = true;
ulong s = 1;
for (ulong z = 2; z <= 10000000000; z++)
{
Increase();
// if (z % 10000000 == 0) Console.WriteLine(z);
if (IsPalindromic()) s += z;
}
Console.WriteLine(s);
}
}


Increase() 就是前述“增一”算法。

Expand(i) 从下标 i 开始向右扩展，必要时递归调用自身。

Reduce() 从最左侧开始执行向左收缩，直到无可收缩。

IsPalindromic() 判断规范序列是否表示回文斐基数。

# 高效的程序

#include <stdio.h>

long compute(const long fib[], long n, long s, int k)
{
long s2, sum = s;
for(int i = k; ; sum += compute(fib, n, s2, (i += 2) + 4))
if((s2 = s + fib[i - 1] + fib[i + 5]) > n) return sum;
}

int main(void)
{
long fib[60] = { 0, 1 }, n = 10000000000, sum = 1;
for(int i=2; i < sizeof fib / sizeof fib[0]; i++) fib[i]=fib[i-1]+fib[i-2];
sum += compute(fib, n, 0, 2);
sum += compute(fib, n, 2, 4);
printf("%ld\n", sum);
return 0;
}


# 参考资料

Using Powers of Phi to represent Integers