mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-08-07, 21:33   #133
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

DFB16 Posts
Default

It's possible the 10^15 figure came from trial division. YAFU (and primesieve) can sieve up to 10^13 in less than an hour; a few hundred hours would get you there, which is a thinkable thought.

Asking yafu to start ECMing the number given an input effort of t50 (use -work 50 and -v along with the factor function), it will tell you that:

Code:
fac: setting target pretesting digits to 209.23
        t15: 3777.00
        t20: 3777.00
        t25: 1510.85
        t30: 539.60
        t35: 139.90
        t40: 31.22
        t45: 5.98
        t50: 1.02
        t55: 0.16
        t60: 0.02
~540 times the effort needed to find a 30 digit prime has been performed. So the chance that a 30 digit prime was missed given that a full t50 was performed is exp(-540), which is a pretty small number.
bsquared is offline   Reply With Quote
Old 2019-09-23, 16:02   #134
Belteshazzar
 
Feb 2011

25 Posts
Default

I built a new computer and decided to do some ECM on OEIS wanted numbers as a "burn-in test." Ran a couple days' worth of fruitless curves on each of several near-factorials before successfully factoring Pell(611).

This brings me to two questions:

How up to date is the ECM effort listed? It's not shocking that my ECM efforts on near-factorials didn't come up with anything, but after a week of having my machine do that without success I wondered whether other people had already been down these roads.

Also, though the table says factors of Pell(611) are needed for A246556, it's for the 611th term, only 56 terms are listed, and the only b-file is just generated from the entry ergo also only 56 terms. So I don't see where to contribute what I found other than factordb.

Last fiddled with by Belteshazzar on 2019-09-23 at 16:03 Reason: too many newlines
Belteshazzar is offline   Reply With Quote
Old 2019-09-23, 18:26   #135
GP2
 
GP2's Avatar
 
Sep 2003

5×11×47 Posts
Default

Quote:
Originally Posted by Belteshazzar View Post
Also, though the table says factors of Pell(611) are needed for A246556, it's for the 611th term, only 56 terms are listed, and the only b-file is just generated from the entry ergo also only 56 terms. So I don't see where to contribute what I found other than factordb.
If the 57th term isn't known, then the sequence listed in OEIS will end after 56 terms.

See for instance their sequence of Mersenne prime exponents, which ends at 43112609 because the double checking has only reached approximately 49M so far.
GP2 is offline   Reply With Quote
Old 2019-09-23, 19:45   #136
Belteshazzar
 
Feb 2011

3210 Posts
Default

That's not the issue; all the previous Pell numbers have been fully factored. You can verify this by going to the b-file for the Pell numbers and pasting any of the previous ones into factordb. (I'll admit I haven't queried all of them.)


And Pell(57) is only 22 digits, it's not as though it was some kind of roadblock. So 'what's the smallest primitive factor for each Pell number' didn't encounter some kind of roadblock at 57.
Belteshazzar is offline   Reply With Quote
Old 2019-09-23, 21:18   #137
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32×52 Posts
Default

Quote:
Originally Posted by Belteshazzar View Post
Also, though the table says factors of Pell(611) are needed for A246556, it's for the 611th term, only 56 terms are listed, and the only b-file is just generated from the entry ergo also only 56 terms. So I don't see where to contribute what I found other than factordb.
The most interesting cases in the OEIS wanted numbers list are those marked "*". They correspond to sequences where only a few terms are known (e.g. not enough to fill the usual data lines in the OEIS). For most others factoring a number will allow further extension of the sequence, but this can usually be done indefinitely. There will always be a smallest unknown term.

All Pell numbers up to 611 are already factored, hence A246556 is known up to a(610). The OEIS does not always list all known terms of a sequence (and certainly not in the data lines).

The first gaps I have are Pell(611), Pell(613), Pell(619), Pell(625).
sean is offline   Reply With Quote
Old 2019-09-23, 21:45   #138
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32·52 Posts
Default

I've submitted a b-file for A246556 up to an including a(612).
sean is offline   Reply With Quote
Old 2019-09-23, 21:55   #139
Belteshazzar
 
Feb 2011

25 Posts
Default

Quote:
Originally Posted by sean View Post
The most interesting cases in the OEIS wanted numbers list are those marked "*". . . . The OEIS does not always list all known terms of a sequence (and certainly not in the data lines).
Of course I read the bit saying "*='more' keyword in OEIS" and saw that Pell(611) had no star, I just thought that if it was listed as a sequence "needing factors" then someone wanted to extend the sequence on OEIS in some way (whether in the entry, in a b-file, or whatever) rather than just filling FactorDB.


I've gone ahead and submitted the factors of Pell(611) to factordb, and I've made a draft wiki edit reflecting my efforts. I'll try one more thing and then probably give factorization a rest until the next time I have a new machine.
Belteshazzar is offline   Reply With Quote
Old 2019-09-29, 21:07   #140
Belteshazzar
 
Feb 2011

25 Posts
Default

Pell number 613 has had t50 ecm effort; no factor found. Factored #s 619, 625, and 627.

