Problems & Puzzles: Puzzles

Puzzle 826. Primes and Pascal Triangle For sure you know the Pascal's triangle. Some years ago two mathematicians (whose names I will omit for a week) demonstrated the following statement related to Pascal's triangle and prime numbers: Stagger the triangle’s rows so that row n starts at column 2n in a square matrix, as shown below. Then a column number is prime if and only if the numbers in that column are each divisible by their row number Q1. Can you produce your own demonstration of the above statement? Q2. In general, how many division tests are needed, by this technique for any column number n?

---

Contribution came from John Arioni

***

John wrote:

 c--> 0 1 2 3 4 5 ….....

r=0 1

r=1 1 1

r=2 1 2 1

r=3 1 3 3 1

r=4 1 4 6 4 1

r=5 1 5 10 10 5 1

…................................

Entries in Pascal's triangle (above) are:

P[r,c] = r! / [c! (r-c)!] ; c <= r

Let M be the matrix resulting after shifting Pascal's triangle rows,

each row by twice the row number, and let c ' = 2r+c - Then:
 

[*] M[r,c'] = r! / [(c'-2r)! (3r-c')!] ; ceiling(c'/3) <= r <= floor(c'/2)

If c'=2r, i.e. the column number is even, then M[r,c'] = r! / [0! r!] =1

is divisible by its row number only in the case r=1, id est. c'=2

Let C represent the generic odd column number of M:

the meaningful entries in column C of M range

from row = ceiling(C/3) to row R = (C-1)/2 .

Here below, in descending order, are the meaningful entries of column C:

M[R,C] = R! / [1!(R-1)!] = [(C-1)/2]! / 1! / [(C-3)/2]!

M[R-1,C] = (R-1)! /[ 3!(R-4)!] = [(C-3)/2]! / 3! / [(C-9)/2]!

M[R-2,C] = (R-2)! /[ 5!(R-7)!] = [(C-5)/2]! / 5! / [(C-15)/2]!

M[R-3,C] = (R-3)! /[ 7!(R-10)!] = [(C-7)/2]! / 7! / [(C-21)/2]!

…............

…............

M[ceiling(C/3) , C]

Expanding the factorials, we get the following (TAB 1):

M[R,C] = 2^-1 (C-1) / 1! = (C-1)/2

M[R-1,C] = 2^-3 (C-3)(C-5)(C-7) / 3!

M[R-2,C] = 2^-5 (C-5)(C-7)(C-9)(C-11)(C-13) / 5!

M[R-3,C] = 2^-7 (C-7)(C-9)(C-11)(C-13)(C-15)(C-17)(C-19) / 7!

….............

…............

M[ceiling(C/3) , C] = see below

C = 6x+3

if C is congruent to 0(mod 3) then, according to [*] :

M[ceiling(C/3) , C] = (C/3)! / [(C-2C/3)! (C-C)!] = 1

which is is divisible by its row number only if C=3 (row=1)

________________________________________________

C = 6x-1

if C = 6x-1, then ceiling(C/3)=2x and:

M[ceiling(C/3 ) , C] = M[2x,6x-1] = 2x = (C+1)/3

M[2x,6x-1] = 2x = (C+1)/3

…......

…......

M[3x-1,6x-1] = 3x-1 = (C-1)/2

The meaningful entries in column C range from row 2x to

row 3x-1 then they are as many as x

______________________________________________

C = 6x+ 1

if C = 6x+1, then ceiling(C/3)=2x+1 and

M[ceiling(C/3) , C] = M[2x+1,6x+1] = x(2x+1) = (C-1)(C+2)/18

M[2x+1,6x+1] = x(2x+1) = (C-1)(C+2)/18

…......

….....

M[3x,6x+1] = 3x = (C-1)/2

The meaningful entries in column C range from row 2x+1 to

3x then they are as many as x

___________________________________________

Dividing each entry of TAB 1 by its row number we get the followig (TAB 2) :

M[R,C] / R = (C-1)/2

M[R-1,C] / (R-1) = 2^-2 (C-5)(C-7) / 3!

M[R-2,C] / (R-2) = 2^-4 (C-7)(C-9)(C-11)(C-13) / 5!

M[R-3,C] / (R-3) = 2^-6 (C-9)(C-11)(C-13)(C-15)(C-17)(C-19) / 7!

….......

M[R-i,C] / (R-i) = 2^-2i [C-(2i+1)-2*1][(C-(2i+1)-2*2]......[C-(2i+1)-2*2i] / (2i+1)!

…........

…........

M[ceiling(C/3) , C]

Q1

Let C be a composite odd integer and 2i+1 one of its factors: of

course C-(2i+1) as well as C-(2i+1)-(2i+1) are divisible by 2i+1,

while [C-(2i+1)-2] , [(C-(2i+1)-2*2], ......[C-(2i+1)-2*2i] aren't.

So we can state that the entry M[R-i,C] in column C of M isn't

divibile by its row number R-i, as - see tab 2 – :

M[R-i,C] / (R-i) = 2^-2i [C-(2i+1)-2*1][(C-(2i+1)-2*2]......[C-(2i+1)-2*2i] / (2i+1)!

If instead C is prime, in the numerator of the expression above,

for any odd number between 3 and 2i+1 (3 and 2i+1 included)

there is at least one factor that is divisible by that number , and:

Q2

ceiling(sqrt(C)/2) – 1 = floor(sqrt(C)/2)

is the number of division tests needed if C is prime.

An example

C=35 = 5*7 = 5*(2*3+1)

R = (C-1)/2 = 17

R -3 = 14

M[R-3,C] / (R-3) = 2^-6 (C-9)(C-11)(C-13)(C-15)(C-17)(C-19) / 7!

M[14,35] / 14 = 2^-6 * 26*24*22*20*18*16 / 7!

7 isn't a factor of any of the numbers in the numerator, so 14

doesn't divide M[14,35].

***