mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2015-04-23, 03:08   #12
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

I have implemented basically what I suggested as a script. It uses my pre-existing aliquot analysis module, together with some code copied from the spider glued to some new code to fully parse the FDB page on a number. (This latter flexibility isn't strictly required for the current simple testing a composite for 1 mod 4, but allows future extensions to other cases.)

https://github.com/dubslow/MersenneF...drivers.py#L87 is the gist of it. The rest of the script just gets my table data (http://dubslow.tk/aliquot/AllSeq.json) and runs through each sequence looking for drivers with class 2 and no extraneous prime factors, before passing it to the "analysis" function. As in the comment, aid with describing the cases to mutate a class 3 or 4 (or more) guide is appreciated.

Currently it outputs this:
Code:
 ./drivers.py 
Getting the current data
 62820 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^4 * C122
999558 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C137
360876 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C126
148008 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
786990 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C122
140256 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
591696 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C121
759456 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C119
592020 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C119
230856 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * 7^2 * C120
608820 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
838320 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C127
240810 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C122
 47352 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C118
162120 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
845844 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^4 * 5 * C126
940632 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
645810 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C119
880512 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C144
517434 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 5^2 * 7^2 * C119
 39648 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C123
943182 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C127
 42084 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C117
223092 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
223398 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C126
386616 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
372060 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C121
 45672 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^4 * 5 * C119
971496 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C124
486960 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C118
848232 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
340956 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 5^2 * 7 * C120
481632 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C120
357000 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C120
537078 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C119
965040 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
506784 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
220992 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
752970 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C133
It would be nearly trivial for someone who knows Python to further organize the output (by driver or composite size, etc) but for now it's a small enough set that I don't feel like bothering. Maybe tomorrow.
Dubslow is offline   Reply With Quote
Old 2015-04-23, 05:56   #13
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52·73 Posts
Default

Stupid Question: Does 2^3*3^2*5 "breaks"? I had the "feeling" that you need 5^2 for a break.
(lunch "break" here, I don't actually have time now to do modular calculus, but almost all my reservations were initially (or still are) the (in)famous D3, and AFAIR, D3 does not break with 3^2, but I may be wrong...)
LaurV is offline   Reply With Quote
Old 2015-04-23, 06:01   #14
axn
 
axn's Avatar
 
Jun 2003

11×421 Posts
Default

2^3*3^2*5*p*q where both p and q are 1 (mod 4) will go from 2^3 to a *higher* power of 2. Because 5,p,and q will each contribute a 2 in terms of (5+1), (p+1) and (q+1), and hence the difference will be 2^3*odd - 2^3*odd = 2^3 * even.
axn is online now   Reply With Quote
Old 2015-04-23, 06:10   #15
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

857510 Posts
Default

, thanks a lot for correction. (You know, I was deciding for 20 seconds to end the former post or not, with the sentence: "axn?")
LaurV is offline   Reply With Quote
Old 2015-04-23, 06:22   #16
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Or in terms of the definitions at http://dubslow.tk/aliquot/analysis.html, the class of 2^3 * 3^2 * 5 is two, the same class as 2^3 * 3 * 5^2 (whereas the class of 2^3 * 3 * 5 is zero).
Dubslow is offline   Reply With Quote
Old 2015-04-23, 15:39   #17
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

The very first one I tried was succesful :) 486960 has lost its 2^2 * 7 !
Dubslow is offline   Reply With Quote
Old 2015-04-23, 18:59   #18
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts
Default

Quote:
Originally Posted by Dubslow View Post
It would be nearly trivial for someone who knows Python to further organize the output (by driver or composite size, etc)
https://github.com/dubslow/MersenneF...rivers.py#L137

Code:
./drivers.py 
Getting the current data
 42084 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C117
 47352 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C118
940632 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
223092 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
608820 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
759456 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C119
592020 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C119
537078 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C119
148008 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
162120 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
645810 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C119
517434 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 5^2 * 7^2 * C119
140256 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
 45672 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^4 * 5 * C119
965040 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
506784 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
481632 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C120
230856 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * 7^2 * C120
386616 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
357000 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C120
340956 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 5^2 * 7 * C120
220992 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
848232 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
591696 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C121
372060 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C121
786990 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C122
240810 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C122
 62820 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^4 * C122
 39648 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C123
971496 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C124
360876 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C126
845844 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^4 * 5 * C126
223398 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C126
943182 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C127
838320 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C127
752970 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C133
999558 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C137
880512 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C144
Edit: In fact sorting by driver is accomplished by this very trivial diff:
Code:
diff --git a/website/py/drivers.py b/website/py/drivers.py
index ed48bb3..b666844 100755
--- a/website/py/drivers.py
+++ b/website/py/drivers.py
@@ -143,7 +143,7 @@ def main():
      data = read_data()
      targets = [data[seq] for seq in data if examine_seq(data[seq])]
      # OTOH targets is a list of the Sequence objects, so here seq is the objec
-     targets.sort(key=lambda seq: seq.cofact)
+     targets.sort(key=lambda seq: seq.guide)
      for seq in targets:
           print("{:>6} may have a driver that's ready to break (composite is 1

Last fiddled with by Dubslow on 2015-04-23 at 19:05
Dubslow is offline   Reply With Quote
Old 2015-04-25, 01:42   #19
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

1001111112 Posts
Thumbs down

I don't consider myself an expert in math, but I can use Wolfram|Alpha. My understanding, which may be incorrect (please correct me if it is), is that the 2s count of a composite number is the sum of the 2s counts of its factors. Also, the 2s count of a prime with a given power b is 0 if b is even, or s + c - 1 if b is odd, with s being the 2s count of the prime itself and c equaling the 2s count of the exponent. The 2s count of a prime p is the value s in the form s(2n + 1) of p + 1. Given that, a given cofactor and associated factors will break a driver when the 2s counts of the factors add up to a value less than or equal to the class of the driver.

Therefore, as we know, a class 2 driver will break if v is a prime of the form 4n+1 (2s count = 1), a prime of the form 8n+3 (2s count = 2), or a product of two primes, each of the form 4n+1 (2s count = 1+1 = 2). If I'm understanding this process right, a class 3 driver will break under any of the above circumstances, or if: v is a prime of the form 16n+7 (2s count = 3), the product of three primes of form 4n+1 (2s count = 3(1) = 3), or the product of one prime of form 4n+1 and another of form 8n+3 (2s count = 2+1 = 3). The break that occurs with a driver of class n when v is the product of ≤ n primes of form 4n+1 always holds, so the t \equiv 1 \pmod 4 test will always work. But a quick foiling of (4n+1)(8p+3) results in 4q+3, where q = 8np + 3n + 2p. That quickly renders such an additional test useless.
Happy5214 is offline   Reply With Quote
Old 2015-04-25, 06:23   #20
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

11×29 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
I don't consider myself an expert in math, but I can use Wolfram|Alpha. [...] Also, the 2s count of a prime with a given power b is 0 if b is even, or s + c - 1 if b is odd, with s being the 2s count of the prime itself and c equaling the 2s count of the exponent.


Obviously, I didn't mean to imply that c is the 2s count of the exponent when said exponent isn't prime itself. I should have said c is equal to n when representing the exponent in its Riesel form, k \cdot 2^n - 1.
Happy5214 is offline   Reply With Quote
Old 2015-04-25, 17:08   #21
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

I've made an update which prints drivers with class higher than 2 (no analysis yet, though your post is definitely appreciated ). There are 20-30 candidates of 2^3 * 3 (which I excluded from the output), with the rest pasted below.

Code:
./drivers.py 
Getting the current data
Sequence 672420 has a driver but also has class 3: 2^5 * 3 * 7^2 * C118
Sequence 158976 has a driver but also has class 3: 2^3 * 3^2 * 5^2 * C120
Sequence 961974 has a driver but also has class 3: 2^5 * 3 * 7^2 * C118
Sequence 661998 has a driver but also has class 3: 2^3 * 3^2 * 5^2 * C122
Sequence 681882 has a driver but also has class 3: 2^5 * 3 * 7^2 * C117
Sequence 258450 has a driver but also has class 3: 2^3 * 3^2 * 5^2 * C128
Sequence 290160 has a driver but also has class 3: 2^3 * 3^2 * 5^2 * C124
Sequence 151032 has a driver but also has class 3: 2^5 * 3 * 7^2 * C120
Sequence 587790 has a driver but also has class 3: 2^5 * 3 * 7^2 * C118
Sequence  81192 has a driver but also has class 3: 2^5 * 3 * 7^2 * C122
Sequence  48780 has a driver but also has class 3: 2^3 * 3^2 * 5^2 * C140
Sequence 383320 has a driver but also has class 3: 2^3 * 3^2 * 5^2 * C121
 42084 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C117
608820 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C118
 47352 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C118
759456 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C119
592020 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 3^2 * 7^2 * C119
148008 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
140256 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
645810 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C119
517434 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 5^2 * 7^2 * C119
 45672 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^4 * 5 * C119
537078 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C119
965040 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
162120 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
506784 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C119
230856 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * 7^2 * C120
481632 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C120
220992 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
386616 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
848232 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C120
357000 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C120
340956 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 5^2 * 7 * C120
591696 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C121
372060 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C121
 62820 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^4 * C122
786990 may have a driver that's ready to break (composite is 1 mod 4): 2^5 * 3^2 * 7 * C122
240810 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C122
 39648 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C123
971496 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C124
 50892 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C125
360876 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C126
223398 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C126
845844 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^4 * 5 * C126
943182 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C127
838320 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C127
752970 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C133
999558 may have a driver that's ready to break (composite is 1 mod 4): 2^2 * 7^2 * C137
880512 may have a driver that's ready to break (composite is 1 mod 4): 2^3 * 3^2 * 5 * C144

Last fiddled with by Dubslow on 2015-04-25 at 17:14
Dubslow is offline   Reply With Quote
Old 2015-05-03, 20:32   #22
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

At least three of the candidates I've tried failed on that particular exponent to break, but then did a few lines later anyways.

537078 lost its driver on the target composite, but then gained it back 15 lines later.... http://factordb.com/sequences.php?se...r=1175&to=1192
Dubslow is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 17:29.

Fri Jul 3 17:29:47 UTC 2020 up 100 days, 15:02, 2 users, load averages: 1.59, 1.65, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.