Then looked at the semiprimes sequence, which is marked 'more,' and found a bunch of small factors. Showed that 859 and 937 belong in the sequence. Ruled out 757, 829, 839, 887, 907. I believe the only candidates remaining <=1000 are 709, 787; both have had t45.

I'm done here for a while.
Belteshazzar is offline   Reply With Quote
Old 2019-09-30, 19:57   #141
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32·52 Posts
Default

Quote:
Originally Posted by Belteshazzar View Post
Pell number 613 has had t50 ecm effort; no factor found. Factored #s 619, 625, and 627.

Then looked at the semiprimes sequence, which is marked 'more,' and found a bunch of small factors. Showed that 859 and 937 belong in the sequence. Ruled out 757, 829, 839, 887, 907. I believe the only candidates remaining <=1000 are 709, 787; both have had t45.

I'm done here for a while.
Thanks! I'll look to do some of these next cases by SNFS at some point, but my resources are not what they once were.
sean is offline   Reply With Quote
Old 2019-10-23, 07:01   #142
Belteshazzar
 
Feb 2011

1000002 Posts
Default

OK, I lied. I came back to this and did more Pell factorizations. That included all the remaining up to 650 (613 & 631 still unfactored, t50) and some between that and 709. Also a bunch of prime-index ones for the semiprime sequence, finding three and ruling out all the others below 1471 (except 709, 787 as mentioned before); I reported that to oeis. Most of these were very quick.

Also noticed on factordb that (apparently over a year ago) someone did a bunch of primorial+/-1 factorizations not noted on the wiki page. For instance, the -1 semiprime sequence contains 503, 709, 859, 863 and the next candidate would be 1013.
Belteshazzar is offline   Reply With Quote
Old 2019-10-23, 07:07   #143
Belteshazzar
 
Feb 2011

25 Posts
Default

Also, I've never done SNFS before and after your reply
Quote:
Originally Posted by sean View Post
Thanks! I'll look to do some of these next cases by SNFS at some point, but my resources are not what they once were.
my curiosity got the better of me and I wondered what kind of resources these jobs would require.

So I glanced at your guide to quintic SNFS polys for Fib/Lucas numbers, used pari's lindep to find a couple polys, and tried sieving briefly w/factmsieve and yafu to try to estimate quad-core time for Pell(709) and the 203-digit cofactor of Pell(613). As a guess based on this, maybe sieving would take about a month for the latter and two years for the former?

Could I get a couple tips here?

Here's the polynomial I was looking at:

Code:
n: 41992954986653668251498160346091865848259963960853060020750860632150880435788410917184988498688690850646615751221247309950434587076089709352088108916792779996577130820982289749315443146420724344354422429
Y1: 390458526450928779826062879981346977190
Y0: -942650270102046130733437746596776286089
c6: 1
c4: 15
c3: -40
c2: 75
c1: -72
c0: 29
Here Y1=Pell(102), Y0=-Pell(103). Since 709 and 613 are both 1 mod six, the same sextic works for Pell(709) with Y1=Pell(118) and Y0=-Pell(119). I guess it's a bit of a bonus that it has a small Galois group?

A few questions:

1. One post I saw hinted that the standard advice for skew (|c0/cn|^1/n) is predicated on Y1=1 or roughly so. What makes sense when Y1 is nowhere close to 1?

2. I see SNFS difficulty computed a couple of different ways. What's the actual general definition? (Including e.g. quadratic second polynomial?)

3. Unless I tell yafu an explicit "size: nnn", here's what it does:
Code:
nfs: detected snfs job but no snfs difficulty; assuming size of number is the snfs difficulty
nfs: guessing snfs difficulty 271 is roughly equal to gnfs difficulty 30
nfs: creating ggnfs job parameters for input of size 30
That seems like a ... rather poor ... guess, to put it mildly. Then it started rapidly running through tiny q ranges and telling me it found 0 relations. If I instead explicitly tell it 'size: 271' then it says 'guessing snfs difficulty 271 is roughly equal to gnfs difficulty 181' which seems more reasonable. It does the same type of thing with Pell(613).

4. Given how it did with that, I don't feel I could trust that the parameters it automatically sets when I give it the SNFS difficulty are near-optimal. I wonder whether its choice of lasieve14 (I'm talking about Pell613 not Pell709 here) is right as well; IIRC factmsieve chooses lasieve15. Downloaded the Silverman "Optimal Parameterization of SNFS" paper, haven't had time to go through it in detail. Hints on params?

Last fiddled with by Belteshazzar on 2019-10-23 at 07:09
Belteshazzar is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sequences using nine-digit pandigital numbers as start ChristianB Aliquot Sequences 16 2014-05-16 06:56
Help wanted, Mersenne base Cunningham numbers kosta Factoring 24 2013-03-21 07:17
OEIS missing sequences Raman Other Mathematical Topics 20 2012-08-22 16:05
Any interest in all sequences/open sequences? Greebley Aliquot Sequences 6 2012-04-07 10:06
my misunderstanding of the OEIS science_man_88 Miscellaneous Math 11 2011-05-18 15:04

All times are UTC. The time now is 18:25.


Sun Dec 5 18:25:52 UTC 2021 up 135 days, 12:54, 1 user, load averages: 1.76, 1.65, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.