20161123, 17:57  #1 
Nov 2011
11101010_{2} Posts 
Search of all even15digit Aliquot cycles
I created a program for searching all Aliquot cycles which element preceding the maximal number of the cycle is 15 digits long and is even. It can be downloaded here. It takes considerably longer than the previous project on 16d odd cycles however it seems to me the most feasible option for exhaustive search of small aliquot cycles. I will definitely pursue this project for some time and I am happy to coordinate it if other people join.
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 83333333 should be completed in order to find all 15d even Aliquot cycles. However there is very low chance of finding anything in the range between 50000000 and 83333333 (in that case the number in the cycle should be divisible by 12 and there are only three such cycles known at the moment). In the following table you can see, how fast various numbers are dealt with (the speed was measured on one core of I74790 CPU): Code:
0  31 days 10  long (approx. 10 days) 100  69 hours 1000  23.4 hours 10000  7.47 hours 100000  102.78 min 1000000  21.43 min 10000000  154 sec The program produces the file output_even_10e15_<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 cycles (if any) from it and 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 selfexplanatory. The most of the lines are as follows: Code:
New cycle found!! <number> ...... <number> Code:
<number> produces too long sequence The program is compiled for 64 bit Windows system. I provide the C++ source code for Windows and an adapted code for Linux, so everyone can try to compile it on their own system. Mathematically the search is carried over as follows. All 15d numbers are tried as the elements preceding the largest term of the Aliquot cycle. Each number is represented as where n is coprime with all small prime numbers up to 53. The line aliquot_even_10e15.exe <n1> <n2> finds all cycles with . All completed and reserved ranges are on the list below: Code:
nrange tested by Status cycles of length>4 found? 0000000000000000 Drdmitry Complete 0 0000000100000004 Drdmitry Complete 0 0000010000000106 Drdmitry Complete 0 0000010700000120 Drdmitry Complete 0 0000012100000140 Drdmitry Complete 0 0000014100000200 Drdmitry Complete 0 0000100000001499 Drdmitry Complete 0 0001000000012000 Drdmitry Complete 0 0010000000100000 Drdmitry Complete 0 0010000100100150 firejuggler Complete 0 0100000001000000 Drdmitry Complete 0 0100000001000200 fivemark Complete 0 0100020101000749 firejuggler Complete 0 1000000010000000 Drdmitry Complete 0 2000000020005000 fivemack Complete 0 Last fiddled with by Drdmitry on 20170117 at 11:47 
20161123, 18:43  #2 
Apr 2010
Over the rainbow
2·3·5·79 Posts 
I will take the 10011010 range

20161124, 09:00  #3 
Nov 2011
2·3^{2}·13 Posts 

20161124, 17:18  #4 
Apr 2010
Over the rainbow
100101000010_{2} Posts 
my bad then, i'll take the 100 001100 150 range.
Last fiddled with by firejuggler on 20161124 at 17:30 
20161124, 17:55  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
6,353 Posts 
This is really quite a big project (since, whilst the runtime gets quicker as N gets larger, the number of N to do gets larger quicker).
Thirty CPUyears for 10^4..10^5, another 60 or so for 10^5..10^6 Up to 10^6 it's about equivalent to factoring a single 195digit number by GNFS. 
20161124, 18:03  #6  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
5693_{10} Posts 
Quote:


20161124, 18:10  #7 
(loop (#_fork))
Feb 2006
Cambridge, England
6353_{10} Posts 
Small problem with the Linux version, it is trying to open iqs_even_10e15.txt and the file that's distributed and that's opened by the Windows version is iqs_even_e15.txt. I've renamed the file but I don't know whether that was the right answer.
(it is worth saying that the gennar() call at the start takes about ten minutes no matter how wide a range you're doing, so you might want to do a wide range at the higher numbers) Each process takes a little under a gigabyte virtual, a little under half a gigabyte physical memory Last fiddled with by fivemack on 20161125 at 10:55 
20161124, 18:38  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
6,353 Posts 
I'll run 2e7 .. 2e7+5e3 over the weekend

20161125, 13:41  #9  
Nov 2011
352_{8} Posts 
Quote:
Yes, renaming iqs_even_10e15.txt file is the right thing to do. I updated the source code for Linux so that it reads the file with the same name as the windows version. Based on your comments I also noticed that Windows and Linux versions were tuned slightly differently. Linux version precomputes twice more factorisations than the Windows one. According to my tests (based on 10e15 odd numbers), it should give approx 2  5% time improvement during the main search, however it also uses twice more memory and it essentially increases the time of the precomputation step. (That was 366 MB on my computer per process). I changed the parameters of the Linux version so that they are (hopefully) the same as in Windows one. In the source code one can tune it manually by changing the constant narlen. But be aware that increasing it will have a tiny improvement in speed of the main procedure, on the other hand it will considerably increase the memory usage and the time of the precomputation step. I also removed several lines from iqs_even_e15.txt file which will not provide any extra Aliquot cycles. That should give a considerable improvement of the speed for big ranges (starting from 1e7) and will be negligible (if at all visible) for small ranges (less than 1e6). After some time I will update the running time for the ranges in this thread. 

20161125, 14:10  #10  
Nov 2011
234_{10} Posts 
Quote:
I put it here because previously some people from the forum expressed their interest in it. I will also pursue it for some time. One can try to make the algorithms more efficient. During the term I do not have enough spare time for that, but I hope to think about it during Christmas or maybe summer vacations. The most promising step for improvement is the factorisation part. I use a combination of trial division and Pollard's rho method. I had not heard of factorisation algorithms which are more efficient for 15 digits numbers but maybe they exist. Making a BOINC project might be a very good idea. However I need some time to understand how that works, which I do not have during the termtime. I hope to spent some time on it later. 

20161125, 14:40  #11  
Jun 2015
Stockholm, Sweden
53_{16} Posts 
Quote:
It factorized 10^{6} even numbers in the range [10^{15}, 10^{15}+2*10^{6}) in 3.72 seconds on a single core of Intel Xeon E51650 v3 (which has about the same performance as i74790 on singlethreaded code). So it's ~268,000 factorizations per second. If you're interested, I can prepare this code as a standalone library. P.S. I also have an implementation of GCD which is ~1.8 times faster than the classic one. Last fiddled with by Sergei Chernykh on 20161125 at 14:44 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Aliquot cycles search, the state of the art.  Drdmitry  Aliquot Sequences  124  20170702 02:48 
Program for searching all odd16digit Aliquot cycles  Drdmitry  Aliquot Sequences  302  20160511 02:17 
Is a search for aliquot 3cycles feasible?  schickel  Aliquot Sequences  7  20130208 01:33 
Small search of cycles with odd and even elements  Drdmitry  Aliquot Sequences  0  20111214 13:50 
Jan Munch Pedersen's Tables of Aliquot Cycles  R. Gerbicz  Math  0  20100701 12:30 