Factoring humongous Cunningham numbers

Yamato · 2006-04-08, 15:47

Quote:

This thread is about factoring homogeneous Cunningham numbers,
i.e. aⁿ ± bⁿ with coprime a and b, 2<=a<b<=12 .

The main tables are located at https://www.unshlump.com/hcn/ (previously at http://www.leyland.vispa.com/numth/f.../anbn/main.htm)
and the reservation server is at http://www.chiark.greenend.org.uk/uc...mack/homcun.pl

_________________________________

I found 3793240807030006427627390804715037 as a factor of 4^337 - 3^337 - maybe it is already known. Program output:

GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Using B1=1000000, B2=839549779, polynomial Dickson(3), sigma=2470101139
Step 1 took 23997ms
Step 2 took 9851ms

I know, 34 digits are not news these days - but maybe somebody is interested in it.

wblipp · 2006-04-08, 16:52

IIRC, Bob Silverman was working a list of aⁿ ± bⁿ.

For numbers close to this form with known interest in the factors, Richard Brent will take factors of a³³⁷-1, with a < 10,000 and the factors > 10⁹.

At present he lists factors for only a from 2 to 10 and a=337.

R.D. Silverman · 2006-04-08, 23:25

Quote:

Originally Posted by wblipp

IIRC, Bob Silverman was working a list of aⁿ ± bⁿ.

For numbers close to this form with known interest in the factors, Richard Brent will take factors of a³³⁷-1, with a < 10,000 and the factors > 10⁹.

At present he lists factors for only a from 2 to 10 and a=337.

I have done all 4^n - 3^n for n <= 261

I have done some recent work on extending 3^n +/- 2^n to n = 400.
There are about 2 dozen composites left.

R.D. Silverman · 2006-04-10, 14:44

Quote:

Originally Posted by R.D. Silverman

I have done all 4^n - 3^n for n <= 261

I have done some recent work on extending 3^n +/- 2^n to n = 400.
There are about 2 dozen composites left.

Would anyone like to take a whack at them?

rogue · 2006-04-10, 16:01

Quote:

Originally Posted by R.D. Silverman

Would anyone like to take a whack at them?

If you post the composites and how much ECM has been done on each, I'm certain that one or more people would throw some resources your way.

R.D. Silverman · 2006-04-10, 16:47

Quote:

Originally Posted by rogue

If you post the composites and how much ECM has been done on each, I'm certain that one or more people would throw some resources your way.

I have run about 300 curves with first limit 1M (a small effort)
Here are the remaining composites with n <= 400.

3^n + 2^n

362 (2) 10840121857.C162
367 (1) 6607.13768373.208782631.17491804898039039514781661.C130
371 (1,7,53) 204389653550334425652053.C126
372 (4,12,124) 5953.C111
379 (1) C181
382 (2) 2293.398047057.C170
383 (1) 2756069.C176
386 (2) 5037855841.2420114303415642626173.2923813115488399382449.C131
388 (4) 3881.97777.C175
394 (2) 99289.347671117.182870936735296723148317.C151
400 (16,80) 19995617469086942401.C134

3^n - 2^n

335 (1,5,67) 161471.2677857341.459904255060815869460551.C88
337 (1) 9785807.C154
343 (1,7,49) 125539.C136
347 (1) 2083.4855947384634671768060977183621.C132
349 (1) 83757907.51095243093.25596540763065937603.11848591000104763324365120718891.C98
353 (1) 4943.7460934577.3939214450103.7049420316073.C130
359 (1) 719.16208386597057.231558857865697.283082202603561296656613.C118
363 (1,3,11,33,121) 2179.1061406858984187.C87
365 (1,5,73) 944621.C132
367 (1) 2203.3671.17250374783.C158
371 (1,7,53) 743.54167.C141
373 (1) 15667.2262619.249965951.C160
379 (1) 419933.885345041389532803.C158
389 (1) 9337.C182
391 (1,17,23) 4741267.C161
395 (1,5,79) 38711.C144
397 (1) 12509122229.183139575629088302014027581573180839.C145

Note that 3,2,335- and 3,2,363- are totally trivial with SNFS;
I just haven't done them.

Several others are quite easy.

xilman · 2006-04-10, 19:51

Quote:

Originally Posted by R.D. Silverman

I have run about 300 curves with first limit 1M (a small effort)
Here are the remaining composites with n <= 400.

...]

Note that 3,2,335- and 3,2,363- are totally trivial with SNFS;
I just haven't done them.

Several others are quite easy.

A C8x is totally trivial with MPQS too.

If it wasn't that I was too lazy (or, if you prefer the politcally correct excuse, too busy with higher prriority work) I'd do them myself. Should only take a few hours each.

Paul

R.D. Silverman · 2006-04-10, 20:16

Quote:

Originally Posted by xilman

