# HG changeset patch # User Steve Losh # Date 1507083182 14400 # Node ID 9cdfe55bc3f126265099eee75f46103076c54556 # Parent 31594a0e04395d6c62557b6b6acc5f44b9237f80 Problem 387 diff -r 31594a0e0439 -r 9cdfe55bc3f1 src/primes.lisp --- 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) diff -r 31594a0e0439 -r 9cdfe55bc3f1 src/problems.lisp --- 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 () diff -r 31594a0e0439 -r 9cdfe55bc3f1 src/utils.lisp --- 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)))