Primality test from pascal triangle

  • #1
317
0

Main Question or Discussion Point

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)15361 = 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.
 

Answers and Replies

  • #2
33,596
9,327
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=1010, but it won't work for 1040, 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.
 
  • #3
317
0
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.
 
  • #4
33,596
9,327
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 1010 if you need a speedup of more than 101000 to be competitive.
 

Related Threads for: Primality test from pascal triangle

  • Last Post
Replies
7
Views
496
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
6
Views
997
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
4
Views
1K
Replies
2
Views
1K
Top