mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2015-07-01, 10:35   #12
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Hello everyone! I'm the one who did an exhaustive search of amicable pairs up to 1013 back in 2002-2003. I use my spare time now developing a highly optimized exhaustive search software with the aim to complete the search up to 1016. It completes the search up to 1013 in just 5 hours on Core i7-4770K, so I estimate 1016 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 58000-60000 for smaller member's largest prime factor. It has found 109963 pairs so far.

I'll keep you posted :)
Sergei Chernykh is offline   Reply With Quote
Old 2015-07-01, 12:39   #13
AndrewWalker
 
AndrewWalker's Avatar
 
Mar 2015
Australia

10100102 Posts
Default

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
AndrewWalker is offline   Reply With Quote
Old 2015-07-01, 12:55   #14
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

8310 Posts
Default

No, I wrote this program from scratch. I use all known speed-up 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 compiler-assisted 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 2015-07-01 at 13:10
Sergei Chernykh is offline   Reply With Quote
Old 2015-07-01, 15:14   #15
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23×32×19 Posts
Default

Quote:
Originally Posted by Sergei Chernykh View Post
It completes the search up to 1013 in just 5 hours on Core i7-4770K
So if I'm right that's 20 core hours, since it has got 4 cores.
R. Gerbicz is offline   Reply With Quote
Old 2015-07-01, 16:48   #16
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2×32×13 Posts
Default

Quote:
Originally Posted by Sergei Chernykh View Post
Hello everyone! I'm the one who did an exhaustive search of amicable pairs up to 1013 back in 2002-2003. I use my spare time now developing a highly optimized exhaustive search software with the aim to complete the search up to 1016. It completes the search up to 1013 in just 5 hours on Core i7-4770K, so I estimate 1016 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 58000-60000 for smaller member's largest prime factor. It has found 109963 pairs so far.

I'll keep you posted :)
That is indeed impressive. I understand that your program can not find longer cycles. However maybe some parts of it (like factorisation routine) can be used for finding longer cycles? I would be very interested in speeding up my program for finding such cycles.
Drdmitry is offline   Reply With Quote
Old 2015-07-01, 17:44   #17
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

1238 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
So if I'm right that's 20 core hours, since it has got 4 cores.
It's 25 core hours because it's 5 times faster on those 4 cores + HT (virtual 8 cores).

Drdmitry, it's only for amicable pairs. Factorization routine is just a trial division with compile-time 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 2015-07-01 at 17:50
Sergei Chernykh is offline   Reply With Quote
Old 2015-07-03, 11:51   #18
AndrewWalker
 
AndrewWalker's Avatar
 
Mar 2015
Australia

2×41 Posts
Default

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 2002-2003 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 2015-07-03 at 11:58
AndrewWalker is offline   Reply With Quote
Old 2015-07-03, 13:41   #19
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Quote:
Originally Posted by AndrewWalker View Post
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.
My program is also purely C++. It's heavily templated though to take advantage of compile-time optimizations, and uses some compiler intrinsics.

As for speedups you mentioned:
- I use compile-time 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 p3 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:
Pairs with smaller member's largest prime factor <= 1176113
Checking against known pairs
0 known pairs missed
c2_3.txt: 100% covered
c2_4.txt: 100% covered
c2_5.txt: 100% covered
c2_6.txt: 100% covered
c2_7.txt: 100% covered
c2_8.txt: 100% covered
c2_9.txt: 99.7143% covered
c2_10.txt: 98.5731% covered
c2_11.txt: 96.9158% covered
c2_12.txt: 95.7462% covered
c2_13.txt: 92.5281% covered
c2_14.txt: 89.2976% covered
c2_15.txt: 86.6471% covered, 18 new pairs found
c2_16.txt: 91.4885% covered, 48045 new pairs found
48063 new pairs found

Last fiddled with by Sergei Chernykh on 2015-07-03 at 13:52
Sergei Chernykh is offline   Reply With Quote
Old 2015-07-14, 13:45   #20
AndrewWalker
 
AndrewWalker's Avatar
 
Mar 2015
Australia

2×41 Posts
Default

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 50-59 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
AndrewWalker is offline   Reply With Quote
Old 2015-07-14, 13:51   #21
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

5316 Posts
Default

I'm almost done with the search. It's currently checking prime factors in the range ~1.65*1014. I need to check all factors up to 5*1014 to complete the search, but it's extremely unlikely that anything exists in this range. (most likely) Final numbers are: 47728 15-digit pairs, 103673 16-digit pairs.
Sergei Chernykh is offline   Reply With Quote
Old 2015-08-12, 16:40   #22
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Pat has added all my new 15-digit pairs and some of 16-digit 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 17-digit pairs, it has reached prime factors ~4*107. I've submitted 209424 new 17-digit pairs to Pat.
Sergei Chernykh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Search of all even-15-digit Aliquot cycles Drdmitry Aliquot Sequences 25 2016-12-16 15:26
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 21:04.

Mon Aug 3 21:04:04 UTC 2020 up 17 days, 16:50, 0 users, load averages: 1.28, 1.39, 1.42

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.