Odd Perfect numbers - a factoring challenge

philmoore · 2004-09-23, 18:29

For those of you interested in factoring by ECM/P-1, I saw the following today on the nmbrthry listserve:
http://listserv.nodak.edu/scripts/wa...y&F=&S=&P=1064
Basically, the author says that he has proven that any odd perfect number must have at least 47 prime factors (including repetitions), and that improving this result depends upon finding factors of the three numbers listed in the posting. Gmp-ecm would probably be the preferred tool here.

akruppa · 2004-09-23, 19:17

I was about to post this, too. I've emailed Kevin G. Hare, asking for info on previous factoring effort so that we can choose bounds accordingly, but haven't received a reply yet.

I've done P-1 on the c301 with B1=100M, and on the c789 and c927 with B1=10M.

I'm attaching files with the numbers to factor. Unfortunately I don't have a lot of cpu time available at present, but I'll start off with 100 curves at B1=1M on the c301.

If you can run gmp-ecm, please help factor these numbers!

Alex

dleclair · 2004-09-23, 19:32

I'm running gmp-ecm on the C301 at the 30-digit level. I have about 15 (slowish) CPUs on it at moment and it will be done soon. If nothing is found I'll bump it up to the 35-digit level and then 40 digits.

If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.

-Don Leclair

dave_dm · 2004-09-23, 19:45

OK then, I'm doing 500@25e4 on the C789, this will take a few hours.

Dave

xilman · 2004-09-23, 21:27

Quote:

Originally Posted by dleclair

I'm running gmp-ecm on the C301 at the 30-digit level. I have about 15 (slowish) CPUs on it at moment and it will be done soon. If nothing is found I'll bump it up to the 35-digit level and then 40 digits.

If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.

-Don Leclair

I loaded the 2 smaller numbers into my home ECMNET soon after the NMBRTHRY moderator let loose the posting. Not having any information about the work done so far I assumed that no work had been done.

Pari-gp is amazingly slow at calculating the largest number. I gave up after about 2 hours cpu and loaded only the 2 smaller ones. Kevin Hare has since mailed me the decimal representation of the largest.

Since then a few hundred curves at B1=50K have completed, as have around 50 at B1=250K. Needless to say, no factors have yet been found.

Paul

wblipp · 2004-09-23, 21:33

Quote:

Originally Posted by dleclair

If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.

I recently ran Dario Alpern's applet to 350, which gets 25 curves at the 35 digit level but jumps there straight from the 25 digit level. I'm not running any more at the present.

These roadblocks suggest he may have found some other factors that are not in Richard Brent's data base. I wonder if he has found factors of

sigma(127¹⁰⁸)
sigma(16¹⁹²)
sigma(2801⁷⁸)

or if his approach doesn't need these.

dave_dm · 2004-09-23, 21:51

I did a quick check to ensure there are no algebraic factors (of polynomials in 11, 547, 3221 respectively). Indeed there aren't. Should this be obvious to me?

Dave

akruppa · 2004-09-23, 22:36

I've done 100@1M for the c301. I'm doing 100@1M on the c927 now.

Note that sigma(11^18), sigma(547^18) and sigma(3221^12) are prime. sigma(p^n) is simply p^0+p^1+...+p^n, i.e. if n+1 is prime, the (n+1)st cyclotomic polynomial evaluated at p, which also explanins the absence of algebraic factors.

Alex

dave_dm · 2004-09-23, 23:25

I'm talking about (for instance) the poly in 11 being irreducible, not the poly in sigma(11^18).

For example, take sigma(sigma(2^4)^2). Here sigma(2^4) = 31 is prime, also 2+1 is prime and sigma(p^2) = p^2 + p + 1 which is irreducible in Z[p].

So in this case the composition of two irreducible cyclotomic polynomials has an algebraic factor:

(x^2 - x + 1)(x^6 + 3x^5 + 5x^4 + 6x^3 + 7x^2 + 6x + 3)

This is really what I meant. Am I making sense?

