mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2015-11-28, 16:31   #67
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57716 Posts
Default

My method to obtain more than 7 million new amicable pairs was pretty standard:
First generate some (i,1) type of amicable pairs, then use the easy (unpublished) te Riele rule get much more pairs.

The search was especially successful on (4,1) type, found more than 900 in this type. (previously it was known only 600 such pairs).
A gold mine was:
41 Gerbicz 2015
4042515853710748097920965379860021278894537700264375=3^2*5^4*13*43*193*1499*9821213*35934768372149*12591529154973463187
4045213074037534292614128569338790912846756018135625=3^2*5^4*13*43*193*6665761314523585756066383974737009258199999
it has given a record of 720344 new amicable pairs.
R. Gerbicz is offline   Reply With Quote
Old 2015-11-29, 17:13   #68
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
And at least for me it is not that easy to get all c2 files, at home I can't download the big ones with 5MBit/sec download speed as it seems there is a time limit for this (not in every big download I get this error message at the end of the c2 file):
"PHP Fatal error: Maximum execution time of 60 seconds exceeded in G:\PleskVhosts\sech.me\httpdocs\ap\dl.php on line 37"
Would it be possible to increase/eliminate this limit?
I haven't come up with a good solution yet, but I added two more parameters to dl.php. For example, http://sech.me/ap/dl.php?d=10&a=20&b=29 will download all 10-digit pairs starting with 20, 21, ..., or 29. Both a and b must be in the range 10 - 99. Thus you can download huge files by parts.

Last fiddled with by Sergei Chernykh on 2015-11-29 at 17:15
Sergei Chernykh is offline   Reply With Quote
Old 2015-11-30, 08:32   #69
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57716 Posts
Default

Quote:
Originally Posted by Sergei Chernykh View Post
I haven't come up with a good solution yet, but I added two more parameters to dl.php. For example, http://sech.me/ap/dl.php?d=10&a=20&b=29 will download all 10-digit pairs starting with 20, 21, ..., or 29. Both a and b must be in the range 10 - 99. Thus you can download huge files by parts.
Thanks, Sergei!
R. Gerbicz is offline   Reply With Quote
Old 2015-12-01, 07:31   #70
AndrewWalker
 
AndrewWalker's Avatar
 
Mar 2015
Australia

2×41 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
My method to obtain more than 7 million new amicable pairs was pretty standard:
First generate some (i,1) type of amicable pairs, then use the easy (unpublished) te Riele rule get much more pairs.

The search was especially successful on (4,1) type, found more than 900 in this type. (previously it was known only 600 such pairs).
A gold mine was:
41 Gerbicz 2015
4042515853710748097920965379860021278894537700264375=3^2*5^4*13*43*193*1499*9821213*35934768372149*12591529154973463187
4045213074037534292614128569338790912846756018135625=3^2*5^4*13*43*193*6665761314523585756066383974737009258199999
it has given a record of 720344 new amicable pairs.
Well done finding all the new pairs! I'm just wondering if your work finds many/any of the exotic i,1 pairs either from the initial search or the subsequent breeding. (Sergei, myself and others have been picking up some of these as a byproduct of the lower digit searching, would be nice to know if they are any use for finding more pairs!)

Also can you say from your work or others that all of the regular (i,1) pairs have been found up to a particular size? (Obviously to 17 digits).

Andrew

PS Is the "unpublished" rule in one of Garcia's papers?

Last fiddled with by AndrewWalker on 2015-12-01 at 07:33
AndrewWalker is offline   Reply With Quote
Old 2015-12-01, 07:36   #71
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Quote:
Originally Posted by AndrewWalker View Post
can you say from your work or others that all of the regular (i,1) pairs have been found up to a particular size? (Obviously to 17 digits).
The smallest (i, 1) pair above 17 digits and found in 2015 is this 21-digit pair:

41 Chernykh 2015
144296691213180636675=3^3*5^2*19*43*113*743*773*1129*3571
144846519073526051325=3^3*5^2*19*43*113*2324362124159

It looks like that all (i, 1) pairs up to 20 digits are already found. All currently known (i, 1) 20 digit pairs were found before 2007.
Sergei Chernykh is offline   Reply With Quote
Old 2015-12-01, 11:51   #72
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

