Blum integer: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: use pygments)
(Added Common Lisp implementation)
 
Line 569: Line 569:
24.997% end in 7
24.997% end in 7
24.985% end in 9
24.985% end in 9
</pre>

=={{header|Common Lisp}}==

Simple implementation without any performance tuning; execute (main) from REPL.

<syntaxhighlight lang="lisp">
(defun is-factor (x y)
(zerop (mod x y)))

(defun is-congruent (num a n)
(= (mod num n) a))

(defun is-prime (n)
(cond ((< n 4) (or (= n 2) (= n 3)))
((or (zerop (mod n 2)) (zerop (mod n 3))) nil)
(t (loop for i from 5 to (floor (sqrt n)) by 6
never (or (is-factor n i)
(is-factor n (+ i 2)))))))

(defun first-factor (n)
(loop for i from 2 to (floor (sqrt n))
thereis (if (is-factor n i) i nil)))

(defun is-blum (n)
(let ((factor (first-factor n)))
(and factor
(is-congruent factor 3 4)
(/= factor (/ n factor))
(is-congruent (/ n factor) 3 4)
(is-prime factor)
(is-prime (/ n factor)))))

(defun main ()
(let ((n 0)
(i 1)
(blums '())
(counts '()))
(dotimes (i 10) (push (cons i 0) counts))
(loop while (<= n 400000)
do (setf i (+ i 2))
(when (is-blum i)
(incf n)
(incf (cdr (assoc (mod i 10) counts)))
(when (<= n 50)
(push i blums)
(when (= n 50)
(format t "First 50 Blum integers:~%")
(format t "~{~5d~5d~5d~5d~5d~5d~5d~5d~5d~5d~%~}~%" (reverse blums))))
(if (find n '(26828 100000 200000 300000 400000))
(format t "The ~7:dth Blum integer is: ~9:d~%" n i))))
(format t "~%% distribution of the first 400,000 Blum integers:~%")
(dolist (x '(1 3 7 9))
(format t "~3$% end in ~a~%" (/ (cdr (assoc x counts)) 4000) x))))
</syntaxhighlight>
{{out}}
<pre>
First 50 Blum integers:
21 33 57 69 77 93 129 133 141 161
177 201 209 213 217 237 249 253 301 309
321 329 341 381 393 413 417 437 453 469
473 489 497 501 517 537 553 573 581 589
597 633 649 669 681 713 717 721 737 749

The 26,828th Blum integer is: 524,273
The 100,000th Blum integer is: 2,075,217
The 200,000th Blum integer is: 4,275,533
The 300,000th Blum integer is: 6,521,629
The 400,000th Blum integer is: 8,802,377

% distribution of the first 400,000 Blum integers:
25.001% end in 1
25.017% end in 3
24.997% end in 7
24.985% end in 9
</pre>
</pre>