题目

Problem 473: Phigital number base

Let φ be the golden ratio: φ .

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位提交正确答案的。

题解

第473题:斐基数

黄金分割比记为 φ

每个正整数均可表为 φ 的幂之和,还可进一步要求和式中 φ 的每个幂最多只用一次。

这种和式并不唯一。

如果限定为有限和式,且不用相邻整数作为指数,则和式唯一。

例如:2=φ+φ−2,3=φ2−2

我们用 0 和 1 的序列表示这种 φ 的幂的和式,小数点右边是负指数。

这种表示法称为斐基数

于是 1=1φ、2=10.01φ、3=100.01φ、14=100100.001001φ

其中 1、2、14 是回文斐基数,而 3 不是(因为小数点不位于正中)。

不超过 1000 的正整数中,回文斐基数之和为 4345。

试求不超过 1010 的正整数中回文斐基数之和。

斐氏数列与斐的幂

我们在欧拉计划第2题已经遇到过著名的斐波那契数列 { Fn },这里将斐氏数列扩展到0及负下标:

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

递推公式 Fn = Fn-1 + Fn-2 对全体整数(正整数、0、负整数)成立。

此外,若 n 为奇数,F-n = Fn,否则 F-n = -Fn

请读者自行验证公式 φn = Fn-1 + Fn φ。

例如:

φ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

注意到 1 = φ0,我们有:

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

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

思考一下,是否每个正整数都能表示为斐的不同幂的和式?

斐基数

十进制数的含义是把数表为 10 的幂的和式(相同的幂有几个,就在前面乘以几):

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

以斐的幂的和式表示正整数,这种表示法称为斐基数(即以 φ 为基的数):

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

向右扩展和向左收缩

根据前述公式 φn = Fn-1 + Fn φ 及斐氏数列的递推公式 Fn = Fn-1 + Fn-2 易得:

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

这就是说,把斐基数表示法序列中的任何 100 替换为 011(可跨越小数点进行替换),而这个斐基数所代表的正整数的值保持不变。这种替换称为“向右扩展”(增加 1 的数目)。

当然,反向替换-- 011 替换为 100 --也是成立的,称为“向左收缩”(缩减 1 的数目)。

正整数表为规范序列

斐基数表示法序列中如果没有相邻的 1,称为规范序列。每个正整数都能表为规范序列。

我们从 1 = 1φ 开始。下一个正整数是:

2 = 1φ + 1.00φ

 = 1φ + 0.11φ(施行了“向右扩展”)

 = 01.11φ

 = 10.01φ(施行了“向左收缩”)

对一个正整数的规范序列进行“增一”算法,可得下一个正整数的规范序列:

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

因为规范序列中没有相邻的 1,算法第2步“向右扩展” 100 替换为 011 的过程中,中间那个位置原先肯定是 0,可以放心替换。最右那个位置需要考虑是否需要继续向右扩展。

暴力破解

准备工作完成,可以开始解题。

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);
  }
}

用静态布尔数组存放规范序列,数组长度 n 是根据需要表示的正整数 1010 事先计算的,常量 k 是规范序列中小数点左边那个位置的下标(从序列左侧算起,0 起始)。

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

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

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

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

主程序首行设置正整数 1 对应的规范序列。1 是回文斐基数,和 s 的初值为 1。循环执行“增一”算法,把回文斐基数加到和 s 中。最后输出和 s 就 OK 了。

此为暴力破解,能算出正确答案,程序运行需要几个小时,不符合欧拉计划的“一分钟原则”。

高效的程序

下面的 C 程序由欧拉计划本题论坛第一个贴子中的 C++ 程序改写而来:

#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;
}

这个程序非常高效,运行时间只有 0.001 秒。目前我还没有完全理解这个程序的工作原理。

参考资料

Using Powers of Phi to represent Integers