- 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

http://groups.yahoo.com/group/primenumbers/message/9879

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 - 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

> > unanswered.

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

I doubt that only prp'ing the smallest cofactors after sieving is significant.

> factors, but I'm not sure the 180/6 = 30 digit head-start is

> such a big deal.

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

disadvantage in some cases. I haven't analyzed your x^210 suggestion and

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