mersenneforum.org Program for searching all odd-16-digit Aliquot cycles
 Register FAQ Search Today's Posts Mark Forums Read

 2015-06-21, 16:54 #1 Drdmitry     Nov 2011 24·3·5 Posts Program for searching all odd-16-digit Aliquot cycles I created a program for searching all Aliquot cycles with the 16d odd smallest elements. It can be downloaded here. It will take too long to complete the search on one computer however with help of a hundred cores it may be accomplished in about a half a year. If there is an interest in the distributed project, I am happy to coordinate it. The program usage is simple. Run the program with two parameters: the beginning and the end of the range to search. In total, the range between 0 and 31746032 should be completed in order to find all 16d odd Aliquot cycles. In the following table you can see, how fast various numbers a dealt with (the speed was measured on one core of my I5-3230M CPU): Code:  0 --- 151 hours 10 --- 39.8 hours 100 --- 14.4 hours 1000 --- 4.45 hours 10000 --- 1.22 hours 100000 --- 798 sec 1000000 --- 131 sec 10000000 --- 11.4 sec As you can see, bigger numbers are much faster dealt with than smaller ones. However smaller numbers produce more amicable numbers. The program produces the file output_odd_10e16__.txt, where n1 and n2 are the beginning and the end of the range to search. The easiest way is to send this file to me. I will then extract all new amicable pairs from it and send them to Pat Costello. If there are some new longer cycles I will send them to David Moews. I will also post a report in this thread. Surely a credit will be given to a discoverer in a standard way: &Bodyagin. You can also interpret the output file yourself. It is mostly self-explanatory. The most of the lines are as follows: Code: New cycle found!! ......  Which do not need explanation, I hope. In quite rare occasions you may find the line Code:  becomes too large. This means that a member of Aliquot sequence became so large that it could exceed 64 bit range. Therefore the program leaves the sequence incomplete. Another line which theoretically may appear is Code:  produces too long sequence This means that the sequence generated by became too long. In both cases the number needs to be dealt manually (for example by aliqueit). At the moment the whole range is pretty much untouched. I only completed individual numbers 0, 10, 100, 1000, 10000, 100000, 1000000 and 10000000 when computed the program speed. The program is compiled for 64 bit Windows system. I provide the C++ source code, so anyone can try to compile it on their own system. Mathematically the search is carried over as follows. All 16d numbers are tried as the smallest elements of the Aliquot cycle. Each number is represented as $3^{a_1} \cdot 5^{a_2} \cdot ... \cdot 41^{a_{12}} \cdot n$ where n is coprime with all small prime numbers up to 41. The line aliquot_odd_10e16.exe finds all cycles with $n1*10e6\le n\le n2*10e6$. Status: Code:  n-range tested by Status # cycles 00000000-00000000 Drdmitry Complete 221 00000001-00000001 Drdmitry Complete 119 00000002-00000002 AndrewWalker Complete 145 00000003-00000010 Drdmitry Complete 586 00000011-00000015 AndrewWalker Complete 271 00000016-00000020 AndrewWalker Complete 195 00000021-00000050 AndrewWalker Complete 833 00000051-00000099 AndrewWalker Complete 1024 00000100-00000100 Drdmitry Complete 21 00000101-00000109 Antonio Complete 142 00000110-00000169 Drdmitry Complete 903 00000170-00000209 Drdmitry Complete 489 + 1 non-amicable 00000210-00000334 Drdmitry Complete 1113 00000335-00000450 AndrewWalker Complete 866 00000451-00000499 Drdmitry Complete 335 00000500-00000540 firejuggler Complete 270 00000541-00000599 Drdmitry Complete 359 00000600-00000620 firejuggler Complete 138 + 1 non-amicable 00000621-00000699 Drdmitry Complete 398 00000700-00000730 firejuggler Complete 163 00000731-00000799 firejuggler Complete 315 00000800-00000899 Drdmitry Complete 482 00000900-00000999 frmky Complete 409 00001000-00001000 Drdmitry Complete 5 00001001-00001010 legendarymudkip Complete 43 00001011-00001099 frmky Complete 311 + 1 non-amicable 00001100-00001299 frmky Complete 747 00001300-00001499 AndrewWalker Complete 590 00001500-00001699 frmky Complete 545 00001700-00001899 frmky Complete 497 00001900-00002299 frmky Complete 897 00002300-00002699 frmky Complete 824 00002700-00003099 frmky Complete 726 00003100-00003139 Drdmitry Complete 74 00003140-00003539 frmky Complete 684 00003540-00003939 frmky Complete 554 00003940-00004339 frmky Complete 541 00004340-00004499 Drdmitry Complete 207 00004500-00004899 frmky Complete 503 00004900-00005699 frmky Complete 924 00005700-00009999 frmky Complete 3529 + 2 non-amicable 00010000-00010000 Drdmitry Complete 0 00010001-00010119 Antonio Complete 69 00010120-00010159 Antonio Complete 26 00010160-00010199 Antonio Complete 26 00010200-00010239 Antonio Complete 15 00010240-00011999 AndrewWalker Complete 1001 00012000-00012999 Drdmitry Complete 558 00013000-00013100 firejuggler Complete 43 00013101-00013700 Drdmitry Complete 303 00013701-00014200 Drdmitry Complete 250 00014201-00014700 Drdmitry Complete 228 00014701-00016000 Drdmitry Complete 600 00016001-00017400 Drdmitry Complete 658 + 1 non-amicable 00017401-00018200 Drdmitry Complete 338 00018201-00018800 Drdmitry Complete 238 00018801-00022400 Drdmitry Complete 1236 + 1 non-amicable 00022401-00023000 Drdmitry Complete 188 + 1 non-amicable 00023001-00024000 schickel Complete 333 00024001-00025000 Drdmitry Complete 318 00025001-00026000 Drdmitry Complete 292 00026001-00027000 Drdmitry Complete 243 00027001-00049999 Drdmitry Complete 4241 + 1 non-amicable 00050000-00069999 frmky Complete 2317 00070000-00099999 frmky Complete 2587 00100000-00100000 Drdmitry Complete 0 00100001-00160000 Drdmitry Complete 3352 + 1 non-amicable 00160001-00240000 Drdmitry Complete 2724 + 2 non-amicable 00240001-00440000 Drdmitry Complete 3092 + 2 non-amicable 00440001-01000000 Drdmitry Complete 3334 01000001-01199999 frmky Complete 613 01200000-01599999 frmky Complete 908 01600000-01999999 frmky Complete 511 02000000-02029999 RichD Complete 43 02030000-02032999 RichD Complete 4 02033000-02033999 RichD Complete 1 02034000-02099999 RichD Complete 97 02100000-02110000 schickel Complete 11 02110000-02999999 frmky Complete 666 03000000-03999999 frmky Complete 571 + 1 non-amicable 04000000-04999999 frmky Complete 424 05000000-06999999 frmky Complete 618 + 1 non-amicable 07000000-07999999 frmky Complete 193 08000000-08999999 frmky Complete 136 09000000-09999999 frmky Complete 102 10000000-10039999 Antonio Complete 5 10040000-16999999 frmky Complete 388 17000000-17999999 frmky Complete 51 18000000-18999999 RichD Complete 42 19000000-19999999 RichD Complete 43 20000000-20399999 RichD Complete 8 20400000-20799999 RichD Complete 23 20800000-21199999 RichD Complete 37 21200000-22999999 RichD Complete 32 23000000-24999999 RichD Complete 63 25000000-25999999 RichD Complete 32 26000000-26999999 RichD Complete 28 27000000-27999999 RichD Complete 31 28000000-28999999 RichD Complete 31 29000000-29999999 RichD Complete 27 30000000-30500000 Drdmitry Complete 17 30500000-30800000 firejuggler Complete 16 30800001-31299999 Happy5214 Complete 14 31300000-31499999 Happy5214 Complete 4 31500000-31599999 Happy5214 Complete 2 31600000-31649999 Happy5214 Complete 2 31650000-31659999 Happy5214 Complete 0 31660000-31669999 Antonio Complete 0 31670000-31689999 RichD Complete 0 31690000-31699999 Antonio Complete 0 31700000-31709999 henryzz Complete 0 31710000-31739999 Antonio Complete 1 31740000-31746032 henryzz Complete 0 Last fiddled with by Drdmitry on 2016-05-11 at 10:41
 2015-06-21, 18:19 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 5,857 Posts Sounds like a good idea. reserving 31740000-31746032 I am assuming the chance of success is proportional to the time spent rather than the range of n. Last fiddled with by henryzz on 2015-06-21 at 18:20
