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.


 
const
  pasTriMax = 61;
 
type
  TPasTri = array[0 .. pasTriMax] of UInt64;
 
var
  pasTri: TPasTri;
 
procedure PascalTriangle(n: LongWord);
// Calculate the n'th line 0.. middle
var
  j, k: LongWord;
begin
  pasTri[0] := 1;
  j := 1;
  while j <= n do
  begin
    Inc(j);
    k := j div 2;
    pasTri[k] := pasTri[k - 1];
    for k := k downto 1 do
      Inc(pasTri[k], pasTri[k - 1]);
  end;
end;
 
function IsPrime(n: LongWord): Boolean;
var
  i: Integer;
begin
  if n > pasTriMax then
  begin
    WriteLn(n, ' is out of range');
    Halt;
  end;
 
  PascalTriangle(n);
  Result := true;
  i := n div 2;
  while Result and (i > 1) do
  begin
    Result := Result and (pasTri[i] mod n = 0);
    Dec(i);
  end;
end;
 
procedure ExpandPoly(n: LongWord);
const
  Vz: array[Boolean] of Char = ('+', '-');
var
  j: LongWord;
  bVz: Boolean;
begin
  if n > pasTriMax then
  begin
    WriteLn(n,' is out of range');
    Halt;
  end;
 
  case n of
    0: WriteLn('(x-1)^0 = 1');
    1: WriteLn('(x-1)^1 = x-1');
  else
    PascalTriangle(n);
    Write('(x-1)^', n, ' = ');
    Write('x^', n);
    bVz := true;
    for j := n - 1 downto n div 2 + 1 do
    begin
      Write(vz[bVz], pasTri[n - j], '*x^', j);
      bVz := not bVz;
    end;
    for j := n div 2 downto 2 do
    begin
      Write(vz[bVz], pasTri[j], '*x^', j);
      bVz := not bVz;
    end;
    Write(vz[bVz], pasTri[1], '*x');
    bVz := not bVz;
    WriteLn(vz[bVz], pasTri[0]);
  end;
end;
 
var
  n: LongWord;
begin
  for n := 0 to 9 do
    ExpandPoly(n);
  for n := 2 to pasTriMax do
    if IsPrime(n) then
      Write(n:3);
  WriteLn;
end.