mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-07-03, 14:56   #1
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

12478 Posts
Default An alternative to Aliqueit: suli.sage

I would like to propose here a program that computes an aliquot sequence.
This program does the same job as Aliqueit and is very easy to use.
It has been written by Paul Zimmermann, Olivier Huber and myself.
I have been using this program for years to calculate my aliquot sequences.
It uses successively all the methods to decompose a cofactor: trivial division, ECM method, NFS method.
This program is written in python and runs on Sage software.
It uses CADO-NFS if the previous methods have failed.
You will find all the necessary explanations to run and understand this program at the beginning of the "suli.sage" file, before the lines of code and throughout the program, in comments.


To run the suli.sage program, you just need:
1) Sage software installed on your computer
2) CADO-NFS software installed on your computer
3) The program "suli.sage" as an attachment to this post
4) The file "Primes.sage" as an attachment to this post


Let me show you an example:

On FactorDB, I can see that the last calculated term of the sequence 15015^6 is the one from iteration 848. It is : 9834981195673212985850621515773881423695219406241982369361863287701490658008404
So I launch the program "suli.sage" in the Sage software and I enter the appropriate data, as shown below in red color, here is what is displayed on the screen, in a Linux terminal:
Code:
garambois@floyd:~/sage-9.2$ ./sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24                     │
│ Using Python 3.8.5. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
sage: load("suli.sage")                                                                                                                                                                                                                      
xxxx = 1506
sage: s(848,9834981195673212985850621515773881423695219406241982369361863287701490658008404)                                                                                                                                                 
nc = 79 848 : 9834981195673212985850621515773881423695219406241982369361863287701490658008404 = 2^2 * 7 * 620830117 * 134880003421560070199 * 4194644477098154235447597837635955172811101649521
nc = 79 849 : 9834981227356538025697171875443129565161408048590815310621637942961822518586796 = 2^2 * 7 * 19 * 870488609 * 21237275970304347993093724113547184338922553651503141966374851282767
nc = 80 850 : 10870242432969291115143007088281061579193350092246266485633750412982822746590804 = 2^2 * 7 * 19 * 1382629 * 35537 * 2504483297898847 * 166043941469329058646809126765680559827530572379187
nc = 80 851 : 12015138999456749827049331786782932118250313246365078301135223774111857791316396 = 2^2 * 7 * 19 * 43 * 16073559587 * 32676583829742768590018336553437103309035269548473804120997651983
nc = 80 852 : 13868146974055485756034888721717456119245724871292353356262517365289167834017364 = 2^2 * 7^2 * 73 * 43313 * 17390071 * 1286826167320431935505408307858311345552908252442283691966335771
***************** Start date of the NFS calculation : '03/07/2021 16h01m00s' ----> c<68> = 22696262584436328671561330441004133588421573181264880696681931475577
***************** End date of the NFS calculation   : '03/07/2021 16h05m20s' ----------------> 259 seconds of NFS calculation time
nc = 80 853 : 14750834355786985984121837337265792330239579109687166198205614729340141538074412 = 2^2 * 7^3 * 353 * 643 * 2087 * 17922206484641885638332779 * 1266376581694083540336190056720393495099563
nc = 80 854 : 15499626992695116294186359364900530887730021680636792371900446163490069802213588 = 2^2 * 7^2 * 103 * 173 * 229459 * 19340903185707608851452370571418185507591631891118154913795592594693
***************** Start date of the NFS calculation : '03/07/2021 16h05m20s' ----> c<65> = 16012104842963537403428102301175103007524147893719251987746696589
***************** End date of the NFS calculation   : '03/07/2021 16h08m34s' ----------------> 193 seconds of NFS calculation time
nc = 80 855 : 16543819665098579849395229198941863300041001863996459951005870582000334290099372 = 2^2 * 7^2 * 37 * 142472015099 * 166994662550252228975007955404633393884707 * 95883931848092187408527
nc = 80 856 : 18044899828004740041174363266640982892925154491525182525178856298931407889369428 = 2^2 * 7 * 647 * 2144479 * 4614939529 * 8799206058473 * 11438283673857752838194383751930323051188172331
nc = 80 857 : 18100696906872936180990656984712461140177713267356883075635232444610976310720172 = 2^2 * 7 * 53 * 263 * 10243135432861811 * 4527648796911094648053703968215803626066910785978130609781
nc = 80 858 : 18923987088303274937174659333083731860418284047442116917790897964301191672026452 = 2^2 * 7^2 * 1171 * 2814629 * 3888268193 * 17821019750305867 * 422755974987799284941934487254761346606353
nc = 80 859 : 19632755711647289404507618341609341743370302854726248308820474006802608490881068 = 2^2 * 7^3 * 23 * 53 * 1900711 * 10005573517 * 514663930861 * 11739317787004978291307 * 102164209345375098914099
nc = 80 860 : 22964998873884361280163188816667533641127553779341637325570024557629819663998932 = 2^2 * 7 * 53 * 15475066626606712452940154189129065795908055107373070974103790133173732927223
nc = 80 861 : 23831602604974337177527837451258761325698404865354529300119836805087548707926444 = 2^2 * 7 * 1171 * 8960213 * 81118514361214627652993796103995075562249438434396376068264340481651
nc = 80 862 : 23872310922292194084905524384590727720670579751649816997558776975150457747303252 = 2^2 * 7 * 1553 * 220901 * 1361385761578807 * 31355630992474277 * 58219777902756755883259558893933344077
nc = 80 863 : 23903270675628010920826582992679605823445684157394302245611593063965062359724204 = 2^2 * 7 * 31 * 467 * 40864233314098999799 * 1443036673459623249050534246244426468498140898671720791
nc = 80 864 : 25551088879280477240955419060190725994065220071286890124929891757109150781165396 = 2^2 * 7 * 587 * 8839 * 1377860041 * 127645362413056519221101336101236799114660586888629334807561239
***************** Start date of the NFS calculation : '03/07/2021 16h08m59s' ----> c<66> = 140048845024977140312663396010915583576968856428824381832568891259
***************** End date of the NFS calculation   : '03/07/2021 16h12m43s' ----------------> 224 seconds of NFS calculation time
nc = 80 865 : 25643936729804859854260040314080278325626105053609547697481973536811907446956204 = 2^2 * 7 * 198427 * 32956901 * 219940303680263346367468832107425559 * 636758441638655521793188522301
 ***************** Start date of the NFS calculation : '03/07/2021 16h12m49s' ----> c<78> = 915864169938382169627039102255551435028819070188430460234826037290192040590147
