login
A210721
a(n) is the smallest trial division companion for the n-th prime number.
1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 3, 2, 3, 1, 3, 2, 2, 2, 2, 3, 2, 2, 3, 2, 6, 2, 6, 4, 5, 3, 3, 2, 2, 8, 3, 5, 4, 6, 2, 4, 6, 6, 12, 8, 2, 8, 6, 4, 12, 3, 12, 4, 4, 5, 3, 12, 8, 12, 10, 18, 18, 12, 20, 8, 4, 8, 24, 12, 10, 18, 18, 6, 10, 18, 6
OFFSET
1,12
COMMENTS
A number p is a prime number when it is not divisible by any prime numbers in between 2 and sqrt(p), named as set P0.
If a list of equations in the form:
p=Product(p_i^k_i)+/-Product(p_j^k_j)
is found, where the intersection of set PI={p_i, (all i_s)} and set PJ={p_j, (all j_s)} is empty, and the set P0 is a subset of the union of PI and PJ, p will not be divisible by any prime numbers in set P0. This set of equations gives a proof of primality of p.
If listing all divisors of a(n) in set A, for each element of A, denoted as A(i), |prime(n)^2-A(i)^2| has a prime factor set of P_i. When the union of all (P_i)s has P0 as its subset, prime(n) cannot have any divisors in set P0.
Thus the number a(n) can be used to generate a trial division proof of the n-th prime, and thus defined as "a trial division companion" of the n-th prime.
This method is demonstrated in the example.
Eric M. Schmidt: If p_1,...,p_r are the primes less than sqrt(p), |p - p_1*...*p_r| is a companion.
Conjecture: a(n) < prime(n)^2*(Pi^(-2Pi)+log((prime(n)+1)/prime(n)))
The above behavior was estimated by ploting a(n) against n.
EXAMPLE
The 137th prime number is 773. Sqrt(773) = 27.802.... To prove its primality in trial division method, one should prove that 773 is not divisible by all prime numbers smaller than 27, or P0 = {2, 3, 5, 7, 11, 13, 17, 19, 23}.
Searching all numbers from {1, 2, 3, ...}, it was found that number 18 has the following property:
1) The divisor list of 18: A = {1, 2, 3, 6, 9, 18};
2) 773^2-1 = 2^3*3^2*43*193, which gives 773 = 3^2*43+2*193. This proves that 773 is not divisible by primes in set P_1 = {2, 3, 43, 193};
773^2-2^2 = 3*5^2*31*257, which gives 773*2 = 5^2*31+3*257. This proves that 773 is not divisible by primes in set P_2 = {3, 5, 31, 257};
773^2-3^2 = 2^4*5*7*11*97, which gives 773 = 2^2*97+5*7*11. This proves that 773 is not divisible by primes in set P_3 = {2, 5, 7, 11, 97};
773^2-6^2 = 13*19*41*59, which gives 773*2 = 19*41+13*59. This proves that 773 is not divisible by primes in set P_4 = {13, 19, 41, 59};
773^2-9^2 = 2^3*17*23*191, which gives 773 = 17*23+2*191. This proves that 773 is not divisible by primes in set P_5 = {2, 17, 23, 191};
773^2-18^2 = 5*7*113*151, which gives 773*2 = 7*113+5*151. This proves that 773 is not divisible by primes in set P_6 = {5, 7, 113, 151};
3) Union P_1 though P_6, we found that 773 is not divisible by all primes in set P_all = {2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 41, 43, 59, 97, 113, 151, 191, 193, 257};
4) P0 is a subset of P_all, thus the primality of the 137th prime 773 is proved by processing the number 18 through the above procedure.
MATHEMATICA
PrimeGroup[n-th_] := Block[{p = Prime[n-th], d, t, fc, fs, e, i},
d = Table[Prime[i], {i, 1, PrimePi[NextPrime[Floor[Sqrt[p]]+1, -1]]}];
t = 0; While[t++; fc = Divisors[t]; fs = Length[fc]; e = {}; Do[e = Union[e, Transpose[FactorInteger[Abs[p^2 - fc[[i]]^2]]][[1]]], {i, 1, fs}]; Intersection[d, e] != d]; t]; Table[PrimeGroup[i], {i, 1, 64}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Lei Zhou, Jan 29 2013
STATUS
approved