Dave

akruppa · 2004-09-24, 00:06

Yes, perfect sense! Good point.

According to Pari, both phi_17(phi_19(x)) and phi_23(phi_13(x)) are irreducible.

Alex

dleclair · 2004-09-24, 00:49

For the C301, I've finished 1100 curves at B1=1M with gmp-ecm 5.0.3 so it is unlikely that there are any 35-digit or smaller factors.

A few minutes ago my machines started 2900 curves at 3M (the 40-digit level). That should be done late tomorrow.

If no factors are found I plan to stop when the 40-digit level is complete.

-Don Leclair

2004-09-23, 18:29	#1
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 19×59 Posts	Odd Perfect numbers - a factoring challenge For those of you interested in factoring by ECM/P-1, I saw the following today on the nmbrthry listserve: http://listserv.nodak.edu/scripts/wa...y&F=&S=&P=1064 Basically, the author says that he has proven that any odd perfect number must have at least 47 prime factors (including repetitions), and that improving this result depends upon finding factors of the three numbers listed in the posting. Gmp-ecm would probably be the preferred tool here.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Odd Perfect Numbers	davar55	Miscellaneous Math	16	2011-01-29 01:53
Regards RSA factoring challenge	koders333	Factoring	5	2006-03-28 13:50
Powerful Numbers programming challenge	geoff	Programming	31	2005-02-20 18:25
Perfect Numbers	MajUSAFRet	Math	3	2003-12-13 03:55
Odd Perfect Numbers	Zeta-Flux	Math	1	2003-05-28 19:41

2004-09-23, 19:32	#3
dleclair Mar 2003 2⁴×5 Posts	I'm running gmp-ecm on the C301 at the 30-digit level. I have about 15 (slowish) CPUs on it at moment and it will be done soon. If nothing is found I'll bump it up to the 35-digit level and then 40 digits. If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level. -Don Leclair

2004-09-23, 19:45	#4
dave_dm May 2004 2⁴×5 Posts	OK then, I'm doing 500@25e4 on the C789, this will take a few hours. Dave

2004-09-23, 21:51	#7
dave_dm May 2004 2⁴·5 Posts	I did a quick check to ensure there are no algebraic factors (of polynomials in 11, 547, 3221 respectively). Indeed there aren't. Should this be obvious to me? Dave

2004-09-23, 22:36	#8
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I've done 100@1M for the c301. I'm doing 100@1M on the c927 now. Note that sigma(11^18), sigma(547^18) and sigma(3221^12) are prime. sigma(p^n) is simply p^0+p^1+...+p^n, i.e. if n+1 is prime, the (n+1)st cyclotomic polynomial evaluated at p, which also explanins the absence of algebraic factors. Alex

2004-09-23, 23:25	#9
dave_dm May 2004 2⁴×5 Posts	I'm talking about (for instance) the poly in 11 being irreducible, not the poly in sigma(11^18). For example, take sigma(sigma(2^4)^2). Here sigma(2^4) = 31 is prime, also 2+1 is prime and sigma(p^2) = p^2 + p + 1 which is irreducible in Z[p]. So in this case the composition of two irreducible cyclotomic polynomials has an algebraic factor: (x^2 - x + 1)(x^6 + 3x^5 + 5x^4 + 6x^3 + 7x^2 + 6x + 3) This is really what I meant. Am I making sense? Dave

2004-09-24, 00:06	#10
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Yes, perfect sense! Good point. According to Pari, both phi_17(phi_19(x)) and phi_23(phi_13(x)) are irreducible. Alex

2004-09-24, 00:49	#11
dleclair Mar 2003 2⁴×5 Posts	For the C301, I've finished 1100 curves at B1=1M with gmp-ecm 5.0.3 so it is unlikely that there are any 35-digit or smaller factors. A few minutes ago my machines started 2900 curves at 3M (the 40-digit level). That should be done late tomorrow. If no factors are found I plan to stop when the 40-digit level is complete. -Don Leclair