GPU to 72 status... - Page 272

James Heinrich · 2014-06-03, 17:48

Perhaps I should retract that posting of data. It includes a lot of data on factors irrelevant to our current interest (mfaktx in the approx 2⁷² range), including some P-1 factors and at lot of very tiny factors (<2⁶⁰). Filtering that out, this data is perhaps more relevant:

Code:

mysql> SELECT COUNT(*) AS `howmany`, `class4620` FROM `known_factors_006` WHERE (`factorbits` BETWEEN 68 AND 74) GROUP BY `class4620` ORDER BY `howmany` DESC LIMIT 30;
+---------+-----------+
| howmany | class4620 |
+---------+-----------+
|      26 |      1680 |
|      22 |      1344 |
|      22 |       504 |
|      20 |      3696 |
|      20 |       252 |
|      20 |      1380 |
|      20 |      4080 |
|      20 |      1260 |
|      20 |      4320 |
|      19 |       168 |
|      19 |      2520 |
|      19 |      3420 |
|      19 |       300 |
|      18 |      1980 |
|      18 |       792 |
|      18 |      3720 |
|      18 |      3096 |
|      18 |      3840 |
|      17 |      3516 |
|      17 |       960 |
|      17 |      1500 |
|      17 |      3120 |
|      17 |      3000 |
|      17 |      4356 |
|      17 |        84 |
|      16 |      2688 |
|      16 |      3540 |
|      16 |      1596 |
|      16 |      2700 |
|      16 |      3312 |
+---------+-----------+
30 rows in set (0.20 sec)

And you can see the spread is pretty even.

chalsall · 2014-06-03, 17:59

Quote:

Originally Posted by James Heinrich

And you can see the spread is pretty even.

Thanks James.

And a big down-side of my suggestion is it would result in a re-enforcing feedback loop.

Best let sleeping dogs lie.

LaurV · 2014-06-04, 03:13

Just for the sake of clarifying (or say, side discussion, which do not need to influence the already-made bench), the factors do not "spread evenly" in classes. When p vary on the whole range (to 10^9 in our case), we can have, for any 92160 factors: 960 in class 0, 135 in class 1, 0 in class 2 (and all 4k+2 classes, they will have 0 factors), 270 in class 3 and 4, 180 in class 5, 0 on class 6, 162 in class 7, and so on (this are real, statistical numbers, from the modular calculus, and not example values which are fabricated to "give an idea"). So, some classes have "higher probability" to contain factors, which seems somehow normal, as no factor can be even, no factor can be 3 or 5 mod 8, etc.

James Heinrich · 2014-06-04, 03:38

Quote:

Originally Posted by LaurV

the factors do not "spread evenly" in classes

Throwing out more numbers I mostly don't understand:

Code:

mysql> SELECT COUNT(*), `howmany` FROM (SELECT COUNT(*) AS `howmany`, `class4620` FROM `known_factors_006` WHERE (`factorbits` BETWEEN 68 AND 74) AND (`class4620` IS NOT NULL) GROUP BY `class4620`) AS `a` GROUP BY `howmany`;
+----------+---------+
| COUNT(*) | howmany |
+----------+---------+
|      349 |       1 |
|      505 |       2 |
|      570 |       3 |
|      473 |       4 |
|      366 |       5 |
|      295 |       6 |
|      174 |       7 |
|      166 |       8 |
|      115 |       9 |
|       91 |      10 |
|       61 |      11 |
|       52 |      12 |
|       41 |      13 |
|       28 |      14 |
|       30 |      15 |
|        9 |      16 |
|        8 |      17 |
|        5 |      18 |
|        4 |      19 |
|        5 |      20 |
|        1 |      21 |
|        2 |      22 |
|        1 |      26 |
+----------+---------+
23 rows in set (0.17 sec)