A C8x is totally trivial with MPQS too.

If it wasn't that I was too lazy (or, if you prefer the politcally correct excuse, too busy with higher prriority work) I'd do them myself. Should only take a few hours each.

Paul

Yep. I use my CPU resources for 'higher prioriy stuff' as well.

These numbers are "in the grass" priority....

John Renze · 2006-04-10, 21:11

The C87 cofactor of 3^636-2^363 factors thusly:

51367404262568392429656240517252067923 x 7705482404964763837578788370404060262063595624219

This factorization was found using Msieve v. 1.01.

Wacky · 2006-04-10, 22:38

[SOAPBOX]
John,
I would like to thank you for completing this factorization.

Sometimes those of us who are committing our resources to more "cutting edge" problems forget that we also need to be grooming new researchers to take our place. Independently solving "simple" problems is both useful for the result and instructive in developing your abilities.

Bob Silverman seduced me into participating in a collaborative factoring project decades ago. (At that time a 90MHz Pentium was very much "state of the art"). With his help, I established an automated collaboration to perform widely distributed sieving. NFSNet continues to help push the limits of the Cunningham Project.

The "cutting edge" always requires some rather formatible resources. I was unable to perform sufficient filtering on one of our current projects on a machine with 2GB of RAM.

But I hope that you have been "bitten" by the bug and will become more active in the NC community. (no, Mike, I don't mean North Carolina) Frankly, we need more new blood. At this point in life, I should ask "Should I wear the bottoms of my trousers rolled?" I'm hoping that my last "hurrah" can be a 1Kb factorization.

I hope to see some younger participants ready to step in and fill the places of those who are more suited to "gardening" rather than cutting-edge math.

And, to Bob and Paul, we old codgers can still teach the young whipersnappers a thing or two.

(Thanks Bob for "infecting" me.)
[/SOAPBOX]

John Renze · 2006-04-10, 23:26

The factors of the C88 are:

1315651155909947565347700897218133001
1338208112877762546551051364373633349610010436196551

2006-04-10, 21:11	#9
John Renze Nov 2005 2⁴·3 Posts	The C87 cofactor of 3^636-2^363 factors thusly: 51367404262568392429656240517252067923 x 7705482404964763837578788370404060262063595624219 This factorization was found using Msieve v. 1.01. Last fiddled with by John Renze on 2006-04-10 at 21:15

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New phi for homogeneous Cunningham numbers	wpolly	Factoring	30	2022-12-14 18:35
Mathematics of Cunningham Numbers (3rd ed., 2002, A.M.S.)	Xyzzy	Cunningham Tables	42	2014-04-02 18:31
Don't know how to work on Cunningham numbers.	jasong	GMP-ECM	6	2006-06-30 08:51
Doing Cunningham numbers but messed up.	jasong	Factoring	1	2006-04-03 17:18
Need help factoring Cunningham numbers	jasong	Factoring	27	2006-03-21 02:47

2006-04-08, 16:52	#2
wblipp "William" May 2003 Near Grandkid 3·7·113 Posts	IIRC, Bob Silverman was working a list of aⁿ ± bⁿ. For numbers close to this form with known interest in the factors, Richard Brent will take factors of a³³⁷-1, with a < 10,000 and the factors > 10⁹. At present he lists factors for only a from 2 to 10 and a=337.

2006-04-10, 22:38	#10
Wacky Jun 2003 The Texas Hill Country 3²×11² Posts	[SOAPBOX] John, I would like to thank you for completing this factorization. Sometimes those of us who are committing our resources to more "cutting edge" problems forget that we also need to be grooming new researchers to take our place. Independently solving "simple" problems is both useful for the result and instructive in developing your abilities. Bob Silverman seduced me into participating in a collaborative factoring project decades ago. (At that time a 90MHz Pentium was very much "state of the art"). With his help, I established an automated collaboration to perform widely distributed sieving. NFSNet continues to help push the limits of the Cunningham Project. The "cutting edge" always requires some rather formatible resources. I was unable to perform sufficient filtering on one of our current projects on a machine with 2GB of RAM. But I hope that you have been "bitten" by the bug and will become more active in the NC community. (no, Mike, I don't mean North Carolina) Frankly, we need more new blood. At this point in life, I should ask "Should I wear the bottoms of my trousers rolled?" I'm hoping that my last "hurrah" can be a 1Kb factorization. I hope to see some younger participants ready to step in and fill the places of those who are more suited to "gardening" rather than cutting-edge math. And, to Bob and Paul, we old codgers can still teach the young whipersnappers a thing or two. (Thanks Bob for "infecting" me.) [/SOAPBOX]

2006-04-10, 23:26	#11
John Renze Nov 2005 60₈ Posts	The factors of the C88 are: 1315651155909947565347700897218133001 1338208112877762546551051364373633349610010436196551