Wheel factorization: Efficient?

[kar_bon]

Originally Posted by 3.14159

Also: About the Prime Pages' database: Can one register to have a prime listed in the misc. primes in their database (Primes that are special-form, but do not make it to the top 5k.)

Here's an example: 3 * 2²¹³³²¹ + 1 is present, but it does not register for the top 5k, but is stored there because it is a prime Proth number.

It's not correct at all:

I got a list of old Top5000 lists like this one:

Die groessten bekannten Primzahlen
Fortsetzung, Teil 1
zusammengestellt von: Andreas Ferl
Stand: 12/2005
==================================


(12/alle5.txt)
(001) 5000  73051674^8192+1                   64419 g333 2003 Generalized Fermat
(002) 4915  73040014^8192+1                   64419 g333 2003 Generalized Fermat
(003) 4916  73033018^8192+1                   64418 g333 2003 Generalized Fermat
(004) 4917  73012436^8192+1                   64417 g333 2003 Generalized Fermat
(005) 4918  1035*2^213949-1                   64409 L80  2005 
(006) 4919  611*2^213927+1                    64402 p161 2005 
(007) 4920  135135*2^213916-1                 64401 L8   2004 
(008) 4921  189*2^213856-1                    64380 L91  2004 
(009) 4922f 1295*2^213818-1                   64369 L80  2005 
(010) 4923  855*2^213807+1                    64366 p161 2005 
(011) 4924  31554*69^35000-1                  64365 g355 2004 
(012) 4925  25924*69^35000-1                  64365 g355 2004 
(013) 4926  1131*2^213798-1                   64363 L80  2005 
(014) 4927  1163*2^213770-1                   64355 L80  2005 
(015) 4928  6738*(2^148227+60443)*(205*2^65523-1639)-1
                                              64352 x25  2002 
(016) 4929  95*6^82691+1                      64349 p67  2004 
(017) 4930  48705*2^213741-1                  64348 L82  2004 
(018) 4931  531*2^213721+1                    64340 g388 2005 
(019) 4932  623*2^213682-1                    64328 L21  2004 
(020) 4933  529*2^213665-1                    64323 L21  2004 
(021) 4934  849*2^213650+1                    64318 p161 2005 
(022) 4935  2145*2^213621-1                   64310 L8   2004 
(023) 4936  411*2^213603-1                    64304 g276 2004 
(024) 4937x 72*14^56091+1                     64290 p67  2005 
(025) 4938x 2327*2^213550-1                   64289 L10  2005 
(026) 4939  70000292^8192+1                   64268 g0   2002 Generalized Fermat
(027) 4940x 78*15^54631+1                     64253 p67  2005 
(028) 4941  975*2^213395+1                    64242 p161 2005 
(029) 4942  Phi(3,24375!3)                    64236 p128 2004 Generalized unique
(030) 4943  1119*2^213370+1                   64234 p69  2005 
(031) 4944  687*2^213366+1                    64233 p161 2005 
(032) 4945  293*2^213346-1                    64227 L21  2005 
(033) 4946  19580625*2^213303+1               64218 p147 2004 
(034) 4947  3*2^213321+1                      64217 Y    1997 
          Divides Fermat F(213319); GF(213316,6), GF(213319,12) [g0]

So it was in the Top5000 then.
And it was submitted in 1997, so the digit-range was very low then.
So it's on the short list because as GFN-divisors, but not for only Proth-type!

[3.14159]

Originally Posted by kar_bon

So it was in the Top5000 then.
And it was submitted in 1997, so the digit-range was very low then.
So it's on the short list because as GFN-divisors, but not for only Proth-type!

... That slashes my hopes into pieces

[axn]

Originally Posted by 3.14159

You were forced to lower the k-range when dealing with factor-rich numbers in order to get the same amount of candidates.

The correct interpretation is, I was forced to _increase_ the k-range for _factor-deficient_ bases, because their "before" probability sucked. Isn't it a good thing to have to deal with smaller k-range?

Originally Posted by 3.14159

obvious composites that could have been eliminated

How do you propose this elimination would have happened? We trial factored all the sieves to p=10^12. What more could we've done to eliminate "obvious composites"?

[CRGreathouse]

Originally Posted by axn

The correct interpretation is, I was forced to _increase_ the k-range for _factor-deficient_ bases, because their "before" probability sucked. Isn't it a good thing to have to deal with smaller k-range?

Yes. Just because the range is so bad that you have to throw out a lot more stuff doesn't mean that the remaining candidates are any better.

[3.14159]

Originally Posted by axn

The correct interpretation is, I was forced to _increase_ the k-range for _factor-deficient_ bases, because their "before" probability sucked. Isn't it a good thing to have to deal with smaller k-range?

Smaller k-range:

-You get no result. Try again.

Also: Factor-rich bases become too large, and as a result, the sieving becomes too slow. I'd be willing to use 360 or 5040 at most, but not a number such as 277200 or 360360, because they have too many factors.

But, I will be willing to experiment.

<experiment begins> I'll use the smallest number divisible by numbers 1-16. (720720)

The numbers that are kicked off have small prime factors: Ex: 807 * 720720¹⁶ + 1 was kicked for being divisible by 487302259. It turned out that it was also divisible by 811, which means it should have never appeared. Strange.

<experiment ends>

k-range: 2-8600. (Candidates ≈ 8600)
Digit range ≈ 97 digits
Primes found: 213 primes.

Now, a prime base: 720101.

<experiment begins>
Sieving.. testing.. collecting data.. done.
<experiment ends>

k-range: 2-17200 (Odd numbers eliminated, had to double range for fair comparison) (Candidates: 8600)
Digit range ≈ 95-98 digits.
Primes found: 65 primes.

Results: The 17-smooth base collected nearly 3.3 times as many primes as did the prime numbered base.
I don't think I'd bother with experimenting for larger numbers. 3.3 to 1 speaks for itself.

[3.14159]

Powers of e whose integer part is prime:
2
7
65659969
5184705528587072464087
14302079958348104463583671072905261080748384225250684971
17199742630376622641833783925547830057256484050709158699244513
90495434206726229847410205869155592694321050043276356069748574418954464448324474771731402260449959015939388343491719
427847885537112357207876255931406846789266913923776392091467045124744001977520721628438365960643441035669087059710408721053015644066027

Woo. I just set a record.

[CRGreathouse]

Originally Posted by 3.14159

Powers of e whose integer part is prime:
2
7
65659969
5184705528587072464087
14302079958348104463583671072905261080748384225250684971
17199742630376622641833783925547830057256484050709158699244513
90495434206726229847410205869155592694321050043276356069748574418954464448324474771731402260449959015939388343491719
427847885537112357207876255931406846789266913923776392091467045124744001977520721628438365960643441035669087059710408721053015644066027

Woo. I just set a record.

See Sloane's A050809 and A050808.

[CRGreathouse]

Originally Posted by 3.14159

Results: The 17-smooth base collected nearly 3.3 times as many primes as did the prime numbered base.
I don't think I'd bother with experimenting for larger numbers. 3.3 to 1 speaks for itself.

The expected difference is (2/1 * 3/2 * 5/4 * 7/6 * 11/10 * 13/12) / (2 * 720101/720100) ≈ 2.61, where the 2 in the denominator accounts for the larger range for the prime.

In particular, the expected number of primes is about 186 to 214 for 720720 and 68 to 86 for 720101. It happens that you were on the high end for the composite base and the low end for the prime, but still.

Edit: Here, I'll write you a program to do these calculations.

expected(b,e,kstart,kstop)=my(f=factor(b)[,1],t=prod(i=1,#f,f[i]/(f[i]-1))*(kstop-kstart+1)/(e*log(b)+log(kstop)-1));[t-sqrt(t),t+sqrt(t)]
expected(720720,16,1,8600)
expected(720101,16,1,17200)

[3.14159]

Originally Posted by CRGreathouse

The expected difference is (2/1 * 3/2 * 5/4 * 7/6 * 11/10 * 13/12) / (2 * 720101/720100) ≈ 2.61, where the 2 in the denominator accounts for the larger range for the prime.

In particular, the expected number of primes is about 186 to 214 for 720720 and 68 to 86 for 720101. It happens that you were on the high end for the composite base and the low end for the prime, but still.

Hmm.. So that was merely a lucky fluke? My objection might still stand, after all.

Originally Posted by CRGreathouse

Edit: Here, I'll write you a program to do these calculations.

Is this PARI code?

[CRGreathouse]

Originally Posted by 3.14159

Hmm.. So that was merely a lucky fluke? My objection might still stand, after all.

It was a fluke that it was a factor of 3 instead of a factor of 2.5. It wasn't a fluke that it was significantly higher than 1.

Originally Posted by 3.14159

Is this PARI code?

Yes. The first line is the function; the second two use the function to determine the expected number of primes for your examples. The range I gave was one standard deviation: a sort of best-guess for the number you'll get. Being outside of it isn't particularly strange, but it gives a good guess. Replace the final part with

[t-3*sqrt(t),3+3*sqrt(t)]

if you want a 99+% interval instead.

The code takes lots of statistical liberties; don't expect good results with very narrow intervals, nor with ranges where the largest number has significantly more bits than the smallest number. But for any reasonable variable-k work you're likely to do it should work fine.

[axn]

Originally Posted by CRGreathouse

[t-3*sqrt(t),3t+3*sqrt(t)]

.