Where "howmany" is the number of factors in a given class, and COUNT(*) is how many times that happens. For example, there is only one instance of a class (#1680 in this case) having 26 factors in the same class.
In short it means that the bulk of the 16359 factors in my data are spread across many different classes: 98% of the factors have less than 10 factors found in the same class. If my poor explanation makes any sense.
So perhaps not quite "spread evenly" (implying uniform distribution) but not nearly as biased as I made it look in post #2972.

axn · 2014-06-04, 03:58

We should expect the factors to be spread evenly. There is no mathematical reason not to. Unless ... P-1.

P-1 factors are NOT expected to fall evenly between the various classes. The upshot is that candidates that has had a (failed) P-1 should behave "unevenly" when it comes to TF factors, and the candidates that haven't had P-1 should be "even". That's the theory, anyway.

Can you do the analysis by removing the TF factors which had a prior P-1?

James Heinrich · 2014-06-04, 04:18

Quote:

Originally Posted by axn

Can you do the analysis by removing the TF factors which had a prior P-1?

Not easily, no, sorry.

LaurV · 2014-06-04, 05:57

Quote:

Originally Posted by axn

We should expect the factors to be spread evenly. There is no mathematical reason not to.

Ooo... happy to contradict you for the first time in my life!

There is a big reason, is called "modular arithmetic".
Assume you have 12 classes, then p (which is a prime) can only be 1,5,7, or 11 (mod 12), so let's put it in a table. I put p on the header, and k on the first column. I compute q=2kp+1, and if this is 3,9 (mod 12) then it can't be prime, also, if it is 3,5 (mod 8) it can't be a factor of a mersenne with odd exponent. I put a 0 in the table in both cases. If not, I put a 1 in the table. Then I sum by columns and rows.

Code:

12 Classes
 k\p 1 5 7 11
 0   1 1 1 1    4
 1   0 0 0 1    1
 2   0 0 0 0    0
 3   1 1 0 0    2
 4   0 1 0 1    2
 5   0 0 1 0    1
 6   0 0 0 0    0
 7   0 1 0 0    1
 8   1 0 1 0    2
 9   0 0 1 1    2
10   0 0 0 0    0
11   1 0 0 0    1

     4 4 4 4   16

You see what happens, for a given p (pick any column), there are always 4 classes from 12, i.e 1/3 "to be tested", because the other 8 either can't generate primes, or their primes are not 1,7, (mod 8), and they can be ignored. For 4620 classes, this number is 960 classes to be tested, what mfaktX is doing.

Switching our attention to lines instead of columns, few lines have no "1"s and their "total" is zero. You can not have factors in these classes, when p varies in the primes set. For some other classes, only ONE p in 4 can have a factor in that class. For other, half of the primes can have factors in the class, etc. Obviously when I say "p may have factors" I refers to its mersenne number, because p is always a prime.

The probability for a p to "have a factor" in a class in not equal, for different classes. Primes which are 1,5,7 (mod 12) can't have factors in class 1, for example. Only primes which are 11 (mod 12) can, which is a quarter of primes, only.

I won't post the 4620 classes table here, it is too big, but to have an idea, this is the table to 60 classes, which shows quite clear the phenomenon:

Code:

60  Classes
 k\p 1  7 11 13 17 19 23 29 31 37 41 43 47 49 53 59
 0   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1   16
 1   0  0  1  0  0  0  1  0  0  0  0  0  0  0  0  1    3
 3   1  0  0  1  1  0  0  0  0  1  1  0  0  0  1  0    6
 4   0  0  1  0  1  0  0  1  0  0  1  0  1  0  0  1    6
 5   0  1  0  0  0  1  0  0  1  0  0  1  0  0  0  0    4
 7   0  0  0  0  1  0  0  1  0  0  0  0  0  0  1  0    3
 8   1  1  0  1  0  0  0  0  1  1  0  1  0  0  0  0    6
 9   0  1  1  0  0  1  0  0  1  0  0  0  1  0  0  1    6
11   1  0  0  1  0  0  0  0  0  0  0  0  0  1  0  0    3
12   0  1  0  1  1  1  1  1  0  1  0  1  1  1  1  1   12
13   0  0  1  0  0  0  1  0  0  0  0  0  1  0  0  0    3
15   1  0  0  1  1  0  0  1  0  1  1  0  0  1  1  0    8
16   0  0  1  0  0  0  1  1  0  0  1  0  0  0  1  1    6
17   0  1  0  0  0  1  0  0  0  0  0  1  0  0  0  0    3
19   0  0  0  0  1  0  0  1  0  0  1  0  0  0  0  0    3
20   1  1  0  1  0  1  0  0  1  1  0  1  0  1  0  0    8
21   0  0  1  0  0  1  1  0  1  0  0  1  0  0  0  1    6
23   1  0  0  1  0  0  0  0  0  1  0  0  0  0  0  0    3
24   1  1  1  0  1  1  0  1  1  1  1  0  1  1  0  1   12
25   0  0  1  0  0  0  1  0  0  0  0  0  1  0  0  1    4
27   0  0  0  1  1  0  0  1  0  1  0  0  0  1  1  0    6
28   0  0  1  0  1  0  1  0  0  0  1  0  1  0  1  0    6
29   0  1  0  0  0  1  0  0  1  0  0  0  0  0  0  0    3
31   0  0  0  0  0  0  0  1  0  0  1  0  0  0  1  0    3
32   0  1  0  1  0  1  0  0  0  1  0  1  0  1  0  0    6
33   0  1  1  0  0  0  1  0  1  0  0  1  1  0  0  0    6
35   1  0  0  1  0  0  0  0  0  1  0  0  0  1  0  0    4
36   1  0  1  1  0  1  1  1  1  0  1  1  0  1  1  1   12
37   0  0  0  0  0  0  1  0  0  0  0  0  1  0  0  1    3
39   1  0  0  0  1  0  0  1  0  1  1  0  0  1  0  0    6
40   0  0  1  0  1  0  1  1  0  0  1  0  1  0  1  1    8
41   0  0  0  0  0  1  0  0  1  0  0  1  0  0  0  0    3
43   0  0  0  0  1  0  0  0  0  0  1  0  0  0  1  0    3
44   1  1  0  0  0  1  0  0  1  1  0  0  0  1  0  0    6
45   0  1  1  0  0  1  1  0  1  0  0  1  1  0  0  1    8
47   0  0  0  1  0  0  0  0  0  1  0  0  0  1  0  0    3
48   1  1  1  1  1  0  1  0  1  1  1  1  1  0  1  0   12
49   0  0  1  0  0  0  0  0  0  0  0  0  1  0  0  1    3
51   1  0  0  1  0  0  0  1  0  0  1  0  0  1  1  0    6
52   0  0  0  0  1  0  1  1  0  0  0  0  1  0  1  1    6
53   0  1  0  0  0  0  0  0  1  0  0  1  0  0  0  0    3
55   0  0  0  0  1  0  0  1  0  0  1  0  0  0  1  0    4
56   1  0  0  1  0  1  0  0  1  0  0  1  0  1  0  0    6
57   0  1  0  0  0  1  1  0  0  0  0  1  1  0  0  1    6
59   1  0  0  0  0  0  0  0  0  1  0  0  0  1  0  0    3

    16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16  256

axn · 2014-06-04, 08:18

Quote:

Originally Posted by LaurV

Ooo... happy to contradict you for the first time in my life!

There is no contradiction. Only confusion. Apparently, everyone has their own way of enumerating the classes. I was going by f, you're going by k, and god only know what James's data is going by. As per your table, class 0 should out number everything, but it is class 1 as per James's data.

Regardless, all the classes that are used for TF should have equal probability of a factor (actually, earlier class should have slightly better chance, since we stop factoring as soon as we find a factor). So there is no difference in changing the order in which classes are TF'ed (chalsall's idea).

