[QUOTE=3.14159;240687]It would waste time and slow progress. So far, it only takes 0.023 seconds to test each candidate.[/QUOTE]

In the worst case you use a system like GP that isn't designed for this kind of work, and you script it rather than compile it. Under those conditions, my machine (which we know is slower than yours) takes 12.5 milliseconds to trial factor a big number to 1e6. Because this will abort early when it finds a factor, and because those most likely are upfront, the average time spent is 6.9 milliseconds*, which removes 49.3% of composites. (This includes the effect of 'having no small prime factors' or it would be much better. The figure is exact, up to rounding; I computed it directly since 1e6 is so small.)

So on about half the numbers we spend an extra 6.9 milliseconds and on the other half we save 23 milliseconds. The average time savings from trial division: 7.8 milliseconds.

Now if you used something that was, I don't know, [i]actually designed for trial division[/i] you should be able to get much better results.** But even on GP which is decidedly the wrong tool for the job (a Swiss Army multitool rather than a chainsaw) you get serious (~33%) savings.


* This figure of course includes the roughly half of the time when you need to run the trial factorization to completion without finding a factor.
** Also, there are algorithms (see, e.g., Bernstein) that make this much faster. Actually, using an extremely crude approximation to the algorithm improved GP's speed to 4.6 milliseconds and average time savings to 41%... for comparison, if trial division ran in 0 milliseconds, it would give 50% time savings.

[QUOTE=3.14159;240633]I already have an ABC script doing the work for the current collection project I'm working on.

It's collecting all primes k * (n! * p(n)#) + 1, where k is between 1 and 10000 and n between 1 and 1000; I'm only about 17% finished, and slowly growing closer to finishing up.

The -f switch is unnecessary. As n increases, a new prime is added as a divisor. It would slow progress significantly if I did so. Based on what n I'm at, at the moment, it's divisible by every prime up to 1069.[/QUOTE]

In post 240, kar_bon pointed out a number of mistakes and then you ask others to double-check your work. In another post you directly referenced PARI. There isn't much that you have posted that leads me to believe that you are using PFGW.

[QUOTE=kar_bon;240477]I've just noticed your searched ranges, but I can't update the tables on my pages with these data in an easy way.

I would be more necessary to search for other ranges (see picture).

I've not yet got results from 3.14159 of his searched range, so please coordinate both searches for next work to do.[/QUOTE]

Ok, thanks.

I've just started sieving k: 10001-10499, b: 1001-1049 +/-1

Do you also keep factors?

[QUOTE=lorgix;240786]Do you also keep factors?[/QUOTE]

No, no factors collected... only primes.


I don't know, how you search for such primes of the form k*b^b+/-1.

The easiest way is like this:

Take pfgw.exe, make a text-file (named for example "kbbp.txt") with:
[code]
ABC2 $a*$b^$b+1
a: from 10001 to 10500
b: from 1001 to 1050
[/code]

and call pfgw with "pfgw -f -tp -l kbbp.txt"

and all factors found will be logged in the file "pfgw-prime.log".

Play with the parameters and see the timings.

No need to sieve too deep, because a test of a candidate takes about a second (if factoring failed) or about nothing to find a small factor.

[QUOTE=CRGreathouse;240691]In the worst case you use a system like GP that isn't designed for this kind of work, and you script it rather than compile it. Under those conditions, my machine (which we know is slower than yours) takes 12.5 milliseconds to trial factor a big number to 1e6. Because this will abort early when it finds a factor, and because those most likely are upfront, the average time spent is 6.9 milliseconds*, which removes 49.3% of composites. (This includes the effect of 'having no small prime factors' or it would be much better. The figure is exact, up to rounding; I computed it directly since 1e6 is so small.)

So on about half the numbers we spend an extra 6.9 milliseconds and on the other half we save 23 milliseconds. The average time savings from trial division: 7.8 milliseconds.

