mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Aliquot Sequences (https://www.mersenneforum.org/forumdisplay.php?f=90)
-   -   Aliquot cycles search, the state of the art. (https://www.mersenneforum.org/showthread.php?t=20271)

Drdmitry 2015-05-23 14:29

Aliquot cycles search, the state of the art.
 
Here I collect all the information about the exhaustive search of small Aliquot cycles I know of.

[SIZE=5]Amicable pairs.[/SIZE]
All pairs below 1e17 are known. Sergei Chernykh is currently running an exhaustive search of all 17-digit pairs. The range after 1e17 is relatively untouched. The most extensive list of all pairs can be found here: [URL="http://sech.me/ap/"]http://sech.me/ap/[/URL]

[SIZE=5]Sociable numbers.[/SIZE]
We consider cycles of odd and even numbers separately. It is more efficient to look for odd cycles by their smallest elements because such Aliquot sequences tend to decrease. Even cycles are usually searched by the number preceding the largest number of the cycle.

[SIZE=4]Odd cycles:[/SIZE]
All cycles below 1e15 are known. The search of all cycles between 1e15 and 1e16 is carried out by this forum [URL="http://mersenneforum.org/showthread.php?t=20316"]here[/URL]. Only cycles of a form given by Borho are known for higher numbers.

[SIZE=4]Even cycles:[/SIZE]
All cycles below 5e12 are known for sure. It seems to me that Andre Needham completed the search for the range up to 1e13, but I am not 100% sure.
Ed Hall started the search of all cycles of length at most four. Later he extended the length to ten. Currently he reached 5e13 (probably a bit more at the moment) for the cycles of length four. Only cycles of a form given by Borho are known for higher numbers. Potentially there may be a couple of longer cycles between 5e12 and 5e13.

Theoretically there may be cycles containing both even and odd numbers. In this case they must contain a number of a form [TEX]2^d\cdot n^2[/TEX]. A couple of years ago I searched for cycles containing a number of this form. Nothing was found up to 1e14.

If there is an interest in doing a collective project to extend one of the ranges above then I can try to adopt my programs for it over summer vacations.

firejuggler 2015-05-23 16:47

you mightwantto check [url]http://mersenneforum.org/showthread.php?t=19372[/url]
edit : Ignore theling, Ididn't see you were already a part of this thread.
edit 2,: maybe this one ? [url]http://mersenneforum.org/showthread.php?t=13291[/url]

science_man_88 2015-05-23 17:38

[QUOTE=firejuggler;402879]you mightwantto check [url]http://mersenneforum.org/showthread.php?t=19372[/url]
edit : Ignore theling, Ididn't see you were already a part of this thread.
edit 2,: maybe this one ? [url]http://mersenneforum.org/showthread.php?t=13291[/url][/QUOTE]

they've been a part of both at some point: [url]http://mersenneforum.org/search.php?searchid=1630877[/url]

Dubslow 2015-05-23 17:58

[QUOTE=firejuggler;402879]you mightwantto check [url]http://mersenneforum.org/showthread.php?t=19372[/url]
edit : Ignore theling, Ididn't see you were already a part of this thread.
edit 2,: maybe this one ? [url]http://mersenneforum.org/showthread.php?t=13291[/url][/QUOTE]

This is a consolidated sequel to those threads.

AndrewWalker 2015-06-10 12:00

[QUOTE=Drdmitry;402869]Here I collect all the information about the exhaustive search of small Aliquot cycles I know of.

[SIZE=5]Amicable pairs.[/SIZE]
All pairs below 1e14 are known. Several people are searching pairs in a range between 1e14 and 1e15:[LIST][*]Andrew Walker is doing a run with the 15d pairs where the first number has a highest factor from 10m to 40m. He is going to finish in a couple of months.[/LIST] [/QUOTE]

This is done and sent to Patrick, along with a quick run on 16 digits up to 10000 for factors of the first number. He is still going
through them, but for the 15 digits so far only <5% are new. I'll be doing more now with 16 digits and some of the breeding methods which look promising! :smile:
Andrew

Drdmitry 2015-06-11 10:23

[QUOTE=AndrewWalker;403817]This is done and sent to Patrick, along with a quick run on 16 digits up to 10000 for factors of the first number. He is still going
through them, but for the 15 digits so far only <5% are new. I'll be doing more now with 16 digits and some of the breeding methods which look promising! :smile:
Andrew[/QUOTE]

That is great! I am afraid that I do not have the rights to change the initial text so it will remain unchanged unfortunately.

As far as I understand, your methods are specific for finding amicable pairs and can not be used for longer cycles? Currently I am interesting in cycles of length bigger than two. My programs are not fast enough to search over all even 15 digits numbers or all odd 16 digits numbers on one computer in a reasonable time. However it can be done with help of a hundred cores.

henryzz 2015-06-14 14:47

[QUOTE=Drdmitry;403869]That is great! I am afraid that I do not have the rights to change the initial text so it will remain unchanged unfortunately.

As far as I understand, your methods are specific for finding amicable pairs and can not be used for longer cycles? Currently I am interesting in cycles of length bigger than two. My programs are not fast enough to search over all even 15 digits numbers or all odd 16 digits numbers on one computer in a reasonable time. However it can be done with help of a hundred cores.[/QUOTE]
PM me/Post changes and I will add them.

AndrewWalker 2015-06-15 12:33

[QUOTE=Drdmitry;403869]That is great! I am afraid that I do not have the rights to change the initial text so it will remain unchanged unfortunately.

As far as I understand, your methods are specific for finding amicable pairs and can not be used for longer cycles? Currently I am interesting in cycles of length bigger than two. My programs are not fast enough to search over all even 15 digits numbers or all odd 16 digits numbers on one computer in a reasonable time. However it can be done with help of a hundred cores.[/QUOTE]

That's correct, it has bits in it which cut off a lot of possible inputs when it determines they can't be an amicable pair, so it
would miss a lot of larger cycles. Wouldn't we all like to have a hundred cores to play with!

Andrew

Drdmitry 2015-06-15 16:18

[QUOTE=AndrewWalker;404094]That's correct, it has bits in it which cut off a lot of possible inputs when it determines they can't be an amicable pair, so it
would miss a lot of larger cycles. Wouldn't we all like to have a hundred cores to play with!

Andrew[/QUOTE]

At the moment I am adjusting the program to make it comfortable for distributed computing.
Unfortunately the code is 64 bit Windows specific. However the only specific part is a fast 64 bit multiplication modulo a 64 bit number. Hopefully it is not too difficult to rewrite it on any other 64 bit system.

AndrewWalker 2015-06-30 08:22

All of my Walker&Einstein results from above have been processed by Pat and are in his lists. There were over 40 thousand submitted,
the number of new pairs are
15 digits 656 pairs
16 digits 18018 pairs

I'm mainly interested in finding new type n1 or Xn1 pairs, the two new ones were
[FONT=&quot]
[/FONT]
[FONT=&quot]X31 Walker&Einstein 2015[/FONT]
[FONT=&quot]1691429789009025=3^5*5^2*13*71*401*709*1061[/FONT]
[FONT=&quot]1756294497513855=3^5*5*13*71*1566099539[/FONT]


[FONT=&quot]X41 Walker&Einstein 2015[/FONT]
[FONT=&quot]5804063919860661=3^2*7^2*13*19*29*47*89*101*4349[/FONT]
[FONT=&quot]6126766409739339=3^2*7*13^3*19*29*80335799[/FONT]


I'm also hoping to find new pairs where the smallest prime factor is bigger than 3.

Can you please add above I'm looking at even 16 digits with the largest factor from 10k to 100k in the first number, this won't find everything and will take several months!

Andrew

Drdmitry 2015-06-30 09:36

[QUOTE=AndrewWalker;405024]All of my Walker&Einstein results from above have been processed by Pat and are in his lists. There were over 40 thousand submitted,
the number of new pairs are
15 digits 656 pairs
16 digits 18018 pairs

I'm mainly interested in finding new type n1 or Xn1 pairs, the two new ones were
[FONT=&quot]
[/FONT]
[FONT=&quot]X31 Walker&Einstein 2015[/FONT]
[FONT=&quot]1691429789009025=3^5*5^2*13*71*401*709*1061[/FONT]
[FONT=&quot]1756294497513855=3^5*5*13*71*1566099539[/FONT]


[FONT=&quot]X41 Walker&Einstein 2015[/FONT]
[FONT=&quot]5804063919860661=3^2*7^2*13*19*29*47*89*101*4349[/FONT]
[FONT=&quot]6126766409739339=3^2*7*13^3*19*29*80335799[/FONT]


I'm also hoping to find new pairs where the smallest prime factor is bigger than 3.

Can you please add above I'm looking at even 16 digits with the largest factor from 10k to 100k in the first number, this won't find everything and will take several months!

Andrew[/QUOTE]

I'm afraid I do not have rights to edit posts here. You can send a private message to henryzz and ask him to make make the changes to the post. I can also do that but the first variant seems to me more efficient.

Some time ago I did the search of all 16d Aliquot cycles with the smallest factor bigger than 3. There is only one such cycle already found by you. I did not check bigger numbers though.


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.