ET_ · 2014-06-04, 09:20

Quote:

Originally Posted by axn

There is no contradiction. Only confusion. Apparently, everyone has their own way of enumerating the classes. I was going by f, you're going by k, and god only know what James's data is going by. As per your table, class 0 should out number everything, but it is class 1 as per James's data.

Regardless, all the classes that are used for TF should have equal probability of a factor (actually, earlier class should have slightly better chance, since we stop factoring as soon as we find a factor). So there is no difference in changing the order in which classes are TF'ed (chalsall's idea).

Can I assue that ALL TF done with mfaktc was completed? Or there may be cases where TF has been interrupted right after finding a factor, without completing the bit level?

Luigi

LaurV · 2014-06-04, 11:38

There is only one way to enumerate "classes", and that is "by k". The term was coined by Oliver long ago, when he did first mfaktc. The "960 classes", "4620 classes", etc, are related to k. Otherwise how do you explain "even" classes? Because q (or f, as per axn said) is always odd prime and 1,7 mod 8... The "classes" here is what mfaktX is using, and they refer to modularity of k to 4620 (or 420, for the "less classes" version). We are interested what values k can take, once p is given, those are "candidate classes" and those we are sieving, powering, blah blah.

James Heinrich · 2014-06-04, 13:53

Quote:

