Friday, January 12, 2018

Testing for Primes

As we have seen a unique (infinite) number sequence is associated with the polynomial equation (x – 1)= 0.

For example when n = 3, the sequence relates to the triangular nos.,

1, 3, 6, 10, 15, 21, 28, 36, …

There is however a fascinating alternative way of obtaining this general sequence.

So again when (x – 1)= 0, each number in the sequence corresponds to

     
 kCn - 1,   =  k!/{(n – 1)!( k – n + 1)!}, where k = n – 1, n, n + 1, n + 2, …

Therefore, when the starting value of n = 3, the first number in sequence is 2C2  = 1

And subsequent numbers are 3C= 3, 4C= 6, 5C= 10, …

Thus these successive numbers represent (n – 1) combinations with respect to 2, 3, 4, 5, … , items respectively.

So when n = 3, successive numbers represent just 2 combinations with respect to 2, 3, 4, 5, …, items respectively.  


For the above general series, in the first number cycle of n, the sum of last (n – 1) digits
= (n + 1)th term – 1

So again, for example when n = 3, the 1st cycle comprises the 3 numbers 1, 3 and 6 respectively.

And the sum of the last two of these numbers = 9, which is 1 less than the 4th term in the sequence (i.e. 10).


This relationship holds for all values of n.

So for example when n = 4, the unique associated (infinite) sequence of digits is,

1, 4, 10, 20, 35, 56, 84, …

These now represent 3 combinations of 3, 4, 5, 6, ... items respectively. 

Thus, the 1st cycle comprises the 4 numbers 1, 4, 10 and 20. And the sum of the last three of these numbers = 34, which now is 1 less than the 5th number in the sequence (i.e. 35).

 ∞
 ∑1/kCn - 1 = sum of reciprocals of unique digit sequence associated 
k = n - 1

with (x – 1)n

So when for example, n = 3 (and n – 1 = 2),

    ∞
  ∑1/ kC= sum of reciprocals of unique digit sequence associated 
  k = 2

with (x – 1)3

= 1/2C2  +  1/3C2  + 1/4C2  + 1/5C2  + … 

= 1 + 1/3 + 1/6 + 1/10 + …   = 2


Remarkably when n is prime the {(n + 1)th term – 1} appears to be always divisible by n3 and when n is composite, not divisible by n3 (where p ≥ 5).

Where p = 3, the {(n + 1)th term – 1} i.e. 9, is divisible by n2 (i.e. 32).

And when p = 2, the {(n + 1)th term – 1} i.e. 2, is divisible by n (i.e. 2).


In principle this provides a fascinating test for whether a number is prime.

Thus in general terms, we can compute,

{(2n – 1Cn – 1) – 1}/n3, to see whether an integer (without remainder) results. Alternatively, we check to see if n3 is a factor.

So for example to test whether n = 29 is prime, we compute

{57C28  – 1)/293}

And because there is an integer result, 29 is therefore prime. 

I have tested for all primes from 5 to 61 (inclusive) and found no exceptions.

In all these cases for primes, where n3 was indeed a factor, in no case was a higher power of n a factor.

It would equally appear to be the case that if we continued on to further cycles - where once again a cycle contains the same number of terms, as the number in question (n) - that the 1st number of the next cycle less 1, will again be divisible by n3, where n is prime.

However in some cases this number will also be divisible by higher powers of n.

For example when n = 5, the first number in the 5th cycle (i.e. 11th term) is 10626.


Then when we subtract 1, we obtain 10625, which is divisible by n4 = 625.  

No comments:

Post a Comment