Thread: prime problem
View Single Post
Old 2004-05-04, 14:07   #5
wblipp's Avatar
May 2003
New Haven

22·32·5·13 Posts

There are some interesting tradeoffs in the difficulty of finding and proving large primes and the difficulty of factoring large numbers. The range of approaches also depends on how much time and computing power is available - a class collaboration for a semester could go much further than an individual for a night.

As jinydu pointed out, the middle number must be of the form 6x - otherwise at least one of the other numbers is divisible by 2 or 3. A little more work will also show that to eliminate 5 as a possible factor, the middle number must be either 30x or 30x+12. I'll stick with the 30x+12 case.

You also require the middle number to be a multiple of 1997. So you need integer solutions to 30x+12=1997y

Using Dario Alpern's Quadratic Integer Solver, you can quickly find that solutions are of the form y= 6 + 30t

Now you know the middle number is of the form 1997*(6+30*t). There are two general strategies from here. You can pick a range where you are sure you can factor 6+30t and look for the primes, or you can limit yourself to special values of 6+30t that are already factored. If you pick the second strategy, you may want to go back up a few paragraphs and pick the 30x route instead of the 30x+12 route.

To find the primes, you'll want to use one of the sieving programs. I've never done such a search, but I think PFGW's "abc" format would work.

To factor the middle number (if not forced to be pre-factored), you might be able to use Dario Alpern's Factoring Applet. For larger number you will need to use other methods.
wblipp is offline   Reply With Quote