9cdfe55bc3f1

Problem 387
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Tue, 03 Oct 2017 22:13:02 -0400
parents 31594a0e0439
children b5be17536fc6
branches/tags (none)
files 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.
+  (labels ((harshadp (number)
+             (dividesp number (sum (digits number))))
+           (strong-harshad-p (number)
+             (multiple-value-bind (result remainder)
+                 (truncate number (sum (digits number)))
+               (and (zerop remainder)
+                    (primep result))))
+           (right-truncatable-harshad-p (number)
+             (iterate (for i :first number :then (truncate-number-right i 1))
+                      (until (zerop i))
+                      (always (harshadp i))))
+           (strong-right-truncatable-harshad-p (number)
+             ;; A "strong, right-truncatable Harshad number" is a number that is
+             ;; both a strong Harshad number and a right-truncatable Harshad
+             ;; 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.
+             (and (strong-harshad-p number)
+                  (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
+             ;; (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)
+                  (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)))))))
+    (harshad-total (expt 10 14))))
+
 
 ;;;; 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 @@
   (mod (truncate integer (expt radix n)) radix))
 
 
-(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`."
   (mod n (expt radix (- (digits-length n radix) amount))))
 
-(defun truncate-number-right (n amount &optional (radix 10))
+(defun-inline truncate-number-right (n amount &optional (radix 10))
   "Chop `amount` digits off the right side of `n` in base `radix`."
   (truncate n (expt radix amount)))