Undergrad Primality test from pascal triangle

[rajeshmarndi]

In pascal triangle, if all the elements of a row(except 1 in both end) are divisible by the row number, then the row number is a prime.

Or if the coefficient of binomial expansion (except 1's) are divisible by the power, then the power is a prime.
It is inefficient to check all the coefficient upto the middle term(since the coefficient repeat, thereafter) with the power of the binomial expansion, for divisibility.

But if we take this way,

Say 15361, i.e

(1+1)¹⁵³⁶¹ = 1 + C(15361,1) + C(15361,2) + ... + C(15361,7680) + C(15361,7681) + ... + C(15361,15360) + 1
So, if 15361 is a prime, then it will also be divisible, to the sum of coefficient, too. But it is highly possible, composite number will also divide the sum of coefficient.
But if we take summation of coefficient in parts, then it becomes almost zero, that each summation part,which will have different values, will also be divisible by power of composite numbers.

That is, in the above example.

If we divide ,7680 coefficient(upto middle term), of the above examples, into say 12 equal parts, i.e each part will have 640 coefficent and each summation part will be of different values. Then, the possibility become highly, that only a power of prime will only divide all the 12 parts summation.C(15361,1)+...+C(15361,640) = will be divisible by the prime power
C(15361,641)+...+C(15361,1280) = will be divisible by the prime power
C(15361,1281)+...+C(15361,1920) = will be divisible by the prime power
C(15361,1921)+...+C(15361,2560) = will be divisible by the prime power
C(15361,2561)+...+C(15361,3200) = will be divisible by the prime power
C(15361,3201)+...+C(15361,3840) = will be divisible by the prime power
C(15361,3841)+...+C(15361,4480) = will be divisible by the prime power
C(15361,4481)+...+C(15361,5120) = will be divisible by the prime power
C(15361,5121)+...+C(15361,5760) = will be divisible by the prime power
C(15361,5761)+...+C(15361,6400) = will be divisible by the prime power
C(15361,6401)+...+C(15361,7040) = will be divisible by the prime power
C(15361,7041)+...+C(15361,7680) = will be divisible by the prime power
So, what is the efficieny of such check, for primality.

Thanks.

 

[mfb]

So, what is the efficieny of such check, for primality.

Extremely bad. To check the primality of n, you have to calculate n/2 binomial coefficients. That works for n=10000, it might work for n=10¹⁰, but it won't work for 10⁴⁰, where n/2 exceeds the total number of computing steps every computer in the world combined ever did.

An approach that is still extremely slow, but orders of magnitude better: just test for divisibility from 2 to $\sqrt n$. Instead of n/2, the number of calculations scales with $\sqrt n$.

Modern tests for prime numbers can check 100-digit numbers in a second.

 

[rajeshmarndi]

Extremely bad. To check the primality of n, you have to calculate n/2 binomial coefficients.

I do not know if there is a formula for summation of coefficent of
C(15361,1)+...+C(15361,640) =

If there is, then you are NOT calculating n/2 binomial coefficent.

You will be only calculating how many parts you are dividing n/2. And then checking those, divisibility with n.

 

[mfb]

There is no useful formula that would speed up calculations notably. It doesn't help to be better by a factor of 10, 1000 or even 10¹⁰ if you need a speedup of more than 10¹⁰⁰⁰ to be competitive.