1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Primality test from pascal triangle

  1. Oct 27, 2016 #1
    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.
     
  2. jcsd
  3. Oct 27, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  4. Nov 27, 2016 #3
    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.
     
  5. Nov 28, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Primality test from pascal triangle
  1. Pascal triangle (Replies: 2)

  2. Pascal triangle (Replies: 3)

  3. Pascals Triangle (Replies: 6)

Loading...