Wheel factorization: Efficient?

[3.14159]

Originally Posted by kar_bon

Less primes to find among the remaining candidates!

Example: k*2^n-1

n-range: 600000-1000000
sieved to p=26*10^12
k=337: 2618 candidates left
k=315: 32276 candidates left

Primes in that range found:
k=337: none
k=315: 3

Ah, I see what the problem is: You assumed I did n-range searches. I perform k-range searches, which means I search for primes in arithmetic progressions.

Maybe this clears everything up.

Originally Posted by kar_bon

BTW: k=337 got no prime for 172000<n<2600000!

Perform a k-range search. Constant probability is awesome.

Now, to wait for sm88 to explain the unspecified sequences.

[axn]

Some sample numbers:

Base|Exponent|Prob.|#tests  |K Range   |Cand Left|Sieve     |#tests |
    |        |Boost|(before)|(3*#tests)|(p=10^12)|efficiency|(after)|
----+--------+-----+--------+----------+---------+----------+-------|
  2 |  250000|    2|  86643 |  259929  |  10563  |  24.61   |  3520 |
  6 |   96713|    3|  57762 |  173286  |  10563  |  16.40   |  3522 |
 30 |   50948| 3.75|  46209 |  138627  |  10563  |  13.12   |  3522 |
210 |   32407|4.375|  39607 |  118821  |  10563  |  11.25   |  3520 |

[science_man_88]

Originally Posted by 3.14159

Ah, I see what the problem is: You assumed I did n-range searches. I perform k-range searches, which means I search for primes in arithmetic progressions.

Maybe this clears everything up.



Perform a k-range search. Constant probability is awesome.

Now, to wait for sm88 to explain the unspecified sequences.

look m for 24m+7 takes on values that appear in sequence related to p all I was trying to do is find a way to use these to sieve out of the sequences involved with the sequence in the OEIS i posted a link to earlier.

85 Mod 23 = 16 the start c

16*4+1 = 65-23 = 42 then -23 = 19
19*4+1 = 77-23 = 54-23 again = 31 - 23 again = 8
8*4+1 = 33-23=10
10*4+1 = 41 - 23=18
18*4+1=73 - 23 = 50 -23=27-23 =4
4*4+1 = 17
17*4+1 = 69 -23 = 46-23=23-23=0

[3.14159]

@Axn: The data explains it all. Inefficient sieving is why I stick to factor-deficient or prime bases.

[axn]

Originally Posted by 3.14159

@Axn: The data explains it all. Inefficient sieving is why I stick to factor-deficient or prime bases.

If that is the conclusion, you've not understood that table at all.

See the columns K-Range, Cands Left, # tests (before) and # tests (after). Those are the key thing. If the sieve efficiency is less for a factor rich base, it compensates it (exactly) by allowing a smaller starting k-range. The net effect is that you _test_ the same number of candidates after sieving. The expected number of tests (~3520) for finding a prime is the same for everything, _after_ sieving.

[CRGreathouse]

Right. axn, thanks for explaining; you do it better than I can.

[3.14159]

Originally Posted by axn

See the columns K-Range, Cands Left, # tests (before) and # tests (after). Those are the key thing. If the sieve efficiency is less for a factor rich base, it compensates it (exactly) by allowing a smaller starting k-range. The net effect is that you _test_ the same number of candidates after sieving. The expected number of tests (~3520) for finding a prime is the same for everything, _after_ sieving.

Ah, okay. I didn't notice that before. But it ultimately shows that factor-deficient/prime bases are more efficient than factor-rich bases.

Originally Posted by CRGreathouse

Right. axn, thanks for explaining; you do it better than I can.

And since when does this warrant a license for implicit insults?

[CRGreathouse]

Originally Posted by 3.14159

And since when does this warrant a license for implicit insults?

I think, conversationally speaking, I'm allowed to self-deprecate. It's difficult for me to understand others (so I asked, e.g., you to explain sm88's posts), and similarly hard for me to be understood (so axn's explanation worked when mine didn't).

[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.

[axn]

Originally Posted by 3.14159

But it ultimately shows that factor-deficient/prime bases are more efficient than factor-rich bases.

You'll have to explain your reasoning.

[3.14159]

Originally Posted by axn

You'll have to explain your reasoning.

You were forced to lower the k-range when dealing with factor-rich numbers in order to get the same amount of candidates. The data there verifies this. Which means factor-rich bases leave too many candidates and waste time on obvious composites that could have been eliminated, and as a result are a terrible choice for prime searching.

If you would have kept the k-range constant, it would further prove the inefficiency of using a factor-rich base.