Anonymous user
Repunit primes: Difference between revisions
Added a Scheme implementation.
(+python) |
(Added a Scheme implementation.) |
||
Line 476:
Base 35: 313 1297
Base 36: 2</pre>
=={{header|Scheme}}==
{{works with|Chez Scheme}}
This uses
[http://www.rosettacode.org/wiki/Miller-Rabin_primality_test#Scheme Miller–Rabin primality test (Scheme)]
, renamed, restructured, with a minor fix.
<br />
Took about 59 minutes to run.
<br />
'''Primality Test'''
<lang scheme>; Test whether any integer is a probable prime.
(define prime<probably>?
(lambda (n)
; Fast modular exponentiation.
(define modexpt
(lambda (b e m)
(cond
((zero? e) 1)
((even? e) (modexpt (mod (* b b) m) (div e 2) m))
((odd? e) (mod (* b (modexpt b (- e 1) m)) m)))))
; Return multiple values s, d such that d is odd and 2^s * d = n.
(define split
(lambda (n)
(let recur ((s 0) (d n))
(if (odd? d)
(values s d)
(recur (+ s 1) (div d 2))))))
; Test whether the number a proves that n is composite.
(define composite-witness?
(lambda (n a)
(let*-values (((s d) (split (- n 1)))
((x) (modexpt a d n)))
(and (not (= x 1))
(not (= x (- n 1)))
(let try ((r (- s 1)))
(set! x (modexpt x 2 n))
(or (zero? r)
(= x 1)
(and (not (= x (- n 1)))
(try (- r 1)))))))))
; Test whether n > 2 is a Miller-Rabin pseudoprime, k trials.
(define pseudoprime?
(lambda (n k)
(or (zero? k)
(let ((a (+ 2 (random (- n 2)))))
(and (not (composite-witness? n a))
(pseudoprime? n (- k 1)))))))
; Compute and return Probable Primality using the Miller-Rabin algorithm.
(and (> n 1)
(or (= n 2)
(and (odd? n)
(pseudoprime? n 50))))))</lang>
'''The Task'''
<lang scheme>; Return list of the Repunit Primes in the given base up to the given limit.
(define repunit_primes
(lambda (base limit)
(let loop ((count 2)
(value (1+ base)))
(cond ((> count limit)
'())
((and (prime<probably>? count) (prime<probably>? value))
(cons count (loop (1+ count) (+ value (expt base count)))))
(else
(loop (1+ count) (+ value (expt base count))))))))
; Show all the Repunit Primes up to 2700 digits for bases 2 through 16.
(let ((max-base 16)
(max-digits 2700))
(printf "~%Repunit Primes up to ~d digits for bases 2 through ~d:~%" max-digits max-base)
(do ((base 2 (1+ base)))
((> base max-base))
(printf "Base ~2d: ~a~%" base (repunit_primes base max-digits))))</lang>
{{out}}
<pre>
Repunit Primes up to 2700 digits for bases 2 through 16:
Base 2: (2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281)
Base 3: (3 7 13 71 103 541 1091 1367 1627)
Base 4: (2)
Base 5: (3 7 11 13 47 127 149 181 619 929)
Base 6: (2 3 7 29 71 127 271 509 1049)
Base 7: (5 13 131 149 1699)
Base 8: (3)
Base 9: ()
Base 10: (2 19 23 317 1031)
Base 11: (17 19 73 139 907 1907 2029)
Base 12: (2 3 5 19 97 109 317 353 701)
Base 13: (5 7 137 283 883 991 1021 1193)
Base 14: (3 7 19 31 41 2687)
Base 15: (3 43 73 487 2579)
Base 16: (2)
</pre>
=={{header|Sidef}}==
| |||