Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

Because I don't know how to build efficient code for it. Or did you type "if x%2!=0 and x%3!=0 ... and x%156577 !=0 ... and x%597811057 !=0..."

Ah. That's not a sieve, though, that's trial division. The key part of a sieve is that you can avoid doing the division at each step with careful arithmetic. That accounts for a time difference of about 1e2, which takes you right into the range I did.

But what you asked before (sorry, can't find it to quote) is wise: try to find a pre-built solution. I didn't, but I'm sure that there are program much better than what I made for myself.

As to the language, I *didn't* write it in Pari. My rule of thimb is that Pari is good at number theory, capable in algebra, and poor at string manipulation and sieving. I just used C, I think.

[3.14159]

Originally Posted by CRGreathouse

Ah. That's not a sieve, though, that's trial division. The key part of a sieve is that you can avoid doing the division at each step with careful arithmetic. That accounts for a time difference of about 1e2, which takes you right into the range I did.

Isn't that how every sieve works? Via trial-dividing every candidate by one integer and eliminating those that are divided by that integer, then proceeding to the next (prime) integer for the remaining candidates?:

Here's an example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150

Dividing each integer by two leaves -->

1 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149

Three: -->

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 137 139 143 145 149

Five -->

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149

Seven -->

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 121 127 131 137 139 143 149

Eleven -->

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149

Which in turn eliminates all the undesirable numbers below the given limit - the composites - the very idea behind a sieve?

[bsquared]

Originally Posted by 3.14159

Isn't that how every sieve works? Via trial-dividing every candidate by one integer and eliminating those that are divided by that integer, then proceeding to the next (prime) integer for the remaining candidates?:

The right idea, but not the right method. Haven't you seen this animation here?

The whole point is to avoid divisions, which are slow, and instead use memory operations and additions. For instance, here is what you wrote, in pseudo-C:

for (i = 2; i < sqrt(N); i++)
{
   // don't bother with numbers we know are composite
   if (primes[i] = 0)
      continue;

   // starting at the number after this one, test all 
   // numbers for divisibility
   for (j=i+1; j < N; j++)
   {
      // don't bother with numbers we know are composite
      if (primes[j] == 0)
         continue;

      if (primes[j] % i == 0)
         primes[j] = 0
   }

   // print all non-zero values in the array
}

Here is a true sieve

for (i = 2; i < sqrt(N); i++)
{
   // don't bother with numbers we know are composite
   if (primes[i] = 0)
      continue;

   // starting at next multiple of this prime
   for (j = i+i; j < N; j += i)
   {
      // cross off this multiple
      primes[j] = 0;
   }

   // print all non-zero values in the array
}

Similar structure. Orders of magnitude faster. Not only is the inner loop longer, but each % can take 20-40 clock ticks while each = takes less than one clock tick, on average.

[3.14159]

Also: I accidentally restarted the sieving for the same old file. This means I lost 16 hours and 1400 candidates of progress. I pretty much have to start from scratch. Screw it, I'll simply start a base 2 search instead, for a larger digit range.

New searches: k * 2²⁵⁶⁷²⁰ + 1 (77284-77287 digits); k * 113^28720 + 1 (58969 to 58971 digits)

[wblipp]

Originally Posted by science_man_88

can we knock out a lot of the sequence through using comparison of 24n+7 intersecting the list made by (6n-/+1)*p ?

No.

Every 24n+7 is also a 6n+1.

24n+7 = 6*(4n)+6+1 = 6*(4n+1)+1

(Besides all the posts between here that explain it would be uselessly inefficient even if it worked)

[science_man_88]

Originally Posted by wblipp

No.

Every 24n+7 is also a 6n+1.

24n+7 = 6*(4n)+6+1 = 6*(4n+1)+1

(Besides all the posts between here that explain it would be uselessly inefficient even if it worked)

I get every 24n+7 is also 6n+1 but we can limit n in either to the sequence I gave then use the patterns in the n values in my list to come up with ones to knock out eventually giving us a decreased list that should contain only Mersenne primes up to a point.

[3.14159]

Originally Posted by science_man_88

I get every 24n+7 is also 6n+1 but we can limit n in either to the sequence I gave then use the patterns in the n values in my list to come up with ones to knock out eventually giving us a decreased list that should contain only Mersenne primes up to a point.

As was posted previously, you should program or download a sieve. Once all the numbers have been tested for primality, grab the primes, add one, factor, and see if it yields a power of 2.
Here's the first Mersenne number that's also 24k + 7:
k = 0; 24k + 7 = 7 = Mersenne number.

The Mersenne numbers begin: 3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147486347, 137438953471, 2199023255551, 8796093022207, 140737488355327, 9007199254740991, 576460752303423487, 2305843009213693951, etc. Subtract 7, and make sure that they are divisible by 24.

[science_man_88]

the sequence goes:

0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, 91625968981, 366503875925, 1466015503701, 5864062014805, 23456248059221, 93824992236885

are there any numbers(n) in this list that work with the patterns so far, if so knock them out they cannot be prime for 24n+7.

[science_man_88]

okay I see a flaw don't know if I have to start at 5 or not

[CRGreathouse]

Originally Posted by science_man_88

are there any numbers(n) in this list that work with the patterns so far, if so knock them out they cannot be prime for 24n+7.

Really, we don't know what you mean. I get that you see the close connection between A002450 and the Mersenne primes, but this is really no different than saying, "if you can just find a pattern in numbers p+1 where p is a Mersenne prime".... Sure, but how does that make the search easier?

[CRGreathouse]

Originally Posted by 3.14159

As was posted previously, you should program or download a sieve. Once all the numbers have been tested for primality, grab the primes, add one, factor, and see if it yields a power of 2.

Are you just playing around with science_man_88? This is obviously a bad method, as I have explained -- far too slow to be useful for any purpose, regardless of how good the sieve is. (Even with a magical sieve that goes directly from one prime to the next it is far too slow.)