--- a/src/problems.lisp Tue Oct 03 22:13:02 2017 -0400
+++ b/src/problems.lisp Wed Oct 04 00:51:13 2017 -0400
@@ -2071,7 +2071,7 @@
(right-truncatable-harshad-p number)))
(strong-right-truncatable-harshad-prime-p (number)
;; A "strong, right-truncatable Harshad prime" is not itself
- ;; a Harshad number. Prime numbers can never be Harshad numbers
+ ;; a Harshad number! Prime numbers can never be Harshad numbers
;; (except for single-digit numbers), because otherwise they would
;; have to have a divisor (the sum of their digits) (thanks
;; lebossle).
@@ -2083,17 +2083,22 @@
(strong-right-truncatable-harshad-p
(truncate-number-right number 1))))
(harshad-total (limit)
- (sum
- (recursively ((digits ()))
- (let ((n (digits-to-number digits :from-end t)))
- (cond
- ((or (>= n limit)) nil)
- ((or (zerop n) (harshadp n))
- (mapcan #'recur
- (loop :for i :from (if (null digits) 1 0) :to 9
- :collect (cons i digits))))
- ((strong-right-truncatable-harshad-prime-p n) (list n))
- (t nil)))))))
+ ;; Instead of trying to check every number below 10^14 for
+ ;; primality, we can recursively build right-truncatable Harshad
+ ;; numbers until we hit a non-Harshad (or the limit), then test
+ ;; that for strong-right-truncatable-harshad-prime-ness.
+ ;;
+ ;; If we work from the left (starting at the high order digits)
+ ;; and make sure the number is a Harshad number at each step,
+ ;; we automatically ensure it's right truncatable.
+ (recursively ((n 0))
+ (cond
+ ((>= n limit) 0)
+ ((or (zerop n) (harshadp n))
+ (iterate (for digit :from (if (zerop n) 1 0) :to 9)
+ (summing (recur (append-digit digit n)))))
+ ((strong-right-truncatable-harshad-prime-p n) n)
+ (t 0)))))
(harshad-total (expt 10 14))))
--- a/src/utils.lisp Tue Oct 03 22:13:02 2017 -0400
+++ b/src/utils.lisp Wed Oct 04 00:51:13 2017 -0400
@@ -75,6 +75,11 @@
(collect d :at :beginning)))
+(defun-inline append-digit (digit number &optional (radix 10))
+ "Appened `digit` to `number` in base `radix` as a low-order digit."
+ (+ digit (* number radix)))
+
+
(defun-inline nth-digit (n integer &optional (radix 10))
"Return the `n`th digit of `integer` in base `radix`, counting from the right."
(mod (truncate integer (expt radix n)) radix))