mersenneforum.org Search of all even-15-digit Aliquot cycles
 Register FAQ Search Today's Posts Mark Forums Read

 2016-11-23, 17:57 #1 Drdmitry     Nov 2011 111010102 Posts Search of all even-15-digit 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 I7-4790 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 As you can see, bigger numbers are much faster dealt with than smaller ones. The statistics for 14d cycles indicates that the most of cycles are expected to be inside 10000 - 1000000 range. However the amicable pairs are more densely packed within smaller ranges. The program produces the file output_even_10e15__.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: &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 (I never saw that happening) you may find the line Code:  produces too long sequence In that case the number needs to be dealt manually (for example with aliqueit). 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 $2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3} \cdot ... \cdot 53^{a_{16}} \cdot n$ where n is coprime with all small prime numbers up to 53. The line aliquot_even_10e15.exe finds all cycles with $n1*10e6\le n\le n2*10e6$. All completed and reserved ranges are on the list below: Code:  n-range tested by Status cycles of length>4 found? 00000000-00000000 Drdmitry Complete 0 00000001-00000004 Drdmitry Complete 0 00000100-00000106 Drdmitry Complete 0 00000107-00000120 Drdmitry Complete 0 00000121-00000140 Drdmitry Complete 0 00000141-00000200 Drdmitry Complete 0 00001000-00001499 Drdmitry Complete 0 00010000-00012000 Drdmitry Complete 0 00100000-00100000 Drdmitry Complete 0 00100001-00100150 firejuggler Complete 0 01000000-01000000 Drdmitry Complete 0 01000000-01000200 fivemark Complete 0 01000201-01000749 firejuggler Complete 0 10000000-10000000 Drdmitry Complete 0 20000000-20005000 fivemack Complete 0 Last fiddled with by Drdmitry on 2017-01-17 at 11:47
 2016-11-23, 18:43 #2 firejuggler     Apr 2010 Over the rainbow 2·3·5·79 Posts I will take the 1001-1010 range
2016-11-24, 09:00   #3
Drdmitry

Nov 2011

2·32·13 Posts

Quote:
 Originally Posted by firejuggler I will take the 1001-1010 range
I am afraid, the range 1000 - 1499 has already been done

 2016-11-24, 17:18 #4 firejuggler     Apr 2010 Over the rainbow 1001010000102 Posts my bad then, i'll take the 100 001-100 150 range. Last fiddled with by firejuggler on 2016-11-24 at 17:30
 2016-11-24, 17:55 #5 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 6,353 Posts This is really quite a big project (since, whilst the run-time gets quicker as N gets larger, the number of N to do gets larger quicker). Thirty CPU-years 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 195-digit number by GNFS.
2016-11-24, 18:03   #6
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

569310 Posts

Quote:
 Originally Posted by fivemack This is really quite a big project (since, whilst the run-time gets quicker as N gets larger, the number of N to do gets larger quicker). Thirty CPU-years 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 195-digit number by GNFS.
I do wonder whether it is worth boincifying this search.

 2016-11-24, 18:10 #7 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 635310 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 2016-11-25 at 10:55
 2016-11-24, 18:38 #8 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 6,353 Posts I'll run 2e7 .. 2e7+5e3 over the weekend
2016-11-25, 13:41   #9
Drdmitry

Nov 2011

3528 Posts

Quote:
 Originally Posted by fivemack 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
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.

2016-11-25, 14:10   #10
Drdmitry

Nov 2011

23410 Posts

Quote:
 Originally Posted by fivemack This is really quite a big project (since, whilst the run-time gets quicker as N gets larger, the number of N to do gets larger quicker). Thirty CPU-years 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 195-digit number by GNFS.
Quote:
 Originally Posted by henryzz I do wonder whether it is worth boincifying this search.
I agree that this is very heavy and lengthy project. And, unless someone with really huge computer power decides to join, it will not finish in a reasonable time. However there is a big chance of finding some new cycles. I personally want to find at least one more cycle of length different to four.

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 term-time. I hope to spent some time on it later.

2016-11-25, 14:40   #11
Sergei Chernykh

Jun 2015
Stockholm, Sweden

5316 Posts

Quote:
 Originally Posted by Drdmitry 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.
My factorization code uses exactly this combination: trial division up to fourth root of N and then 1 or 2 Pollard-Brent calls to get the remaining factors. I've just run a quick test on numbers you're interested in.

It factorized 106 even numbers in the range [1015, 1015+2*106) in 3.72 seconds on a single core of Intel Xeon E5-1650 v3 (which has about the same performance as i7-4790 on single-threaded 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 2016-11-25 at 14:44

 Similar Threads Thread Thread Starter Forum Replies Last Post Drdmitry Aliquot Sequences 124 2017-07-02 02:48 Drdmitry Aliquot Sequences 302 2016-05-11 02:17 schickel Aliquot Sequences 7 2013-02-08 01:33 Drdmitry Aliquot Sequences 0 2011-12-14 13:50 R. Gerbicz Math 0 2010-07-01 12:30

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

Fri Aug 7 01:42:52 UTC 2020 up 20 days, 21:29, 1 user, load averages: 1.46, 1.63, 1.67