Originally Posted by ET_

Can I assue that ALL TF done with mfaktc was completed? Or there may be cases where TF has been interrupted right after finding a factor, without completing the bit level?

From my data you can assume nothing. It might have had the bitlevel completed, it might have aborted after finding the first factor. Remember also that I make no claim that all these factors were found by mfaktx, only that they're in the range of interest to us and they could have been found by mfaktx.

2014-06-04, 03:13	#2984
LaurV Romulan Interpreter Jun 2011 Thailand 22677₈ Posts	Just for the sake of clarifying (or say, side discussion, which do not need to influence the already-made bench), the factors do not "spread evenly" in classes. When p vary on the whole range (to 10^9 in our case), we can have, for any 92160 factors: 960 in class 0, 135 in class 1, 0 in class 2 (and all 4k+2 classes, they will have 0 factors), 270 in class 3 and 4, 180 in class 5, 0 on class 6, 162 in class 7, and so on (this are real, statistical numbers, from the modular calculus, and not example values which are fabricated to "give an idea"). So, some classes have "higher probability" to contain factors, which seems somehow normal, as no factor can be even, no factor can be 3 or 5 mod 8, etc. Last fiddled with by LaurV on 2014-06-04 at 03:14

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Status	Primeinator	Operation Billion Digits	5	2011-12-06 02:35
62 bit status	1997rj7	Lone Mersenne Hunters	27	2008-09-29 13:52
OBD Status	Uncwilly	Operation Billion Digits	22	2005-10-25 14:05
1-2M LLR status	paulunderwood	3*2^n-1 Search	2	2005-03-13 17:03
Status of 26.0M - 26.5M	1997rj7	Lone Mersenne Hunters	25	2004-06-18 16:46

2014-06-04, 03:58	#2986
axn Jun 2003 5085₁₀ Posts	We should expect the factors to be spread evenly. There is no mathematical reason not to. Unless ... P-1. P-1 factors are NOT expected to fall evenly between the various classes. The upshot is that candidates that has had a (failed) P-1 should behave "unevenly" when it comes to TF factors, and the candidates that haven't had P-1 should be "even". That's the theory, anyway. Can you do the analysis by removing the TF factors which had a prior P-1?

2014-06-04, 11:38	#2991
LaurV Romulan Interpreter Jun 2011 Thailand 3·3,221 Posts	There is only one way to enumerate "classes", and that is "by k". The term was coined by Oliver long ago, when he did first mfaktc. The "960 classes", "4620 classes", etc, are related to k. Otherwise how do you explain "even" classes? Because q (or f, as per axn said) is always odd prime and 1,7 mod 8... The "classes" here is what mfaktX is using, and they refer to modularity of k to 4620 (or 420, for the "less classes" version). We are interested what values k can take, once p is given, those are "candidate classes" and those we are sieving, powering, blah blah.