Circular primes implementation and tests

1 files changed, 69 insertions, 0 deletions

diff --git a/circular-primes/README.org b/circular-primes/README.org
new file mode 100644
index 0000000..132552f
--- /dev/null
+++ b/circular-primes/README.org
@@ -0,0 +1,69 @@
+* Solver for https://projecteuler.net/problem=35
+
+The above problem asks us to calculate all of the circular primes below 1,000,000. A circular prime number is a number that is prime in all rotations, i.e.:
+
+197, 971, and 719
+
+** Solution
+
+*** First (Faster, at 1m50s on my laptop)
+
+I thought my original solution somewhat clever... It collects all of the prime numbers below 1,000,000 (all 78,498 of them) using my "sieve of eratosthenes" implementation. Then, it tkes the first number, finds all of the rotations of that number, places them in a second list, and takes the difference of the two. If the original "primes" list is the expected size smaller (if all of the rotated numbers were in the primes list), the second list is added to the list of found circular primes.
+
+It only works because no number divisible by 11 is pressent (i.e. no "333"), and there are no duplicates in the initial primes list:
+
+#+begin_src scheme
+  (define (generate-circular-primes-to n)
+    "Returns the 'circular primes' under N."
+    (let loop ((primes (generate-primes-to n))
+               (circular-primes '()))
+      (if (null? primes)
+          (sort circular-primes <)
+          (let* ((circle (number->circular-list (car primes)))
+                 (prev-num-primes (length primes))
+                 (primes (lset-difference eqv? primes circle)))
+            (loop primes
+                  ;; primes contains no duplicates, so:
+                  (if (eq? (length primes) (- prev-num-primes (length circle)))
+                      (append circle circular-primes)
+                      circular-primes))))))
+
+  (define (number->circular-list n)
+    "Given number N, returns a list of all rotated
+  numbers of N, i.e.:
+
+  123 -> '(312 231 123)"
+    (let ((lst (string->list (number->string n))))
+      (let loop ((accum (list lst))
+                 (next (list-rotate lst)))
+        (if (equal? next lst)
+            (map (lambda (x) (string->number (list->string x)))
+                 accum)
+            (loop (cons next accum)
+                  (list-rotate next))))))
+#+end_src
+
+Sorting through 78,000 primes was extremely slow, however. Scheme lists are a slow structure for continuous large set operations, even if we are saving time by not processing the same "circular primes" in the list repeatedly.
+
+*** Second (Slow, at 3m10s on my laptop)
+
+I decided to try a more simplistic approach by using filter on the initial prime list, and defining a predicate for circular primes (circular-primes? procedure). What I discovered is that "filter" is not implemented to be any faster than the set operations (lists  have to be traversed in their entirety each time, unlike a tree or hash map), and this algorithm does not benefit from any of the speedups of my previous.
+
+#+begin_src scheme
+  (define (generate-circular-primes-to n)
+    "Returns the 'circular primes' under N."
+    (filter circular-prime? (generate-primes-to n)))
+
+  (define (circular-prime? n)
+    "Given number N, returns #t if list of all rotated
+  numbers of N are also prime, #f otherwise."
+    (let ((initial (string->list (number->string n))))
+      (if (or (not (prime? n))
+              (negative? n))
+          #f
+          (let loop ((next (list-rotate initial)))
+            (cond
+             ((equal? next initial) #t)
+             ((not (prime? (string->number (list->string next)))) #f)
+             (#t (loop (list-rotate next))))))))
+#+end_src