## e-group suggestions with Binomials

Expand Messages
• Note to newbies: If this leads to cpu demanding projects, simple requests will be made at a later time. Don t worry if this post sounds complicated. The
Message 1 of 7 , May 24, 2005
Note to newbies: If this leads to cpu demanding projects, simple requests will
be made at a later time. Don't worry if this post sounds complicated.

The binomial C(x,y) = (x!/(x-y)!)/y! = [x*(x-1)*...*(x-y+1)]/y!
The function C(x,y) is in both PrimeForm and The Prime Pages.
PrimeForm cannot evaluate it for x>2^31 but it would be an easy fix.
I don't know whether The Prime Pages can handle x>2^31 now.

In this post +/-1 means +1 or -1 (not and).
Titanic means a number (not necessarily prime) with at least 1000 digits.

"Binomial" is a Prime Pages tolerated comment for C(x,y)+/-1. It does not have a
top-20.
All current binomials have x<=354172. Such small x give trivial complete
factorization of C(x,y). The largest binomial is:
758 C(354172,177086)+1 106614 p16 2005 Binomial
The 67 largest binomials in the full database are by p16 = Daniel Heuer,
PrimeForm.

I think challenging binomial forms are more interesting than the largest
binomial, especially when the record is not registered anywhere.
I suggest PrimeForm e-group projects to find (and prove!) top-5000 primes using
binomials with non-trivial factorization. I have 3 challenges in mind:

A) Maximize y in k*C(x,y)+/-1 with titanic x (and small k, e.g. k<10^12).
B) Maximize y in C(x,y)+/-1 with titanic x.
C) Maximize subtitanic x in C(x,y)+/-1.

Proving any top-5000 C(x,y)+/-1 with x from 500 to 1500 digits seems infeasible
to me, so the precise size of the titanic limit is not important.

C(x,y)+/-2 appears useless so the factorization must come from C(x,y), i.e. y
consecutive numbers ending with x. I think David's implementaion of KP
(Konyagin-Pomerance method) should be able to prove any k*C(x,y)+/-1 if C(x,y)
is at least 30% factored (PrimeForm needs 33.33%). Reaching 30% with the
restrictions is the challenge.

----------------------------------------------------------

A) Maximize y in k*C(x,y)+/-1 with titanic x.

k>1 does not give the binomial comment but the challenge looks interesting.
To get a head start on y, I looked at known cases of several factorizations in
almost consecutive numbers. The best already known at the needed size for
top-5000 was 4 factorizations, coming from 3 primes and either a number with
constructed factors or 3 numbers with 1/3 constructed factors in BLS-provable
CPAP-3/triplets. I examined all available triplets, CC3's (length 3 Cunningham
Chains) of both kinds, CPAP-3 with difference 6, and a "nothing" from Ken Davis'
CPAP-3/triplet search.
A CC3 p, 2p-1, 4p-3 with p-1 factored by construction gives factorization of 4p,
4p-2, 4p-3, 4p-4. Multiplying these by 2 to 6 still gives 4 factorizations
within 25 numbers.

GMP-ECM was run on numbers near the known factorizations in hope of finding prp
cofactors. Their size can be proved by Primo. The best result follows.

In 2001 Michael Angel, Dirk Augustin, Paul Jobling's NewPGen, Paul Jobling, Yves
Gallot's Proth.exe found this CC3 of the 2nd kind:
p = 1531785651*2^10107+1, 2p-1, 4p-3
With N = 8*(p-1) = 1531785651*2^10110, this gives all factors of:
N, N+2 = 2*(4p-3), N+4 = 2^2*(2p-1), N+8 = 2^3*p

GMP-ECM found 3 further complete factorizations with the prp's:
(N-4)/(2^2*5*7*31237*286235451569*11609891459483469679)
(N+5)/(47*2087*240631)
(N+15)/(3*6343*1655652931*1809537707*376766311088897*7992061535285413)

Assuming Primo proves these as part of a proposed e-group project, in total 7 of
20 consecutive 3053-digit numbers are factored:
N -4, +0, +2, +4, +5, +8, +15
7/23 = 0.3043 > 30%, so a prime k*C(N+x,23)-1 should be KP provable.
PrimeForm would only be able to prove k*C(N+x,21)-1.

I suggest searching prime q = k*C(N+18,23)-1 which has around 70230 digits.
I can sieve 4-way to at least 5*10^11 with a bonus twin and two Sophie Germain
chances in q+2, 2q+1, (q-1)/2.

An 8th factorization would lead to 8/27 = 0.2963. With already found factors in
the other 19 numbers, this crawls above 30% factorization of C(N+x,27), so
k*C(N+x,27)-1 would become provable. x can vary from 15 to 22 to include the 7
known factorizations and give 27 potential numbers for the 8th.
If somebody want to try their luck, the 27 composite cofactors I reached are:

(N-11)/(7*11*31*740709869*36019552313*5754952087369043827)
(N-10)/(145081378753)
(N-9)/(3*5)
(N-8)/(2^2*5084641*3702275685377)
(N-7)/(13^2*9173655362071)
(N-6)/(3^2*23*92467*2062993*44766613387)
(N-5)/(271*25939)
(N-3)/(3*37*4179551693)
(N-2)/(3229*608339158211*2195558721443)
(N-1)/(443*512397569*747778922174583899749)
(N+1)/(5^4*179*18691*67023071*828414468062375867)
(N+3)/(3^3*7*17*769309*37241663*633648618817439699987)
(N+6)/(3*5*13*9769*4161831581*2253021875118653)
(N+7)/(19*31256441)
(N+9)/(3*113*1237*11527)
(N+10)/(7*83*101*48973*100399010893*717550605597053)
(N+11)/(5*11*61)
(N+12)/(2*3^2*9011*262519*225217825960981333)
(N+13)/(109*99989*3379164582960823)
(N+14)/(79)
(N+16)/(2^3*5*29*71)
(N+17)/(7*23*769*11357869*326449573001*8324698336049803606091)
(N+18)/(3*144645443*1242324019*30346084597567)
(N+19)/(13*280760917970256472816453)
(N+20)/(2*17*31*150357501241)
(N+21)/(3^2*5*4909*176629*4033860989*291330527*3677930815683701)
(N+22)/(11*59*291762855892929833)

I have run the recommended ECM 6.0 curves for 20-digit factors, plus half of the
recommended 206 curves for 25-digit factors.

It may not be worth doing more factorization. Maybe the chance of C(x,27) is
better by starting from scratch on a different form just large enough for the
top-5000, but C(x,24) is fine for me.

----------------------------------------------------------

Two possibly interesting primes were found in other search cases.

David's 4259-digit triplet record is M +5, +7, +11, where
M = (62258488321368*3331#*(1037*3331#+1)+210)*(1037*3331#-1)/35

He proved M+5 and M+7 with pfgw -tc -f -e10000000 which finds the constructed
33.3% factors 1037*3331#/35 of M+6:
http://groups.yahoo.com/group/primeform/message/3437
http://groups.yahoo.com/group/primeform/message/3443

I found that pfgw -f -d -qM+6 easily gives a prp cofactor with 2841 digits:
(M+6)/(1037*3331#/35)/(2*3*163) is 3-PRP!
All factors were found by David's pfgw -tc but the cofactor was not prp'ed.
Running Primo on this would enable new -tc proofs of M+5 and M+7 with 100% of
M+6:

Calling N+1 BLS with factored part 100.00% and helper 0.12% (300.12% proof)
(62258488321368*3331#*(1037*3331#+1)+210)*(1037*3331#-1)/35+5 is prime!

Calling N-1 BLS with factored part 100.00% and helper 0.15% (300.15% proof)
(62258488321368*3331#*(1037*3331#+1)+210)*(1037*3331#-1)/35+7 is prime!

As Jim would correctly say, it doesn't prove them any more, but I was amused.

p = 1749900015*2^6818-1, 2p+1, 4p+3 is a known CC3, so 4p, 4p+2, 4p+3, 4p+4 are
all factored.
Now, so is 4p+1 with prime (1749900015*2^6820-3)/(3*173*2707*7207) proved by
Primo.
This gives 5 consecutive completely factored 2063-numbers, i.e. complete
factorization of C(1749900015*2^6820,5).

Jack Brennen asked for "Consecutive numbers all factored" in

He mentioned BiTwins as record for 5 numbers. The current BiTwin record at
http://ourworld.compuserve.com/homepages/hlifchitz/Henri/fr-us/BiTwinRec.htm
has 1529 digits.
I couldn't extend any of the titanic BiTwins to a 6th factored number with ECM,
so Jack's challenge for 6 titanic all factored numbers is still unanswered.

----------------------------------------------------------

B) Maximize y in C(x,y)+/-1 with titanic x.

If N-1 and N are both completely factored, one by construction and one by being
prime, then C(x,6) is 33.33% factored for 15 values of x:
x = N + 0,1,2,3,4,5; 2N + 0,1,2,3,4; 3N + 0,1,2; 4N + 0,1; 5N

This gives 30 provable C(x,6)+/-1 chances.
Using known primes from the full database should give enough chances to expect a
couple of top-5000 primes up to 100000 digits.
Otherwise, searching N = k*p#+1 would not be a big part of the whole project,
considering each N gives 30 chances without factors<=p.

y>6 looks harder. A possible construction for C(x,7):
Construct 10% factorization of N-1, 90% of N, and search N+1 prime when N's 10%
cofactor is prp.
A triple hit on N's cofactor, N+1, C(~N,7)+/-1 gives (0.1+1+1)/7 = 0.3, so KP
provable.
Each double hit gives many binomial chances, (5+3+1)*2 = 18 by my count:
(N-1,N,N+1) extends to 7 numbers in 5 ways, 2*(N-1,N,N+1) in 3 ways, and
3*(N-1,N,N+1) in 1 way, all 9 with +1 or -1 in the prime.

C(x,8) is considerably harder with a similar method placing 40% factors in N-1
and 60% in N.
(0.4+1+1)/8 = 0.3, but a triple hit would maybe take more time than it is worth.

Twins N+/-1 with N factored would give 30% of C(x,10), but I don't want to
search the expected number of twins. We could first look for a fluke with
database twins.
x needs around 6060 digits. That's in Primo range for a prp cofactor, so it
doesn't have to be twins.
Assume we sieve all relevant numbers to e.g. 10^12 for N=k*14057#, save found
factors, and start by prp'ing unfactored N-1. My count says each N-1 prime gives
720 combined chances for provable C(x,10)+/-1, each needing a double hit on a
~6050-digit cofactor with no factors<10^12, and a ~60530-digit Binomial with no
factor<=14057. That means it may be practicable to find the expected number of
N-1 primes.
Maybe not all 720 chances should be tried. If e.g. N+8 has prp cofactor then it
only gives two chances: C(N+8,10)+/-1. It may not be worth the time to prp the
cofactor here.
After the hit, we must wait for ECPP around 6050 digits. If the top-5000 looks
in danger at the time, we could consider asking François Morain for help with
his distributed fastECPP.

I'm not sure which y to recommend and others may have better ideas to reach the
needed factorization.

----------------------------------------------------------

C) Maximize subtitanic x in C(x,y)+/-1.

x should be large enough to make factorization challenging. Maybe a feasible
size to reach KP is x around 200 digits but factorization is not my field.
Getting x>RSA-200 could be a nice touch and looks possible. We could go for x =
10^200+k.
To get a head start on the factorizations, we could sieve a range of e.g. 10^8 k
to at least 10^12 and prp all cofactors. Then we only prp C(x,y)+/-1 in the
cases with most factorization. I haven't estimated whether it's worth the
trouble.
60523 digits should give some top-5000 life and at least ensure it qualifies
when 30% factorization is reached and KP completes.
If all 3 Binomial projects are done at some time then maybe C(10^200+k,303)+/-1
is an appropriate size here.

Projects B) and C), like all other Binomials, do not appear sievable. Customized
trial factoring might be a little faster than pfgw -f but may not be worth the
programming time if a development pfgw with the fast tree-factorize does -f.
This can be combined with prp'ing by a more stable pfgw.

----------------------------------------------------------

Phew, that was a mouthful. Glad you are still here :-)

--
Jens Kruse Andersen
• Jens: I confirm that KP is feasible above 100k digits. It s just a matter of showing that a cubic has no integral roots (after doing all the BLS tests). As
Message 2 of 7 , May 24, 2005
Jens: I confirm that KP is feasible above 100k digits.
It's just a matter of showing that a cubic has
no integral roots (after doing all the BLS tests).
As Phil remarked, that is best done with a small prime
witness, q, such that the cubic is irreducible mod q.
David
PS: I was indeed amused by you clam to "overprove" my
M+5 and M+7. I am suprised that you wasted so much time
using Primo to prove the 2841-digit cofactor:
(10006185844*((1037*3331#)^2-1)+35)/163 is 137-PRP!
That seems an expensive way to "overprove" a number
that is only 50% larger than its _unnecessary_ ECPP helper :-)
• ... for(y=1,6,print(factor(y!*(binomial(x,y)-1))[,1]~)) [x - 1] [x - 2, x + 1] [x - 3, x^2 + 2] [x - 4, x + 1, x^2 - 3*x + 6] [x - 5, x^4 - 5*x^3 + 10*x^2 +
Message 3 of 7 , May 24, 2005
Jens:

> This gives 30 provable C(x,6)+/-1 chances

for(y=1,6,print(factor(y!*(binomial(x,y)-1))[,1]~))

[x - 1]
[x - 2, x + 1]
[x - 3, x^2 + 2]
[x - 4, x + 1, x^2 - 3*x + 6]
[x - 5, x^4 - 5*x^3 + 10*x^2 + 24]
[x - 6, x + 1, x^4 - 10*x^3 + 41*x^2 - 80*x + 120]

for(y=1,6,print(factor(y!*(binomial(x,y)+1))[,1]~))

[x + 1]
[x^2 - x + 2]
[x + 1, x^2 - 4*x + 6]
[x^4 - 6*x^3 + 11*x^2 - 6*x + 24]
[x + 1, x^4 - 11*x^3 + 46*x^2 - 96*x + 120]
[x^6 - 15*x^5 + 85*x^4 - 225*x^3 + 274*x^2 - 120*x + 720]

So with y = 6 you lose the minus-sign.

Moreover there is no hope at all for

> A triple hit on N's cofactor, N+1, C(~N,7)+/-1

since C(x,7)+1 and C(x,7)-1 are _both_ composite for all x > 427.

Proof: Run pfgw up to x = 7!+7 = 5047 and then we are done, since
C(x,7)-1 is divisible by (x-7)/gcd(x-7,7!)
C(x,7)+1 is divisible by (x+1)/gcd(x+1,7!)

In the case of

> C(10^200+k,303)+/-1

we have 10^200 =~ 121! << 303!,
so there may be such a prime with k > 0.

However, the search method is very hairy,
since it should be restricted to values of k
such that one of
10^200+k-303 or 10^200+k+1
divides 303!

Note that Daniel's almost-central binomial primes
get round this problem. But in cases that you
are considering, with x >> y, I strongly recommend
that you restrict attention to

N=C(x,y)+1 with even y

where y!*N does not have an algebraic divisor.

David
• ... Oops! I guess I should have worked out the kinks before posting suggestion B) and C). Everybody else was posting e-group suggestions and I wanted to join
Message 4 of 7 , May 24, 2005

> So with y = 6 you lose the minus-sign.
...
> C(x,7)+1 and C(x,7)-1 are _both_ composite for all x > 427.
...
> > C(10^200+k,303)+/-1
> it should be restricted to values of k such that one of
> 10^200+k-303 or 10^200+k+1 divides 303!
...
> restrict attention to
>
> N=C(x,y)+1 with even y
>
> where y!*N does not have an algebraic divisor.

Oops!
I guess I should have worked out the kinks before posting suggestion B) and C).
Everybody else was posting e-group suggestions and I wanted to join in.
A) is still good and variations of B) and C) should be.
Thanks David.

--
Jens Kruse Andersen
• ... Jens, I tried an alternate approach, but I guess it s a dead end. I wrote a sieve similar to what is used for the quadratic sieve and number field sieve
Message 5 of 7 , May 25, 2005
On May 24, 2005, at 8:31 PM, Jens Kruse Andersen wrote:
> Jack Brennen asked for "Consecutive numbers all factored" in
>
> He mentioned BiTwins as record for 5 numbers. The current BiTwin
> record at
> http://ourworld.compuserve.com/homepages/hlifchitz/Henri/fr-us/
> BiTwinRec.htm
> has 1529 digits.
> I couldn't extend any of the titanic BiTwins to a 6th factored
> number with ECM,
> so Jack's challenge for 6 titanic all factored numbers is still

Jens,

I tried an alternate approach, but I guess it's a dead end. I wrote a
sieve similar to what is used for the quadratic sieve and number
field sieve (where instead of flagging a given sieve entry, the
logarithm of the factor is added), then searched for max(sum(6
consecutive entries)) over the sieve array. There's a problem with
this, in that primes contribute 0 to the sum, but actually represent
a fully factored value -- unfortunately, there's just too many primes
and too many false positives in the sieve array to PRP them all. If
anyone has a better strategy to process the output of the sieve
array, I'd be grateful.

Anyway, this seems to be a dead end in that the best result I have
achieved was to remove less than 180 digits from all 6 values. Of
course, that contribution is for primes <~ 4*10^8. Anyway, finding a
single prime, which is of course trivial at this range, means 1000
digits removed from one of the factors. Applying more advanced
factoring algorithms would remove extra factors, but I'm not sure the
180/6 = 30 digit head-start is such a big deal.

What I believe might be more productive is to search for six
polynomials g_i(x) = f(x) + i, i = 1..6, such that some of them have
algebraic factorizations. I don't know how likely this is to happen,
or even whether it's possible, but it might be a good approach. Of
course, we could tolerate one or two of them being irreducible, then
search for values of x such that these two are prime (assuming their
distance is even, of course). An example is f(x) = x^2 - 6: there are
algebraic factorizations for x^2, x^2 - 1 and x^2 - 4, plus one could
search for twins of the form x^2 - 3, x^2 - 5. This polynomial isn't
particularly advantageous because 1000/2 = 500 digit integers are
still out of reach of QS/NFS, but one could search for higher-degree
polynomials. I'm not coding this because I don't have the slightest
idea of how to optimize the search.

Décio

[Non-text portions of this message have been removed]
• ... I found some polynomials that, I believe, render the search quite likely to succeed. These would be x^210 - 4, x^210 - 1, x^210 and x^210 + 1. The first is
Message 6 of 7 , May 25, 2005
On May 25, 2005, at 5:25 PM, Décio Luiz Gazzoni Filho wrote:
> An example is f(x) = x^2 - 6: there are
> algebraic factorizations for x^2, x^2 - 1 and x^2 - 4, plus one could
> search for twins of the form x^2 - 3, x^2 - 5. This polynomial isn't
> particularly advantageous because 1000/2 = 500 digit integers are
> still out of reach of QS/NFS, but one could search for higher-degree
> polynomials. I'm not coding this because I don't have the slightest
> idea of how to optimize the search.

I found some polynomials that, I believe, render the search quite
likely to succeed. These would be x^210 - 4, x^210 - 1, x^210 and
x^210 + 1. The first is factored by difference of squares, the third
is trivially factorizable, and the second and fourth have lots of
factors thanks to their cyclotomic heritage. In particular, the
largest factor of x^210 - 1 is O(x^48), and the largest factor of
x^210 + 1 is O(x^96). I wrote a program that sieves x^210 - 2 or
x^210 - 3 (according to whether x is odd or even, respectively)
looking for primes, and they are plentiful: starting from x = 57797
(the smallest x such that x^210 > 10^1000), I found about 100 primes.
It shouldn't be hard to find an x such that x^210 - 2 is prime and
x^210 - 3 is fully factorable (even twice a prime, if we really want
to put an icing in the cake) or vice-versa. x^210 - 1 and x^210 + 1
should succumb to ECM and/or MPQS/NFS, even if we have to look at a
handful of values of x to achieve that. The only worrisome part is
x^210 - 4 = (x^105 + 2)(x^105 - 2), but that again, looking at a few
dozens or hundreds of values should do the trick.

So, I suggest the following strategy:
1. look for x^210 - 2 or x^210 - 3 prime, according to the parity of x
2. try to fully factor the other of x^210 - 2 or x^210 - 3, but don'
t put too much effort into it, because values should be fairly easy
to come by.
3. try to fully factor x^210 - 4 = (x^105 + 2)(x^105 - 2), putting
some more effort into it, as candidates that survived the previous
two stages aren' t plenty.
4. put a lot of effort into factoring x^210 + 1 (the one whose
largest algebraic factor is O(x^96))
5. the same for x^210 - 1, and again taking into account algebraic
factorizations.
6. done -- x^210 is trivially factorable.

Is this the best strategy? And is anyone willing to put some CPU time
into factoring the candidates in steps 3-6? I'm performing the first
step locally, and I think I can handle the second step as well.

Décio

[Non-text portions of this message have been removed]
• Congratulations to Luigi Morelli on 61876115*420*RSA-200^512-1. ... I have not looked seriously at the possible algorithms and will probably not search it. I
Message 7 of 7 , May 26, 2005
Congratulations to Luigi Morelli on 61876115*420*RSA-200^512-1.

> > Jack's challenge for 6 titanic all factored numbers is still

I have not looked seriously at the possible algorithms and will probably not
search it.
I only did limited ECM on both sides of the already known BiTwins in hope of a
prp cofactor which would have given 6 numbers with very little cpu time.

Décio wrote:

> Applying more advanced factoring algorithms would remove extra
> factors, but I'm not sure the 180/6 = 30 digit head-start is
> such a big deal.

I doubt that only prp'ing the smallest cofactors after sieving is significant.
And I doubt any advanced factoring before the initial prp test is worth doing.

There is a much smaller chance of factoring two random 500-digit numbers
simultaneously than one random 1000-digit number, so algebraic factors are a
algebraic factors are not my strong side as recently revealed. It sounds like
unpleasantly few candidates near 1000 digits to work with.

Any search should start with known prime factors corresponding to at least one
whole number.
Without analyzing algebraic factors, my first idea for a strategy was:
Sieve k*2^3300+n (fast sieve form) for a large k range and
n = -5,-4,-3,-2,-1,+1,+2,+3,+4. Save factors.
prp test k*2^3300-1 (fast prp form) when it has no known factor. Some pfgw
versions can also make a fast prp test on a cofactor of this. It may not be
practical to combine a fast prp form with algebraic factors.
If a prp was found, there are 5 chances to expand to 6 numbers:
Starting at n = -5...-1. Each chance requires 4 simultaneous factorizations. prp
the 8 cofactors for n = -5..-2,1..4.
I haven't estimated what to best do next but it may be along these lines with x
< y < z:
If 3 of 6 consecutive numbers are left to be factored then do x amount of
GMP-ECM on all 3. If 2 are left then do y amount on both. If only 1 is left then
do z on it.

This has shorter expectation than 5 simultaneous titanic primes like Jim's
CPAP-5 and Norman's 5-tuplet, but it's still harder than I want on my cpu. I
don't know how it compares to x^210. My mentioning of Jack's challenge in
passing was not a PrimeForm e-group suggestion.

A huge collection of titanic prp's next to a number with known factorization
might help. The Prime Pages database has too few but some people may have found
millions, e.g. in AP searches.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.