mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2015-06-21, 16:54   #1
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default 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_<n1>_<n2>.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: <discoverer>&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!!
<number>
......
<number>
Which do not need explanation, I hope. In quite rare occasions you may find the line
Code:
<number> 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:
<number> produces too long sequence
This means that the sequence generated by <number> 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 <n1> <n2>
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
Drdmitry is offline   Reply With Quote
Old 2015-06-21, 18:19   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

569310 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2015-06-21, 21:25   #3
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2×32×13 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Drdmitry is offline   Reply With Quote
Old 2015-06-22, 02:17   #4
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

2·5·7·43 Posts
Default

Bummer. Can't compile on Linux due to:

fatal error: windows.h: No such file or directory.
#include<windows.h>
RichD is offline   Reply With Quote
Old 2015-06-22, 04:52   #5
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

349 Posts
Default

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.
Happy5214 is offline   Reply With Quote
Old 2015-06-22, 08:29   #6
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
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.
Drdmitry is offline   Reply With Quote
Old 2015-06-22, 09:03   #7
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

32·59 Posts
Default

reserving 31730000-31739999
Approx. 10hrs work.
Antonio is offline   Reply With Quote
Old 2015-06-22, 09:51   #8
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by Antonio View Post
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.
Drdmitry is offline   Reply With Quote
Old 2015-06-22, 10:12   #9
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

32·59 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
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.
Antonio is offline   Reply With Quote
Old 2015-06-22, 10:26   #10
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

3528 Posts
Default

Quote:
Originally Posted by Antonio View Post
My bad, I read what I expected to be there, not what was actually there.
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.
Drdmitry is offline   Reply With Quote
Old 2015-06-22, 13:59   #11
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

53110 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
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 !)
Antonio is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aliquot cycles search, the state of the art. Drdmitry Aliquot Sequences 124 2017-07-02 02:48
Search of all even-15-digit Aliquot cycles Drdmitry Aliquot Sequences 25 2016-12-16 15:26
Is a search for aliquot 3-cycles feasible? schickel Aliquot Sequences 7 2013-02-08 01:33
BOINCify Aliquot searching? schickel Aliquot Sequences 23 2011-05-16 23:13
Jan Munch Pedersen's Tables of Aliquot Cycles R. Gerbicz Math 0 2010-07-01 12:30

All times are UTC. The time now is 01:44.

Fri Aug 7 01:44:11 UTC 2020 up 20 days, 21:30, 1 user, load averages: 1.17, 1.53, 1.63

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.