View Single Post
Old 2004-10-23, 11:28   #7
ET_'s Avatar
Aug 2002
Team Italia

22·3·401 Posts

Originally Posted by synergy
Second question first. You create A and B that way.
Take an example. Starting with {2,3,5,7,11} you put some in A, some in B. So A might be 2^a*5^b*7^c, and B would have to be 3^d*11^e in order to use all of them from the set. So A*B has all of the above primes as factors, and no others i.e. no prime p(n+r) divides A*B.

First question: Let's look at this inductively. Using {2,3} i.e. abs(2^a +/- 3^b) you can get all primes from 5 to 25. Then you use the primes you just found, {2,3,5,7,11,13,17,19} and 23, but we won't use 23, I'll explain in a minute why. Put some of the set in A, ALL OF THE REST in B, and apply the absolute value thingie. Now, here is where the 23 comes in. EVERY output less than 23^2=529 will be prime. These will all be between 23 and 529.
Next step? Use the primes you just found, except 523, to find all primes between 523 and 523^2=273529. Granted, we're getting a huge number of variables, but it's exciting that the range grows so fast, and no composites need checking. Don't know if it is efficient, but smart algorithms could be created to pick partitions between A and B that are most likely to give small enough outputs to be within the target range without too much trouble. Even if it isn't efficient, it should be worth something as a theoretical understanding of one more facet of the distribution of the primes.
I see.
It seems you are working on two different fields of factoring: congruences modulo a prime numbers product and trial factoring up to the square root of a number.

A hint: take a look at the Fermat's little theorem and check out results to avoid Carmichael numbers. You will have a good challenge to check the efficience of your idea.

ET_ is online now   Reply With Quote