139910 Posts
Default

Quote:
Originally Posted by AndrewWalker View Post
Well done finding all the new pairs! I'm just wondering if your work finds many/any of the exotic i,1 pairs either from the initial search or the subsequent breeding.
Thanks. As I learned the rule is published, see for example the survey at http://oai.cwi.nl/oai/asset/4143/04143D.pdf (page 9-10).
I have searched "only" for regular (i,1) types as these gives much more pairs than the irregulars (note that you can apply the te Riele rule also for the irregulars).

Quote:
Originally Posted by AndrewWalker View Post
Also can you say from your work or others that all of the regular (i,1) pairs have been found up to a particular size? (Obviously to 17 digits).
My search was different, note also that "small" (i,1) type pair won't give you many AP, even my larger ones are still not that very exciting:
say the 900 regular (4,1) pair has given 7M new pair (don't know the correct figure), in average that is less than 8000 new pairs per one regular (i,1) pair.
R. Gerbicz is offline   Reply With Quote
Old 2015-12-11, 19:01   #73
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,399 Posts
Default

So far tripled the known number of amicable pairs in this year!

Finally downloaded all c2 files, it took some time, the total size is 25.5 GBytes (the real count is obviously somewhat larger). Used curl.h library to download it with a c code.

http://sech.me/ap/dl.php?d=11&a=55&b=59 is also downloading the 11 digits pairs starting with 54 in the smaller term, what is a problem (not checked every a,b combinations). And this is an error not only for 11 digits.

My suggestion to make the upload (and optionally the download) faster on http://sech.me/ap/submit.html, while keeping the c2 file and upload format.
It would be even an improvement on David Moews's format, see that on http://djm.cc/aliquot-database/aliquot-database.uhtml .

Let (n,m) be an amicable pair (n<m) and g=gcd(n,m), in the upload:
in the first line there is no change ([optional #] type author year)
in the second line give the prime factorization of g.
in the third line give the prime factorization of n/g and m/g, seperated by a single space.
the fourth line is empty.

Let p,q be the largest prime factors of n and m, in the general case in the prime factorization these
has got an exponent=1, and in this case we can skip these factors in the third line, as we can recover them
quickly: we know a,b where

n=a*p
m=b*q
here gcd(a,p)=gcd(b,q)=1, as p,q are prime factors with exponent=1.
Since n,m is an amicable pair: sigma(a)*(p+1)=sigma(b)*(q+1)=a*p+b*q
from this (linear equation system) we can easily get that:

p=(b*sigma(b)+sigma(a)*(sigma(b)-b))/(a*sigma(b)+sigma(a)*(b-sigma(b)))
q=sigma(a)*(p+1)/sigma(b)-1

Note: if the denominator=0 in the formula for p, then this gives no solution, otherwise
the numerator should be also equal to zero (so before division it was c1*p=c0, where c1=c0=0)
, but then (a+b)*sigma(b)=0, contradiction.
So you should consider only the case where denominator!=0.

One example:
instead of the long form:
52 Chernykh 2015
10000038430333472389639196495581571703811508519341139357606404362100114924718480425327302956481552091613122511439512045864644400554493484575018567812942028023870853758600890282709934135211420149375925=3^3*5^2*19*31*647*2459*5498256668803134744400284381645697*2159177*15595178728169*80102078917417*142954673388881503354407393922788121*7457169855869184777027175733414646695449141582155087600336262807138347680833561875599
10000043061746313675688063566993046183019639196803558251029615447935398543993674990250570277297741997696844921859194700501549755659015120076467874934408892947993132186621683421380108987795019274624075=3^3*5^2*19*31*647*2459*5498256668803134744400284381645697*385585725761869156211745483928670847042430834744924574107532526867599*7457169855869184005855902789575548927338966166838568239579444556765289145410452559759

submit it as:
52 Chernykh 2015
3^3*5^2*19*31*647*2459*5498256668803134744400284381645697
2159177*15595178728169*80102078917417*142954673388881503354407393922788121 385585725761869156211745483928670847042430834744924574107532526867599


There are very few amicable pairs where p or q has got an exponent>1, for example:
n=46129121115;m=54412443813;
for these pairs just use the full factorization of both(!) number on the third line. So
for example write:

X44 Moews&Moews 1992
3*7^2*31
5*11*41*67^2 13*17*97*557

This also means that in every case you should check these two forms, and in general the full factorization form
does not give a further solution as for example sigma(n)=n+m won't be true.

I would be also interested in a zipped download that is using the above stripped format.
Say make it only once a week. Any idea/suggestion?


ps. as still more than 90% of all pairs is in te Riele rule, we could use this. But it would be a harder job.
And for me now the above stripped format is enough.
R. Gerbicz is offline   Reply With Quote
Old 2015-12-12, 16:47   #74
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
dl.php?d=11&a=55&b=59 is also downloading the 11 digits pairs starting with 54 in the smaller term, what is a problem (not checked every a,b combinations). And this is an error not only for 11 digits
I know. It's how it's supposed to work. Valid values are 10...49 and then 50, 52, 54, ..., 98.

Quote:
There are very few amicable pairs where p or q has got an exponent>1, for example:
n=46129121115;m=54412443813;
for these pairs just use the full factorization of both(!) number on the third line. So
for example write:

X44 Moews&Moews 1992
3*7^2*31
5*11*41*67^2 13*17*97*557
For this case some other prime can be removed (41 for example). It's still possible to restore removed prime. Interesting way to archive the database. And amicable pair type (X44) can also be removed, because it's easily computed.

P.S. I can set up weekly cron job on the server which saves the database in this form.

Last fiddled with by Sergei Chernykh on 2015-12-12 at 17:18
Sergei Chernykh is offline   Reply With Quote
Old 2015-12-12, 19:34   #75
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,399 Posts
Default

Quote:
Originally Posted by Sergei Chernykh View Post
For this case some other prime can be removed (41 for example). It's still possible to restore removed prime. Interesting way to archive the database. And amicable pair type (X44) can also be removed, because it's easily computed.
Yes, that works.
Just to correct my above post: in the general case let p and q be the largest prime factor of n/g and m/g. And with your idea: just select any p,q prime factor (with exponent=1) of n/g and m/g in special cases.

What I have not written above that if n/g or m/g is greater than 1 and it is a powerful number (https://en.wikipedia.org/wiki/Powerful_number) then trivially you can't select such a prime factor. Not checked the database, but even if there is no such known amicable pair it could exist.

And for a coprime amicable pair print 1 in the second line (g=gcd(n,m)=1), we still don't know if this exist.
R. Gerbicz is offline   Reply With Quote
Old 2015-12-15, 18:18   #76
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
And at least for me it is not that easy to get all c2 files, at home I can't download the big ones with 5MBit/sec download speed as it seems there is a time limit for this (not in every big download I get this error message at the end of the c2 file):
"PHP Fatal error: Maximum execution time of 60 seconds exceeded in G:\PleskVhosts\sech.me\httpdocs\ap\dl.php on line 37"
Would it be possible to increase/eliminate this limit?
[From Pedersen and Costello I have also the old c2 files]
I've changed the way c2_*.txt files are downloaded. PHP scripts are not involved anymore, therefore there are no time limits for downloading.

dl.php is still available though, if you use it for automatic download scripts.

P.S. If you don't care about the order of pairs in files, you can download raw text files, i.e. sech.me/ap/100/23.txt for all 100-digit pairs starting with 23.

Last fiddled with by Sergei Chernykh on 2015-12-15 at 18:21
Sergei Chernykh is offline   Reply With Quote
Old 2015-12-17, 14:34   #77
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,399 Posts
Default

Quote:
Originally Posted by Sergei Chernykh View Post
I've changed the way c2_*.txt files are downloaded. PHP scripts are not involved anymore, therefore there are no time limits for downloading.
Thanks, that is working (tried on Chrome 64 bits).
R. Gerbicz 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 09:38.

Wed Sep 30 09:38:46 UTC 2020 up 20 days, 6:49, 0 users, load averages: 1.31, 1.55, 1.50

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.