The Last Prime Digit
April 16, 2019
We don’t want to store lots of prime numbers, only to throw them away, so we generate the primes and calculate the last digits on the fly, trading time for space:
(define (grimes n) (let ((ps (primegen)) (counts (make-matrix 4 4 0))) (ps) (ps) (ps) ; discard 2,3,5 (let loop ((prev (ps)) (n (- n 4))) (if (zero? n) counts (let ((curr (modulo (ps) 10))) (matrix-set! counts (quotient prev 3) (quotient curr 3) (+ 1 (matrix-ref counts (quotient prev 3) (quotient curr 3)))) (loop curr (- n 1)))))))
This calculation took a few minutes:
> (grimes 10000000) #(#(446808 756071 769923 526953) #(593195 422302 714795 769915) #(639384 681759 422289 756851) #(820368 640076 593275 446032))
You can run the program at https://ideone.com/IcT9ib.
Here is my take in Julia (1.0.2):
lastdigit(n::Int64) = n % 10
for i = 2:N
ld1 = lastdigit(P[i-1])
ld2 = lastdigit(P[i])
a = b = 0
end
Z /= N
4×4 Array{Float64,2}:
0.0462304 0.0742944 0.0750461 0.0544234
0.0601098 0.0444256 0.0704369 0.075029
0.0637398 0.0675519 0.0443935 0.0743187
0.0799143 0.0637294 0.0601274 0.0462292
On another note, I wonder if Dr. Grimes changed his surname so that it rhymes with “primes” because he’s so intrigued by them…
Sourcecode in Python is on ideone.
Here are some results:
I let it run longer and with primes upto 10_900_000_000_000 the result only changes a little.
Here’s a solution in C++. It uses the non-segmented Sieve of Eratosthenes, limiting how large the primes can get before the system runs out of memory.
Example Usage: