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

Published on 12 May 2024 09:40 PM
#Bracmat

How to resolve the algorithm AKS test for primes step by step in the Bracmat 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 Bracmat programming language

Source code in the bracmat programming language

( (forceExpansion=.1+!arg+-1)
& (expandx-1P=.forceExpansion$((x+-1)^!arg))
& ( isPrime
  =
    .         forceExpansion
            $ (!arg^-1*(expandx-1P$!arg+-1*(x^!arg+-1)))
          : ?+/*?+?
        & ~`
      |
  )
& out$"Polynomial representations of (x-1)^p for p <= 7 :"
& -1:?n
&   whl
  ' ( 1+!n:~>7:?n
    & out$(str$("n=" !n ":") expandx-1P$!n)
    )
& 1:?n
& :?primes
&   whl
  ' ( 1+!n:~>50:?n
    & ( isPrime$!n&!primes !n:?primes
      |
      )
    )
& out$"2 <= Primes <= 50:"
& out$!primes
);

( out$"Primes between 980 and 1000, short version:"
& 980:?n
&   whl
  ' ( !n+1:<1000:?n
    & ( 1+!n^-1*((x+-1)^!n+-1*(x^!n+-1))+-1:?+/*?+?
      | out$!n
      )
    )
);

You may also check:How to resolve the algorithm Determine if two triangles overlap step by step in the QB64 programming language
You may also check:How to resolve the algorithm Semordnilap step by step in the Rust programming language
You may also check:How to resolve the algorithm Trigonometric functions step by step in the AWK programming language
You may also check:How to resolve the algorithm Quickselect algorithm step by step in the Julia programming language
You may also check:How to resolve the algorithm Non-decimal radices/Output step by step in the Run BASIC programming language