AKS test for primes: Difference between revisions

=={{header|Lambdatalk}}==

<lang Scheme>

{require lib_BN} // for big numbers

1) pascalian binomial coefficient C(n,p) = n!/(p!(n-p)!) = (n*(n-1)...(n-p+1))/(p*(p-1)...2*1)

{def coeff

{lambda {:n :p}

{BN.intPart

{BN./ {S.reduce BN.* {S.serie :n {- :n :p -1} -1}}

{S.reduce BN.* {S.serie :p 1 -1}}}}}}

-> coeff

2) polynomial expansions of (x − 1)^p

{def sign

{lambda {:n}

{if {= {% :n 2} 0} then + else -}}}

-> sign

{def coeffs

{lambda {:n}

{br}(x - 1)^:n =

{if {= :n 0}

then + 1x^0

else {if {= :n 1}

then + 1x^1 - 1x^0

else {sign 0} 1x^:n

{S.map {{lambda {:p :n} {sign {- :p :n}} {coeff :p :n}x^{- :p :n}} :n}

{S.serie 1 {- :n 1}}}

{sign :n} 1x^0}}}}

-> coeffs

{S.map coeffs {S.serie 0 7}}

->

(x - 1)^0 = + 1x^0

(x - 1)^1 = + 1x^1 - 1x^0

(x - 1)^2 = + 1x^2 - 2x^1 + 1x^0

(x - 1)^3 = + 1x^3 + 3x^2 - 3x^1 - 1x^0

(x - 1)^4 = + 1x^4 - 4x^3 + 6x^2 - 4x^1 + 1x^0

(x - 1)^5 = + 1x^5 + 5x^4 - 10x^3 + 10x^2 - 5x^1 - 1x^0

(x - 1)^6 = + 1x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6x^1 + 1x^0

(x - 1)^7 = + 1x^7 + 7x^6 - 21x^5 + 35x^4 - 35x^3 + 21x^2 - 7x^1 - 1x^0

3) primality test

Taking into account the symmetry of the list of coefficients and the uselessness of the sign

in the calculation of the divisibility, one can limit the tests to half of the list,

and define a simplified function, aks_coeffs:

{def aks_coeffs

{lambda {:n}

{S.map {coeff :n} {S.serie 1 {+ {/ {- :n 1} 2} 1}}}}}

-> aks_coeffs

{def divide

{lambda {:a :b}

{= {BN.compare {BN.% :b :a} 0} 0}}}

-> divide

{def isprime

{lambda {:n}

{if {and {S.map {divide :n} {aks_coeffs :n}}} then :n else .}}}

-> isprime

{S.map isprime {S.serie 2 100}}

-> 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 31 . . . . . 37 . . . 41 . 43 . . . 47

. . . . . 53 . . . . . 59 . 61 . . . . . 67 . . . 71 . 73 . . . . . 79 . . . 83 . . . . . 89 . . . . . . . 97 . . .

</lang>