mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2016-11-23, 17:57   #1
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

111010102 Posts
Default 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_<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:

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

Code:
<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 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 <n1> <n2>
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
Drdmitry is offline   Reply With Quote
Old 2016-11-23, 18:43   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2·3·5·79 Posts
Default

I will take the 1001-1010 range
firejuggler is offline   Reply With Quote
Old 2016-11-24, 09:00   #3
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by firejuggler View Post
I will take the 1001-1010 range
I am afraid, the range 1000 - 1499 has already been done
Drdmitry is offline   Reply With Quote
Old 2016-11-24, 17:18   #4
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

1001010000102 Posts
Default

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

Last fiddled with by firejuggler on 2016-11-24 at 17:30
firejuggler is offline   Reply With Quote
Old 2016-11-24, 17:55   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2016-11-24, 18:03   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

569310 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
henryzz is offline   Reply With Quote
Old 2016-11-24, 18:10   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

635310 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2016-11-24, 18:38   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

I'll run 2e7 .. 2e7+5e3 over the weekend
fivemack is offline   Reply With Quote
Old 2016-11-25, 13:41   #9
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

3528 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 is offline   Reply With Quote
Old 2016-11-25, 14:10   #10
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

23410 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 View Post
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.
Drdmitry is offline   Reply With Quote
Old 2016-11-25, 14:40   #11
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

5316 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
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
Sergei Chernykh 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
Program for searching all odd-16-digit Aliquot cycles Drdmitry Aliquot Sequences 302 2016-05-11 02:17
Is a search for aliquot 3-cycles feasible? schickel Aliquot Sequences 7 2013-02-08 01:33
Small search of cycles with odd and even elements Drdmitry Aliquot Sequences 0 2011-12-14 13:50
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:42.

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

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.