Problem 29

Consider all integer combinations of a^b for 2 ≤ b ≤ 5 and 2 ≤ b ≤ 5:

\[\begin{array}{l} 2^2 = 4 & 2^3 = 8 & 2^4 = 16 & 2^5 = 32 \\ 3^2 = 9 & 3^3 = 27 & 3^4 = 81 & 3^5 = 243 \\ 4^2 = 16 & 4^3 = 64 & 4^4 = 256 & 4^5 = 1024 \\ 5^2 = 25 & 5^3 = 125 & 5^4 = 625 & 5^5 = 3125\end{array}\]

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

\[4,8,9,16,25,27,32,64,81,125,243,256,625,1024,3125\]

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

不同的幂

考虑所有满足 2 ≤ b ≤ 5 和 2 ≤ b ≤ 5 的幂 a^b：

如果把这些幂从小到大排列并去重，可以得到如下由 15 个不同的项组成的数列：

\[4,8,9,16,25,27,32,64,81,125,243,256,625,1024,3125\]

考虑所有满足 2 ≤ a ≤ 100 和 2 ≤ b ≤ 100 的幂 a^b，将它们排列并去重所得到的数列有多少个不同的项？

由于 elisp 支持大数运算，因此容易解决：

(length
 (delete-dups
  (cl-loop for a from 2 to 100
	   append (cl-loop for b from 2 to 100
			   collect (expt a b)))))
=> 9183

当然并不是所有的语言都允许这样的便利，我们得学着如何在行为受限的情况下解决问题。实际上我们完全没有必要算出这些幂，我们需要的是这样的变换：

\[a^b = (a^{c})^d \ \ \ b = cd\]

只要 \(a^c \lt 100\)，这样的变换就是成功的。由于 \(c \ge 2\)，\(a\) 必然小于 10。因此我们只需对于 \(2\) 到 \(10\) 范围内的底数进行检查。已知组合总数为 \(99^{2} = 9801\)，用组合总数减去重复项即可。

以下是可能出现重复项的幂次项们：

2, 4, 8, 16, 32, 64
3, 9, 27, 81
5, 25
6, 36
7, 49
10, 100

对于 5 到 10 这些平方项，只需从低阶项中减去相同值的高阶项即可，对于 10 来说就是从 10⁴, 10⁸ … 到 10¹⁰⁰ 这些对应于 100² 到 100⁵⁰ 的项，共计 49 项。

对于 2 和 3 的幂次项们，情况稍微有些复杂，我建议直接打表：

;; 81^100 = 3^400
;; 27^100 = 3^300
;; 9 ^100 = 3^200
;; 3 ^100 = 3^100

;; from 3^2 to 3^400

(let ((eu29-3s (make-vector 401 nil)))
  (cl-loop for i from 2 to 100 by 1
	   for j from 4 to 200 by 2
	   for k from 6 to 300 by 3
	   for l from 8 to 400 by 4
	   do (progn (aset eu29-3s i t)
		     (aset eu29-3s j t)
		     (aset eu29-3s k t)
		     (aset eu29-3s l t)))
  (- (* 4 99)
     (cl-loop for i from 2 to 400
	      count (aref eu29-3s i))))
=> 156

(let ((tb2 (make-vector 601 nil)))
  (cl-loop for a1 from 2 to 100 by 1
	   for a2 from 4 to 200 by 2
	   for a3 from 6 to 300 by 3
	   for a4 from 8 to 400 by 4
	   for a5 from 10 to 500 by 5
	   for a6 from 12 to 600 by 6
	   do (progn
		(aset tb2 a1 t)
		(aset tb2 a2 t)
		(aset tb2 a3 t)
		(aset tb2 a4 t)
		(aset tb2 a5 t)
		(aset tb2 a6 t)))
  (- (* 99 6)
     (cl-loop for i from 2 to 600
	      count (aref tb2 i))))
=> 266

(+ 266 156) => 422
(+ 422 (* 49 4)) => 618
(- (* 99 99) 618) => 9183

Problem 29

1. Problem

2. Solution