How to resolve the algorithm AKS test for primes step by step in the Clojure programming language

Published on 12 May 2024 09:40 PM
#Clojure

How to resolve the algorithm AKS test for primes step by step in the Clojure programming language

Table of Contents

Problem Statement

The AKS algorithm for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles. The theorem on which the test is based can be stated as follows: are divisible by

p

{\displaystyle p}

.

Using

p

3

{\displaystyle p=3}

:

And all the coefficients are divisible by 3,   so 3 is prime.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm AKS test for primes step by step in the Clojure programming language

Source code in the clojure programming language

(defn c 
  "kth coefficient of (x - 1)^n"
  [n k] 
  (/ (apply *' (range n (- n k) -1)) 
     (apply *' (range k 0 -1))
     (if (and (even? k) (< k n)) -1 1)))

(defn cs 
  "coefficient series for (x - 1)^n, k=[0..n]"
  [n] 
  (map #(c n %) (range (inc n))))

(defn aks? [p] (->> (cs p) rest butlast (every? #(-> % (mod p) zero?))))

(println "coefficient series n (k[0] .. k[n])")
(doseq [n (range 10)] (println n (cs n)))
(println)
(println "primes < 50 per AKS:" (filter aks? (range 2 50)))

You may also check:How to resolve the algorithm Calendar - for REAL programmers step by step in the PL/I programming language
You may also check:How to resolve the algorithm Determine if two triangles overlap step by step in the Raku programming language
You may also check:How to resolve the algorithm Sort numbers lexicographically step by step in the Wren programming language
You may also check:How to resolve the algorithm Empty program step by step in the friendly interactive shell programming language
You may also check:How to resolve the algorithm List comprehensions step by step in the Sidef programming language