2015-06-21, 21:25   #3
Drdmitry

Nov 2011

24·3·5 Posts

Quote:
 Originally Posted by henryzz Sounds like a good idea. reserving 31740000-31746032 I am assuming the chance of success is proportional to the time spent rather than the range of n.
Great, thanks!
From my 15d search experience, the frequency of finding new amicable pairs slowly drops as n grows. From this pint of view smaller number may be more rewarding.

 2015-06-22, 02:17 #4 RichD     Sep 2008 Kansas 63648 Posts Bummer. Can't compile on Linux due to: fatal error: windows.h: No such file or directory. #include
 2015-06-22, 04:52 #5 Happy5214     "Alexander" Nov 2008 The Alamo City 26·32 Posts A few notes/questions: * What exactly is the platform-specific code? (What needs windows.h?) * Why do we need more implementations of mulmod, powmod, etc.? Isn't there a cross-platform library that can do this and, if there isn't a suitable one, can't we develop a small one to avoid this code duplication? * English comments later in the file would be nice. I can't read any East Slavic languages. That aside, this looks like a worthy project. I might work on this once we get a 64-bit Linux executable built.
2015-06-22, 08:29   #6
Drdmitry

Nov 2011

24×3×5 Posts

Quote:
 Originally Posted by Happy5214 A few notes/questions: * What exactly is the platform-specific code? (What needs windows.h?) * Why do we need more implementations of mulmod, powmod, etc.? Isn't there a cross-platform library that can do this and, if there isn't a suitable one, can't we develop a small one to avoid this code duplication? * English comments later in the file would be nice. I can't read any East Slavic languages. That aside, this looks like a worthy project. I might work on this once we get a 64-bit Linux executable built.