Here, I interrupted the calculation when an NFS decomposition was run on CADO-NFS at index 865.
If this interruption had been caused by a power failure, I could have retrieved all the results in the files "suli1506" and "suli1506last" see attached files.
Note that I can calculate as many different aliquot sequences as I want, simultaneously on one computer.
I just have to make sure to change the 4-digit number "xxxx" at the beginning of the suli.sage program.
For each sequence this number must be different.
You can put any 4-digit number, but here I found it better if the 4-digit number gives me information about the identity of the calculated sequence.
As it was the sequence 15015^6, I have chosen xxxx=1506.

Do not hesitate if you have any questions !
Attached Files
File Type: zip suli.sage.zip (4.0 KB, 46 views)
File Type: zip Primes.sage.zip (203.7 KB, 44 views)
File Type: zip suli1506.zip (1.7 KB, 39 views)
File Type: zip suli1506last.zip (179 Bytes, 35 views)
garambois is offline   Reply With Quote
Old 2021-07-05, 13:31   #2
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1100011102 Posts
Default

Great, thanks! I'll try it soon.

But eve before that I have comments. :) Would it be possible to write CADO NFS output to screen? For short factorizations it's ok like this and really long ones I'd do manually anyway, but for intermediate ones of a few hours, having an ETA would be nice.

Or is it written to a file I could tail?

And one small feature which might be easy to implement, could you add parsing of simple operations such as powers?
bur is offline   Reply With Quote
Old 2021-07-05, 17:02   #3
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

10101001112 Posts
Default

Quote:
Originally Posted by bur View Post
But eve before that I have comments. :) Would it be possible to write CADO NFS output to screen? For short factorizations it's ok like this and really long ones I'd do manually anyway, but for intermediate ones of a few hours, having an ETA would be nice.
I modified some lines of the program so that you can see the CADO-NFS output, see the attached file "suli_nfsoutput.sage".
If you prefer this second version, please let me know, because I think I'll have to remove some more lines that are no longer needed (lines that display the error message if the NFS calculation fails).


Quote:
Originally Posted by bur View Post
And one small feature which might be easy to implement, could you add parsing of simple operations such as powers?
I'm sorry, but I don't understand your request ?
My English betrays me !
Attached Files
File Type: zip suli_nfsoutput.sage.zip (4.0 KB, 51 views)

Last fiddled with by garambois on 2021-07-05 at 17:04 Reason: Forgot the attachment !
garambois is offline   Reply With Quote
Old 2021-07-05, 17:12   #4
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

7×97 Posts
Default

IMPORTANT :

I forgot to mention one important thing in the very first post.
From time to time you have to go and delete the old files called "cado.xxxx" in the folder "DIR/travail/" (DIR is the folder containing CADO_NFS).
You should delete these files when you have finished the calculations for a sequence.
If this is not done, the hard disk will fill up quickly.
garambois is offline   Reply With Quote
Old 2021-07-06, 12:17   #5
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×199 Posts
Default

Thanks for the cado output!

By my second comment I meant that it would be possible to use 2^20 as input instead of 1048576. Similar to what yafu does. Depending on sage's ability I think it might be either very easy to implement or quite some work.

Last fiddled with by bur on 2021-07-06 at 12:17
bur is offline   Reply With Quote
Old 2021-07-06, 17:04   #6
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

2A716 Posts
Default

