mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Factoring humongous Cunningham numbers (https://www.mersenneforum.org/showthread.php?t=5722)

 Yamato 2006-04-08 15:47

Factoring humongous Cunningham numbers

i.e. a[SUP]n[/SUP] [FONT=&quot]±[/FONT] b[SUP]n[/SUP] with coprime a and b, 2<=a<b<=12 .

The main tables are located at [url]https://www.unshlump.com/hcn/[/url] (previously at [url]www.leyland.vispa.com/numth/factorization/anbn/main.htm[/url])
and the reservation server is at [URL]http://www.chiark.greenend.org.uk/ucgi/~twomack/homcun.pl[/URL] [/QUOTE]_________________________________

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

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[sup]n[/sup] ± b[sup]n[/sup].

For numbers close to this form with known interest in the factors, Richard Brent will take factors of a[sup]337[/sup]-1, with a < 10,000 and the factors > 10[sup]9[/sup].

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

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

[QUOTE=wblipp]IIRC, Bob Silverman was working a list of a[sup]n[/sup] ± b[sup]n[/sup].

For numbers close to this form with known interest in the factors, Richard Brent will take factors of a[sup]337[/sup]-1, with a < 10,000 and the factors > 10[sup]9[/sup].

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

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=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.[/QUOTE]

Would anyone like to take a whack at them?

 rogue 2006-04-10 16:01

[QUOTE=R.D. Silverman]Would anyone like to take a whack at them?[/QUOTE]

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=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.[/QUOTE]

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=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.[/QUOTE]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=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[/QUOTE]

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

All times are UTC. The time now is 08:22.