题目

Problem 571. Super Pandigital Numbers

A positive number is pandigital in base b if it contains all digits from 0 to b - 1 at least once when written in base b.

A n-super-pandigital number is a number that is simultaneously pandigital in all bases from 2 to n inclusively.
For example 978 = 11110100102 = 11000203 = 331024 = 124035 is the smallest 5-super-pandigital number.
Similarly, 1093265784 is the smallest 10-super-pandigital number.
The sum of the 10 smallest 10-super-pandigital numbers is 20319792309.

What is the sum of the 10 smallest 12-super-pandigital numbers?

题解

第571题:超级全能数

如果 b 进制正整数包含 0 至 b - 1 的数字,则称为全能数

如果正整数同时是 2 至 n 进制全能数,则称为 n 阶超级全能数。
例如 978 = 11110100102 = 11000203 = 331024 = 124035 是最小的 5 阶超级全能数。
同样地,1093265784 是最小的 10 阶超级全能数。
前 10 个 10 阶超级全能数的和是 20319792309。

前 10 个 12 阶超级全能数的和是多少?

分析

首先,我们从 12 进制全能数入手,从 1023456789AB 开始,顺序生成各个排列,直到找到 10 个满足要求的全能数。
其次,对于每个排列,检查是否为 11 至 5 进制全能数。
其中,不用检查是否为 4 至 2 进制全能数。因为 8 进制全能数一定是 2 进制全能数,9 进制全能数一定是 3 进制全能数。此外,对于足够小的正整数,同时是 12 至 5 进制全能数,也是 4 进制全能数。

注意,同时是 12 至 5 进制全能数,不一定是 4 进制全能数。例如:

190AB5634780212 =
4A9827315865011 =
1565970130425810 =
614013746568529 =
3437016735757028 =
32042426655642147 =
531455445500212026 =
40230320320132140135 =
32033200323232332330024

解答

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

#include <stdio.h>

const int max = 12, limit = 10;

int next_perm(char s[])
{ // return: 1:success, 0:fail
  int i = max - 1; while (s[i] >= s[i+1]) i--;
  if (i == 0) return 0;
  int j = max; while (s[i] >= s[j]) j--;
  char t = s[i]; s[i] = s[j]; s[j] = t;
  for (int a = i+1, b = max; a < b; a++, b--)
    t = s[a], s[a] = s[b], s[b] = t;
  return 1;
}

long to_decimal(const char s[])
{
  long z = 0;
  for (int i = 1; i <= max; i++) z = s[i] + z * max;
  return z;
}

int is_pandigital(long z, int base)
{
  int a = 0;
  for (long t; z > 0; z = t) a |= 1 << (z - (t = z / base) * base);
  return ++a == 1 << base;
}

int is_super_pandigital(long z)
{
  for (int i = max - 1; i >= 5; i--) if (!is_pandigital(z, i)) return 0;
  return 1;
}

int main(void)
{
  static char a[max + 1]; a[1] = 1; long sum = 0;
  for (int i = 3; i <= max; i++) a[i] = i - 1;
  for (int n = 0; n < limit; ) {
    long z = to_decimal(a);
    if (is_super_pandigital(z)) n++, sum += z;
    if (!next_perm(a)) break;
  }
  printf("%ld\n", sum);
  return 0;
}

简要说明:

  • next_perm 函数按顺序生成下个排列。
  • to_decimal 函数把 12 进制数(排列)转换为 10 进制数。
  • is_pandigital 函数检查整数 z 是否为 base 进制全能数。
  • is_super_pandigital 函数检查整数 z 是否为超级全能数。
  • main 函数调用以上函数完成工作。

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

按顺序生成所有排列

《计算机程序设计艺术·卷4A:组合算法(一)(英文版)》,第 7.2.1.2 节,第 319 页:

参考资料

  1. 计算机程序设计艺术·卷4A:组合算法(一)(英文版)
  2. Wikipedia: Permutation: Generation in lexicographic order