Quote:
Originally Posted by bur View Post
By my second comment I meant that it would be possible to use 2^20 as input instead of 1048576. Similar to what yafu does. Depending on sage's ability I think it might be either very easy to implement or quite some work.
This is not a problem at all : you can very well calculate the aliquot sequence 2^20 with this input:
s(0,2^20)
Or even any sequence with any arithmetic expression, as long as your number is an integer.
An example :
Code:
sage: load("suli.sage") 
xxxx = 3654
sage: s(0,2^20)
nc = 7 0 : 1048576 = 2^20
nc = 7 1 : 1048575 = 3 * 5^2 * 11 * 31 * 41
nc = 6 2 : 951297 = 3 * 31 * 53 * 193
nc = 6 3 : 389631 = 3 * 11 * 11807
nc = 6 4 : 177153 = 3 * 59051
nc = 5 5 : 59055 = 3 * 5 * 31 * 127
nc = 5 6 : 39249 = 3^2 * 7^2 * 89
nc = 5 7 : 27441 = 3^2 * 3049
nc = 5 8 : 12209 = 29 * 421
nc = 3 9 : 451 = 11 * 41
sage: s(0,(2+10)^(10-5)-1)
nc = 6 0 : 248831 = 11 * 22621
nc = 5 1 : 22633 = 13 * 1741
nc = 4 2 : 1755 = 3^3 * 5 * 13
nc = 4 3 : 1605 = 3 * 5 * 107
nc = 3 4 : 987 = 3 * 7 * 47
nc = 3 5 : 549 = 3^2 * 61
sage:
garambois is offline   Reply With Quote
Old 2021-07-10, 18:40   #7
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×199 Posts
Default

Everything seems to work well. Just for clarification, the index I give in s(i,n) is just to format the output? It doesn't seems to get terms from factordb. So how do I upload the new terms to factordb?
bur is offline   Reply With Quote
Old 2021-07-11, 05:30   #8
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

39810 Posts
Default

And one more thing, is ECM is only done with one thread?
bur is offline   Reply With Quote
Old 2021-07-16, 14:37   #9
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

7×97 Posts
Default

I have a tiny bit of access time to my computer and I'm doing some quick answers today.
I won't be able to answer any more messages until early August.


Quote:
Originally Posted by bur View Post
Everything seems to work well. Just for clarification, the index I give in s(i,n) is just to format the output? It doesn't seems to get terms from factordb. So how do I upload the new terms to factordb?
The best way is to enter a sequence that you want to calculate in FactorDB and then put in the program the right index i of the last term of the sequence and the right last term n of the sequence by doing a copy-paste.
But if you change the index i, the results will still be interpreted correctly by FactorDB.

Another possibility is to read the data for a sequence automatically from the program.
Please find attached a version of the program suli.sage that does this automatically, here for the sequence 276^5.
You only need to run this program after entering the value for "xxxx" as usual and then the value for "sequence".

To enter your results in FactorDB, you have to copy and paste the rows from the "sulixxxx" file into FactorDB.


Quote:
Originally Posted by bur View Post
And one more thing, is ECM is only done with one thread?
Unfortunately, yes, the ECM calculation is only done on a single thread at the moment.
I had tried to do these calculations on multiple threads, but failed and didn't push it, because I don't yet have a computer with enough treads to do sequence calculations on multiple threads in parallel.
The sage software cannot use the ECM method on multiple threads.
So you have to download an ECM program from outside sage that can do this and call it as a subprocess, like we do for cado-NFS.


Don't hesitate to let me know if I don't answer your questions, but you may have to wait for my new answer until early August this time !
Attached Files
File Type: zip suli_nfsoutput_automatread.sage.zip (4.4 KB, 32 views)

Last fiddled with by garambois on 2021-07-16 at 14:39 Reason: Forgot the attached file !
garambois is offline   Reply With Quote
Old 2021-07-22, 07:13   #10
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

6168 Posts
Default

Thanks, regarding ECM, I think the original GMP-ECM also does not support multi-threading, at least yafu simply calls it several times simultaneously with different sigma values to achieve a multi-threading effect.

Maybe a similar thing could be done with suli?
bur is offline   Reply With Quote
Old 2021-08-02, 08:14   #11
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

12478 Posts
Default

Quote:
Originally Posted by bur View Post
Maybe a similar thing could be done with suli?
I haven't thought about this too much yet, since I work for all my sequences on a single thread.
If I have time, I'll do some testing during this August.
I'll let you know if I manage to reach my goal...
garambois is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aliqueit.exe discussion bsquared Aliquot Sequences 595 2021-07-01 23:23
Alternative to LL paulunderwood Miscellaneous Math 36 2019-08-26 08:09
Question about Sage's is_pseudoprime() function (Baillie-PSW) neomacdev Software 3 2019-07-15 23:22
Program for Sage enzocreti enzocreti 18 2018-12-06 05:34
Alternative CPU architecture henryzz Hardware 11 2018-07-10 07:33

All times are UTC. The time now is 23:57.


Fri Oct 15 23:57:12 UTC 2021 up 84 days, 18:26, 0 users, load averages: 1.20, 1.20, 1.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.