View Single Post 2009-06-14, 23:04   #3
ATH
Einyen

Dec 2003
Denmark

319710 Posts Quote:
 Originally Posted by akruppa So it looks like those p with few factors in p-1 do, in fact, have a lower chance of surviving trial division. ATH, I assume the number of factors is the number of prime factors with multiplicity in p-1? It might be interesting to make such a table for the number of proper divisors of p-1 as well.
If you mean distinct prime factors, here is the list:
Code:
p-1 factors	Total(20M-30M)	numbers without factors to 2^66-2^68
--------------------------------------------------------------------
2 factors	49855		17960 = 36.02%
3 factors	173824		63988 = 36.81%
4 factors	218645		81127 = 37.10%
5 factors	118143		44684 = 37.83%
6 factors	25228		9692  = 38.42%
7 factors	1548		629   = 40.63%
8 factors	9		6     (=66.67%)
--------------------------------------------------------------------
Total		587252		218086
There is a clear rising percentage of numbers "surviving" trialfactor to 2^66-2^68, the more distinct prime factors p-1 has.

If you mean all factors (not just prime factors) then the list is extensive, here is whole list (not counting 1 and p-1 as factors of p-1): mersennetest.txt

Here is the list abbriviated by combining the factor-categories with low number of members in them:
Code:
p-1 factors	Total(20M-30M)	numbers without factors to 2^66-2^68
--------------------------------------------------------------------
2 factors	23895		8278 = 34.64%
4 factors	12264		4577 = 37.32%
6 factors	76473		27329 = 35.74%
7-8 factors	3355		1230 = 36.66%
10 factors	47504		17911 = 37.70%
12-13 factors	985		376 = 38.17%
14 factors	98842		35686 = 36,10%
16 factors	5377		2038 = 37.90%
18 factors	10600		3991 = 37.65%
19-22 factors	68947		25980 = 37.68%
23-26 factors	2651		946 = 35.68%
28 factors	1955		753 = 38.52%
30 factors	66115		24718 = 37.39%
31-34 factors	13651		5150 = 37.73%
36-38 factors	12384		4728 = 38,18%
40-46 factors	49363		18813 = 38.11%
48-54 factors	3795		1435 = 37.81%
58 factors	4090		1563 = 38.22%
61-62 factors	24317		9256 = 38.06%
64-70 factors	12353		4747 = 38.43%
73-78 factors	6840		2622 = 38.33%
79-94 factors	18451		6969 = 37.77%
96-106 factors	1528		577 = 37.76%
108-110 factors	1234		465 = 37.68%
118 factors	2806		1091 = 38.88%
124-126 factors	4652		1819 = 39.10%
128-142 factors	4558		1761 = 38.64%
148-158 factors	1635		634 = 38.78%
160-178 factors	951		361 = 37.96%
180-190 factors	2707		1076 = 39.75%
194-214 factors	659		272 = 41.27%
218-254 factors	1294		508 = 39.26%
258-286 factors	546		230 = 42.12%
292-318 factors	147		58 = 39.46%
322-358 factors	141		57 = 40.43%
376-382 factors	108		43 = 39.81%
394-430 factors	48		28 = 58.33%
446-478 factors	20		7 = 35.00%
502-574 factors	11		3 = 27.27%
--------------------------------------------------------------------
Total		587252		218086 (=37.14%)
The trend is not so clear here, since there is so many categories with more or less members in. But 39+% happens only for >124 factors and 40+% only for >194factors.

Last fiddled with by ATH on 2009-06-14 at 23:11  