The most of platform-specific code appeared in the program because of the need to implement the mulmod function. x64 processors can multiply two 64 bit numbers modulo another 64 bit number just in two basic assembler operations, which is much faster than the standard long arithmetic routine. If one can provide a fast cross-platform implementation of this function that would be great.

In my implementation of mulmod, unfortunately, I did not manage to write it straight in assembler (perhaps because of my poor knowledge of how to add assembler code to a C++ program). I used VC++ intrinsic _mul128 for multiplication and some dirty hack found somewhere on the internet for taking the remainder. Nevertheless this combination worked about ten times faster than if NTL library is used. I did not try GMP but I expect that my mulmod will work significantly faster.

I also used GetTickCount() function from windows.h to measure the time spent by certain procedures. I am sure that this part can easily be made platform independent.

 2015-06-22, 09:03 #7 Antonio     "Antonio Key" Sep 2011 UK 53110 Posts reserving 31730000-31739999 Approx. 10hrs work.
2015-06-22, 09:51   #8
Drdmitry

Nov 2011

24·3·5 Posts

Quote:
 Originally Posted by Antonio reserving 31730000-31739999 Approx. 10hrs work.
Thanks, noted.
I see that not including the upper limit to the search may cause a confusion. For example, with current reservation the number 31739999 will not be covered. Will be fixed in a minute.

2015-06-22, 10:12   #9
Antonio

"Antonio Key"
Sep 2011
UK

32×59 Posts

Quote:
 Originally Posted by Drdmitry Thanks, noted. I see that not including the upper limit to the search may cause a confusion. For example, with current reservation the number 31739999 will not be covered. Will be fixed in a minute.

My bad, I read what I expected to be there, not what was actually there.

2015-06-22, 10:26   #10
Drdmitry

Nov 2011

24·3·5 Posts

Quote:
 Originally Posted by Antonio My bad, I read what I expected to be there, not what was actually there.
I already checked that 31739999 does not give any cycles. So no need to worry about that.

2015-06-22, 13:59   #11
Antonio

"Antonio Key"
Sep 2011
UK

53110 Posts

Quote:
 Originally Posted by Drdmitry No problem, I already fixed it and reuploaded the program. I already checked that 31739999 does not give any cycles. So no need to worry about that.
OK, thanks.
(Now the last line of your first post is wrong then !)

 Similar Threads Thread Thread Starter Forum Replies Last Post Drdmitry Aliquot Sequences 124 2017-07-02 02:48 Drdmitry Aliquot Sequences 25 2016-12-16 15:26 schickel Aliquot Sequences 7 2013-02-08 01:33 schickel Aliquot Sequences 23 2011-05-16 23:13 R. Gerbicz Math 0 2010-07-01 12:30

All times are UTC. The time now is 04:03.

Sun Apr 18 04:03:41 UTC 2021 up 9 days, 22:44, 0 users, load averages: 2.17, 2.29, 2.14