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:

   a number   



p


{\displaystyle p}

   is prime   if and only if   all the coefficients of the polynomial expansion of
 



(
x
−
1

)

p


−
(

x

p


−
1
)


{\displaystyle (x-1)^{p}-(x^{p}-1)}


are divisible by   



p


{\displaystyle p}

.



Example

Using   



p
=
3


{\displaystyle p=3}

:

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



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





 Note:
This task is not the AKS primality test.   It is an inefficient exponential time algorithm discovered in the late 1600s and used as an introductory lemma in the AKS derivation.



Task



 Create a function/subroutine/method that given   



p


{\displaystyle p}

   generates the coefficients of the expanded polynomial representation of   



(
x
−
1

)

p




{\displaystyle (x-1)^{p}}

.
 Use the function to show here the polynomial expansions of   



(
x
−
1

)

p




{\displaystyle (x-1)^{p}}

   for   



p


{\displaystyle p}

   in the range   0   to at least   7,   inclusive.
 Use the previous function in creating another function that when given   



p


{\displaystyle p}

   returns whether   



p


{\displaystyle p}

   is prime using the theorem.
 Use your test to generate a list of all primes under   35.
 As a stretch goal,   generate all primes under   50   (needs integers larger than 31-bit).


References

 Agrawal-Kayal-Saxena (AKS) primality test (Wikipedia) 
 Fool-Proof Test for Primes - Numberphile (Video). The accuracy of this video is disputed -- at best it is an oversimplification.


'METHOD -- Use the Pascal triangle to retrieve the coefficients
'UPPER LIMIT OF FREEBASIC ULONGINT GETS PRIMES UP TO 70
Sub string_split(s_in As String,char As String,result() As String)
    Dim As String s=s_in,var1,var2
    Dim As Integer n,pst
    #macro split(stri,char,var1,var2)
    pst=Instr(stri,char)
    var1="":var2=""
    If pst<>0 Then
        var1=Mid(stri,1,pst-1)
        var2=Mid(stri,pst+1)
    Else
        var1=stri
    End If
    Redim Preserve result(1 To 1+n-((Len(var1)>0)+(Len(var2)>0)))
    result(n+1)=var1
    #endmacro
    Do
        split(s,char,var1,var2):n=n+1:s=var2
    Loop Until var2=""
    Redim Preserve result(1 To Ubound(result)-1)
End Sub
 
'Get Pascal triangle components
Function pasc(n As Integer,flag As Integer=0) As String
    n+=1
    Dim As Ulongint V(n):V(1)=1ul
    Dim As String s,sign
    For r  As Integer= 2 To n
        s=""
        For i As Integer = r To 1 Step -1
            V(i) +=  V(i-1)
            If i Mod 2=1 Then sign="" Else sign="-"
            s+=sign+Str(V(i))+","
        Next i
    Next r
    If flag Then 'formatted output
        Dim As String i,i2,i3,g
        Redim As String a(0)
        string_split(s,",",a())
        For n1 As Integer=1 To Ubound(a)
            If Left(a(n1),1)="-" Then sign="" Else sign="+"
            If n1=Ubound(a) Then i2="" Else i2=a(n1)
            If n1=2 Then i3="x" Else i3="x^"+Str(n1-1)
            If n1=1 Then i="":sign=" " Else i=i3
            g+=sign+i2+i+" "
        Next n1
        g="(x-1)^"+Str(n-1)+" = "+g
        Return g
    End If
    Return s
End Function
 
Function isprime(num As Integer) As Integer
    Redim As String a(0)
    string_split(pasc(num),",",a())
    For n As Integer=Lbound(a)+1 To Ubound(a)-1
        If (Valulng(Ltrim(a(n),"-"))) Mod num<>0 Then Return 0
    Next n
    Return -1
End Function
'==================================== 
'Formatted output
For n As Integer=1 To 9
    Print pasc(n,1)
Next n
 
Print
'Limit of Freebasic Ulongint sets about 70 max
Print "Primes up to 70:"
For n As Integer=2 To 70
    If isprime(n) Then Print n;
Next n
 
Sleep