mersenneforum.org Numbers wanted for OEIS sequences
 Register FAQ Search Today's Posts Mark Forums Read

 2019-08-07, 21:33 #133 bsquared     "Ben" Feb 2007 3×1,193 Posts 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.
 2019-09-23, 16:02 #134 Belteshazzar   Feb 2011 25 Posts 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
2019-09-23, 18:26   #135
GP2

Sep 2003

1010000110012 Posts

Quote:
 Originally Posted by Belteshazzar 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.

 2019-09-23, 19:45 #136 Belteshazzar   Feb 2011 25 Posts 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.
2019-09-23, 21:18   #137
sean

Aug 2004
New Zealand

111000012 Posts

Quote:
 Originally Posted by Belteshazzar 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).

 2019-09-23, 21:45 #138 sean     Aug 2004 New Zealand 32×52 Posts I've submitted a b-file for A246556 up to an including a(612).
2019-09-23, 21:55   #139
Belteshazzar

Feb 2011

2016 Posts

Quote:
 Originally Posted by sean 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.

 2019-09-29, 21:07 #140 Belteshazzar   Feb 2011 3210 Posts 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.
2019-09-30, 19:57   #141
sean

Aug 2004
New Zealand

3418 Posts

Quote:
 Originally Posted by Belteshazzar 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.

 2019-10-23, 07:01 #142 Belteshazzar   Feb 2011 3210 Posts 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.
2019-10-23, 07:07   #143
Belteshazzar

Feb 2011

1000002 Posts

Quote:
 Originally Posted by sean 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

 Similar Threads Thread Thread Starter Forum Replies Last Post ChristianB Aliquot Sequences 16 2014-05-16 06:56 kosta Factoring 24 2013-03-21 07:17 Raman Other Mathematical Topics 20 2012-08-22 16:05 Greebley Aliquot Sequences 6 2012-04-07 10:06 science_man_88 Miscellaneous Math 11 2011-05-18 15:04

All times are UTC. The time now is 13:12.

Tue Dec 7 13:12:12 UTC 2021 up 137 days, 7:41, 0 users, load averages: 0.82, 1.16, 1.41