Now if you used something that was, I don't know, [i]actually designed for trial division[/i] you should be able to get much better results.** But even on GP which is decidedly the wrong tool for the job (a Swiss Army multitool rather than a chainsaw) you get serious (~33%) savings.


* This figure of course includes the roughly half of the time when you need to run the trial factorization to completion without finding a factor.
** Also, there are algorithms (see, e.g., Bernstein) that make this much faster. Actually, using an extremely crude approximation to the algorithm improved GP's speed to 4.6 milliseconds and average time savings to 41%... for comparison, if trial division ran in 0 milliseconds, it would give 50% time savings.[/QUOTE]

Each of PFGW's PRP tests takes 0.023 seconds so far. It would take about 0.060 seconds to trial-divide to 2^20, as of now.

There are no savings there, unless you insist on me counting negative savings.

[QUOTE=3.14159;240805]Each of PFGW's PRP tests takes 0.023 seconds so far. It would take about 0.060 seconds to trial-divide to 2^20, as of now.[/QUOTE]

How is trial division taking that long? Could PFGW possibly be that much worse than Pari at TD? Or are you just using a particularly inefficient GP script for TD? Because even my slow computer takes 12.5 milliseconds for the entire TD, or 6.9 seconds for an average number*, for the naive script in GP. With a not-particularly-clever trick I can get that down to 4.6 milliseconds. How can your fast computer take 5 to 13 times longer than mine?

Edit: A variation on my trick allows the average speed to be reduced to 3.6 milliseconds (worst-case: 5.3 milliseconds if no factors are found). Now I'm 16 times faster than you despite my slower computer. What's going on?

* Assumptions: Equidistributed modulo p for 1069 < p < 1e6, not divisible by any p <= 1069. Speed calculations use 21000 to 22000-bit numbers.

[QUOTE=kar_bon;240795]
don't know, how you search for such primes of the form k*b^b+/-1.
[/QUOTE]

well lets see for +1 if b is a multiple of 6 to be 6n+1 k can be anything positive.

if b is a odd multiple of 3 then k must be even

if b^b is even if it's 0 mod 6 then k can be anything, in the other cases k should be a multiple of 3.

for -1 pretty much the same I haven't figured out what to do if b is a multiple of other primes.

[QUOTE=CRGreathouse;240808]How is trial division taking that long? Could PFGW possibly be that much worse than Pari at TD?[/QUOTE]

Perhaps because you tried it on small numbers.

PARI took 0.11 seconds to divide to the same range. PFGW took 0.06 seconds to do so.

[QUOTE=science_man_88;240809]well lets see for +1 if b is a multiple of 6 to be 6n+1 k can be anything positive.

if b is a odd multiple of 3 then k must be even

if b^b is even if it's 0 mod 6 then k can be anything, in the other cases k should be a multiple of 3.

for -1 pretty much the same I haven't figure out what to do if b is a multiple of other primes.[/QUOTE]

Counterexample: 11632 * 176[sup]176[/sup] + 1 is prime. Neither 176 nor 11632 is a multiple of three.

[QUOTE=3.14159;240810]Perhaps because you tried it on small numbers.[/QUOTE]

I tried it on 21000 to 22000-bit numbers, the same size you were at when you posted you speed statistics. If you want to give me your current times and sizes I'd be happy to recalculate. Larger numbers will in general favor me.

My best method (could be improved, of course!) [i]scripted in GP[/i] (not using an optimized C program which would of course be faster) takes an average of 3.63 milliseconds.

[QUOTE=CRGreathouse;240817]I tried it on 21000 to 22000-bit numbers, the same size you were at when you posted you speed statistics. If you want to give me your current times and sizes I'd be happy to recalculate. Larger numbers will in general favor me.

My best method (could be improved, of course!) [i]scripted in GP[/i] (not using an optimized C program which would of course be faster) takes an average of 3.63 milliseconds.[/QUOTE]

7000-digit numbers? O rly?