HOME SUMMARY

Problem 29

1. Problem

Distinct Powers

Consider all integer combinations of ab 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 ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

不同的幂

考虑所有满足 2 ≤ b ≤ 5 和 2 ≤ b ≤ 5 的幂 ab

\[\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}\]

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

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

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

2. Solution

由于 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 来说就是从 104, 108 … 到 10100 这些对应于 1002 到 10050 的项,共计 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