# 9cdfe55bc3f1

`Problem 387`
author Steve Losh Tue, 03 Oct 2017 22:13:02 -0400 31594a0e0439 b5be17536fc6 (none) src/primes.lisp src/problems.lisp src/utils.lisp

## Changes

```--- a/src/primes.lisp	Tue Oct 03 20:40:02 2017 -0400
+++ b/src/primes.lisp	Tue Oct 03 22:13:02 2017 -0400
@@ -207,6 +207,19 @@
(primes% (1+ min) max))

+(defun-inline next-prime% (p)
+  (case p
+    ((nil) 2)
+    (2 3)
+    (t (iterate (for i :from (+ p 2) :by 2)
+                (finding i :such-that #'primep)))))
+
+(defmacro-driver (FOR var IN-PRIMES _)
+  (declare (ignore _))
+  (let ((kwd (if generate 'generate 'for)))
+    `(,kwd ,var :next (next-prime% ,var))))
+
+
(defun nth-prime (n)
"Return the `n`th prime number."
(if (= n 1)```
```--- a/src/problems.lisp	Tue Oct 03 20:40:02 2017 -0400
+++ b/src/problems.lisp	Tue Oct 03 22:13:02 2017 -0400
@@ -2027,6 +2027,75 @@
(prime-generating-integer-p candidate))
(summing candidate))))))

+(defun problem-387 ()
+  ;; A Harshad or Niven number is a number that is divisible by the sum of its digits.
+  ;; 201 is a Harshad number because it is divisible by 3 (the sum of its digits.)
+  ;; When we truncate the last digit from 201, we get 20, which is a Harshad number.
+  ;; When we truncate the last digit from 20, we get 2, which is also a Harshad number.
+  ;;
+  ;; Let's call a Harshad number that, while recursively truncating the last
+  ;; digit, always results in a Harshad number a right truncatable Harshad
+  ;; number.
+  ;;
+  ;; Also: 201/3=67 which is prime.
+  ;; Let's call a Harshad number that, when divided by the sum of its digits,
+  ;; results in a prime a strong Harshad number.
+  ;;
+  ;; Now take the number 2011 which is prime.  When we truncate the last digit
+  ;; from it we get 201, a strong Harshad number that is also right truncatable.
+  ;; Let's call such primes strong, right truncatable Harshad primes.
+  ;;
+  ;; You are given that the sum of the strong, right truncatable Harshad primes
+  ;; less than 10000 is 90619.
+  ;;
+  ;; Find the sum of the strong, right truncatable Harshad primes less than
+  ;; 10^14.
+             (dividesp number (sum (digits number))))
+             (multiple-value-bind (result remainder)
+                 (truncate number (sum (digits number)))
+               (and (zerop remainder)
+                    (primep result))))
+             (iterate (for i :first number :then (truncate-number-right i 1))
+                      (until (zerop i))
+             ;; A "strong, right-truncatable Harshad number" is a number that is
+             ;; number.  Note that after the first truncation the rest no longer
+             ;; need to be strong -- it's enough for this number itself to be
+             ;; strong.
+             ;; A "strong, right-truncatable Harshad prime" is not itself
+             ;; 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).
+             ;;
+             ;; What we're looking for here are prime numbers for whom we can
+             ;; chop off the right digit and get strong, truncatable Harshad
+             ;; numbers.
+             (and (primep number)
+                    (truncate-number-right number 1))))
+             (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))))
+                     (t nil)))))))
+

;;;; Tests --------------------------------------------------------------------
(test p1 (is (= 233168 (problem-1))))
@@ -2105,6 +2174,7 @@
(test p323 (is (= 6.3551758451d0 (problem-323))))
(test p345 (is (= 13938 (problem-345))))
(test p357 (is (= 1739023853137 (problem-357))))
+(test p387 (is (= 696067597313468 (problem-387))))

(defun run-tests ()```
```--- a/src/utils.lisp	Tue Oct 03 20:40:02 2017 -0400
+++ b/src/utils.lisp	Tue Oct 03 22:13:02 2017 -0400
@@ -80,11 +80,20 @@

-(defun digits-to-number (digits)
+(defun digits-to-number (digits &key from-end (radix 10))
+  "Concatenate `digits` to return an integer in base `radix`.
+
+  If `from-end` is `t`, start at the end of the list.
+
+  "
(if digits
-    (reduce (lambda (total digit)
-              (+ (* total 10) digit))
-            digits)
+    (if from-end
+      (iterate (for d :in digits)
+               (for multiplier :first 1 :then (* radix multiplier))
+               (summing (* multiplier d)))
+      (reduce (lambda (total digit)
+                (+ (* total radix) digit))
+              digits))
0))

(defun extremely-fucking-unsafe-digits-to-number (digits)
@@ -250,11 +259,11 @@
(- final (* 3 leg))))))

-(defun truncate-number-left (n amount &optional (radix 10))
+(defun-inline truncate-number-left (n amount &optional (radix 10))
"Chop `amount` digits off the left side of `n` in base `radix`."