20150701, 10:35  #12 
Jun 2015
Stockholm, Sweden
83 Posts 
Hello everyone! I'm the one who did an exhaustive search of amicable pairs up to 10^{13} back in 20022003. I use my spare time now developing a highly optimized exhaustive search software with the aim to complete the search up to 10^{16}. It completes the search up to 10^{13} in just 5 hours on Core i74770K, so I estimate 10^{16} can be done in ~230 days on this PC alone.
What's even better is that I can run it distributed on 12 PCs in total. I estimate the search to be done in just 3 weeks on this cluster. I've already started the search and it's moving really fast, currently searching in the range 5800060000 for smaller member's largest prime factor. It has found 109963 pairs so far. I'll keep you posted :) 
20150701, 12:39  #13 
Mar 2015
Australia
1010010_{2} Posts 
Wow, that's impressive! I've been using David Einstein's program from around that same era, is yours based on a similar
approach or have you tried something different? Andrew 
20150701, 12:55  #14 
Jun 2015
Stockholm, Sweden
83_{10} Posts 
No, I wrote this program from scratch. I use all known speedup methods (mainly from 1986 te Riele paper, but not all of them actually improved performance on my hardware) + a couple of methods I used in 2002, and I did a really thorough optimization which includes compilerassisted replacement of divisions by multiplications and a lot of other programming tricks. The program perfectly fits in CPU cache and doesn't suffer from thread contention, so it's perfectly parallelizable. Actually, I'm much more experienced as a programmer than as a mathematician :)
P.S. I haven't seen David Einstein's program, but my approach is the same: recursively iterate over all factorizations of smaller member, going from smaller to larger prime factors. Last fiddled with by Sergei Chernykh on 20150701 at 13:10 
20150701, 15:14  #15 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}×3^{2}×19 Posts 

20150701, 16:48  #16  
Nov 2011
2×3^{2}×13 Posts 
Quote:


20150701, 17:44  #17  
Jun 2015
Stockholm, Sweden
123_{8} Posts 
Quote:
Drdmitry, it's only for amicable pairs. Factorization routine is just a trial division with compiletime replacement of division by multiplication for the first 64 primes and other speedups to detect ineligible numbers as soon as possible. P.S. Currently searching 102495  106129 for smaller member's largest prime factor, 122917 pairs found so far. Last fiddled with by Sergei Chernykh on 20150701 at 17:50 

20150703, 11:51  #18 
Mar 2015
Australia
2×41 Posts 
Sergei, it sounds like your program operates basically the same way as David's but his is purely c++. I'll mention two of the other main speed ups it uses:
 Table of primes p and 1/p (both in long double) it precomputes and uses for divisions. My present runs it uses primes up to 100 million.  When trial factoring the second number, at some point you can say the remaining factors are either p.q or p^2 . Here you can stop trial factoring. In the first case you know what p.q is. If you then assume the pair is amicable, you know sigma for the second number and hence what (p+1).(q+1) is. I don't know if any of the papers mention this. I'll keep doing the 16 digit even pairs for a short while, there won't be many but these and the others there will at least give you something to check your program against. I'll also submit what I've found through my breeder/BDE experiments, mainly because I want to know if it's finding much that is new, these will also have larger factors than the others I've found so they will also be useful for checking. (These also are not producing massive numbers of new pairs but the length goes much bigger!). As you would know lots of the pairs have most of their factors small. When I was searching back around 20022003 I tried another trick. I was searching 16 digit pairs with factors to 10 million, for odds this was slow and I only got to somewhere in the 3^2*... range. For evens it was even slower. For most amicable pairs if you factor the pair sum it has very small factors, even if the factors of the two numbers are large. This means that for the factors p in the numbers p+1 has very small factors. So what I tried was restricting my table of primes p for the first number to those where p+1 has all it's factors less than some limit say 100 or 1000. This will miss some pairs but for the rest it speeds things up and I was able to find a lot of even pairs back then. This trick may be useful if you go to 17 digits or higher and the total time looks too big. Just search for the easier ones and come back later for harder ones when you have a better program or more computers! I don't know for sure but I suspect this may also work for longer aliquot sequences, based on ones discovered in the past. This may be worth considering in the future if we search even values or longer than 16 digits for sequences as it lets you search the more likely candidate numbers first, and then come back for others later. Good luck! Andrew Last fiddled with by AndrewWalker on 20150703 at 11:58 
20150703, 13:41  #19  
Jun 2015
Stockholm, Sweden
83 Posts 
Quote:
As for speedups you mentioned:  I use compiletime precomputed table of first 64 primes and their reciprocals to speed up first trial divisions. Compiler embeds it directly in the assembly code, so it resides in code cache and doesn't interfere with data cache. I also have a table of all primes up to 269 million in a very compact form (1 byte/prime number). As for reciprocals, they'll be 8 bytes each and they'll have to be in the regular data cache and evict other data out of the cache. Using them might slow down things instead. But I'll test it.  Stopping when p^{3} is strictly greater than the second number (unfactored portion of it) seems to be a good idea. But my profiler tests show that my program spends < 1% of time that far in trial division, so it won't give a significant speedup. I'll test it too. I already verify my search daily. Here's the latest verification: Quote:
Last fiddled with by Sergei Chernykh on 20150703 at 13:52 

20150714, 13:45  #20 
Mar 2015
Australia
2×41 Posts 
Congratulations on all the new submissions Sergei! I submitted a few more Walker&Einstein pairs but they probably got covered by your ones. I've also submitted the first group from my breeder runs, I'll be lucky to get one or two new ones for the 15 digits but hopefully a few hundred for 16 digits (these generally have much larger factors). The largest pairs were in the 5059 digit range.
Unfortuneately my computer was starting to play up a bit last week so I'm in the process of setting up a new one, but it should be a bit quicker. Andrew 
20150714, 13:51  #21 
Jun 2015
Stockholm, Sweden
53_{16} Posts 
I'm almost done with the search. It's currently checking prime factors in the range ~1.65*10^{14}. I need to check all factors up to 5*10^{14} to complete the search, but it's extremely unlikely that anything exists in this range. (most likely) Final numbers are: 47728 15digit pairs, 103673 16digit pairs.

20150812, 16:40  #22 
Jun 2015
Stockholm, Sweden
83 Posts 
Pat has added all my new 15digit pairs and some of 16digit pairs, but he has issues with processing so many new pairs. I resubmitted remaining pairs in a format which suits his programs better.
P.S. I'm currently running an exhaustive search of 17digit pairs, it has reached prime factors ~4*10^{7}. I've submitted 209424 new 17digit pairs to Pat. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Search of all even15digit Aliquot cycles  Drdmitry  Aliquot Sequences  25  20161216 15:26 
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 