Search of all even-15-digit Aliquot cycles

[Drdmitry]

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):

       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_<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 self-explanatory. The most of the lines are as follows:

New cycle found!!
<number>
......
<number>

Which do not need explanation, I hope. In quite rare occasions (I never saw that happening) you may find the line

<number> 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 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:

  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

[firejuggler]

I will take the 1001-1010 range

[Drdmitry]

Originally Posted by firejuggler

I will take the 1001-1010 range

I am afraid, the range 1000 - 1499 has already been done

[firejuggler]

my bad then, i'll take the 100 001-100 150 range.

[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.

[henryzz]

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.

[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

[fivemack]

I'll run 2e7 .. 2e7+5e3 over the weekend

[Drdmitry]

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

Thank you for the comments.
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.

[Drdmitry]

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.

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.

[Sergei Chernykh]

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 10⁶ even numbers in the range [10¹⁵, 10¹⁵+2*10⁶) 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.