题目

Problem 581. 47-smooth triangular numbers

A number is p-smooth if it has no prime factors larger than p.
Let T be the sequence of triangular numbers, ie T(n)=n(n+1)/2.
Find the sum of all indices n such that T(n) is 47-smooth.

题解

第581题:47-光滑三角形数

p-光滑数是其所有素因数均不超过 p 的数。
记 T 是三角形数序列,即:T(n)=n(n+1)/2。
求:使得 T(n) 是 47-光滑数的所有 n 的和。

分析

刘新宇的新作《算法新解》即将由人民邮电出版社出版。该书前言中的“丑数:数据结构的威力”小节中给出了一个非常高效的算法,可以顺序生成 5-光滑数。概述如下:

5-光滑数只有 2、3 和 5 这三个素因数。我们使用队列 Q2、Q3 和 Q5,初始化为 Q2 = {2}、Q3 = {3} 和 Q5 = {5}。然后重复以下步骤:

  • 比较这 3 个队列的头部元素,找到最小的元素所在的队列,将其出队,得到 x。
  • 如果 x 是从 Q2 取出的,则将 2x 加入 Q2,将 3x 加入 Q3,将 5x 加入 Q5
  • 如果 x 是从 Q3 取出的,则将 3x 加入 Q3,将 5x 加入 Q5。注意,不需要将 2x 加入 Q2,因为 2x 已经在 Q3 中了。
  • 如果 x 是从 Q5 取出的,则将 5x 加入 Q5,而不需要处理 2x 和 3x 了。

我把这个算法稍做修改,使用包含 15 个队列的数组,用来生成 47-光滑数。

显而易见,如果 T(n) 是 47-光滑数,那么 n 和 n+1 都必须是 47-光滑数。

解答

根据以上分析,我们有以下 C# 程序:

using System;
using System.Collections.Generic;

static class E581
{
  static readonly int[] ps = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};

  static int IndexOfMinValue(long[] a)
  {
    int k = 0; long m = a[0];
    for (int i = a.Length - 1; i > 0; i--) if (m > a[i]) m = a[k = i];
    return k;
  }

  static IEnumerable<long> Smooth()
  {
    yield return 1;
    var a = new long[ps.Length];
    var b = new Queue<long>[a.Length];
    for (var i = a.Length - 1; i >= 0; i--)
      (b[i] = new Queue<long>()).Enqueue(a[i] = ps[i]);
    for (int k; ; ) {
      var x = a[k = IndexOfMinValue(a)];
      yield return x; b[k].Dequeue();
      for (var i = a.Length - 1; i >= k; i--) b[i].Enqueue(x * ps[i]);
      a[k] = b[k].Peek();
    }
  }

  static void Main()
  {
    var s = new List<long>();
    foreach (var n in Smooth()) { if (n > (long)1e13) break; s.Add(n); }
    var a = s.ToArray(); long z = 0;
    foreach (var n in a) if (Array.BinarySearch(a, n+1) >= 0) z += n;
    Console.WriteLine(z);
  }
}

简要说明:

  • Smooth 方法生成 47-光滑数的无限序列。注意:它的主循环是无限循环。
  • Smooth 方法中的 b 数组用于管理队列,a 数组存放各队列头部元素。
  • IndexOfMinValue 方法用于找出最小元素所在的队列。
  • 根据题目的意思,三角形数序列中的 47-光滑数是有限的。Main 方法的第 1 个 foreach 循环利用 Smooth 方法生成所有不超过 1013 的 47-光滑数的有序列表。
  • Main 方法的第 2 个 foreach 循环查找同时满足 n 和 n+1 都是 47-光滑数的 n,并求和。

这个程序的运行时间是 9 秒。

改进

把上述程序中的 Main 方法修改为:

  static void Main()
  {
    var r = Smooth().GetEnumerator(); r.MoveNext();
    long z = 0, n0 = r.Current; r.MoveNext();
    for (long n; (n = r.Current) <= (long)1e13; n0 = n, r.MoveNext())
      if (n == n0 + 1) z += n0;
    Console.WriteLine(z);
  }

运行时间下降到 2 秒。不但如此,还减少了内存占用,真是一举两得。时间复杂度从 O(nlogn) 下降到 O(n),空间复杂度从 O(n) 下降到 O(1)。

参考资料

  1. Wikipedia: Smooth number
  2. Wikipedia: Triangular number
  3. GitHub: Book of Elementary Algorithms and Data structures