题目

Problem 616: Creative numbers

新葡京娱乐场:  目前,该旗舰服务平台已经聚集20家专长于北京一日游服务的供应商,提供150余条北京一日游产品,涵盖了天安门、故宫、长城、颐和园、王府井、奥林匹克公园等著名景点。

Alice plays the following game, she starts with a list of integers L and on each step she can either:

  • remove two elements a and b from L and add ab to L
  • or conversely remove an element c from L that can be written as ab, with a and b being two integers such that a, b > 1, and add both a and b to L

For example starting from the list L = {8}, Alice can remove 8 and add 2 and 3 resulting in L = {2, 3} in a first step. Then she can obtain L = {9} in a second step.

Note that the same integer is allowed to appear multiple times in the list.

An integer n > 1 is said to be creative if for any integer m > 1 Alice can obtain a list that contains m starting from L = {n}.

Find the sum of all creative integers less than or equal to 1012.

题解

第616题:有创造力的数

爱丽丝在玩一个游戏:她从整数列表 L 开始,每一步她可以:

  • L 中删除两个元素 ab,并将 ab 添加到 L
  • 或者相反地,从 L 中删除一个形如 ab 的元素 c,其中 ab 都是整数且 a, b > 1,然后将 ab 添加到 L

例如,从整数列表 L = {8} 开始,第一步爱丽丝可以删除 8 并添加 2 和 3,得到 L = {2, 3}。然后第二步她可以得到 L = {9}。

注意在列表中同一整数允许重复出现多次。

如果对于任意整数 m > 1,爱丽丝都能从 L = {n} 开始得到一个包含 m 的整数列表,则称整数 n > 1 为有创造力的

找出所有不超过 1012 的有创造力的数之和。

分析

显然,有创造力的数必须满足以下条件:

  1. 能够写成 ab 的形式,且 a, b > 1。
  2. ab 不能都是素数。否则,我们只能得到 {ab}, {ba} 和 {a, b}。
  3. 不等于 16。否则,我们只能得到 {16}, {2, 4} 和 {2, 2, 2} 。

满足以上条件的 ab 都是有创造力的。证明如下:

  1. 如果 b = pqp, q > 1),则 ab = apq = (ap)q,可以得到 {a, p, q}。
  2. 如果 a = pq,则我们能够从 {ab} 得到 {a, b},从而得到 {ba},同上。
  3. 从 {a, p, q}(q > 2),我们能够得到:{a, pq}, {apq = (ap)pq-1}, {ap, pq-1},最终得到:{a, p, p, q-1}。
  4. 如果 {a, p, q} 不是 {2, 2, 2},则总可以得到 {2, 2, 3, ...}。
  5. 从 {2, 2, 3} 出发,可以得到 {2, 32 = 9}, {29 = 83}, {3, 8}, {38 = 94}, {4 = 22, 9 = 32}, 最终得到:{2, 2, 2, 3}。
  6. 因此,从 {2, 2, 3} 出发,可以得到 {2, 2, 2, 3}, {2, 2, 2, 2, 3}, ..., {2, 2, 2, ..., 2, 3}。
  7. 因此,可以得到任意大的整数。再利用第 3 条,就可以得到任意整数 m > 1。

解答

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

import Data.Set ( fromList )
import Math.NumberTheory.Primes.Testing ( isPrime )
main = let n = 10^12 in print $ flip (-) 16 $ sum $ fromList
  $ concat [takeWhile (<=n) [a^b | b <- [2..], not (isPrime a
  && isPrime b)] | a <- [2 .. ceiling $ sqrt $ fromIntegral n]]

简要说明:

  • 本程序使用双重复循环遍历所有不超过 nab
  • 第 5 行的外层循环的循环变量 a 从 2 至 √n
  • 第 4 行的内层循环的循环变量 b 从 2 开始,直到 ab > n 停止。
  • 第 3 行的fromList 语句把列表转换为集合,以消除重复的元素。

这个程序的运行时间是 3 秒。不超过 1012 的有创造力的数共有 930,380 个,前 4 个是:

  • 36 = 62
  • 64 = 26 = 43 = 82
  • 81 = 34 = 92
  • 100 = 102