20220924, 10:02  #1 
Sep 2022
1_{8} Posts 
Factoring n!+1
n!+1 is often prime since it does not divide any number up to n, and on factordb all numbers up to \(140!+1\) have been fully factored. However, no factors are known for \(140!+1\): http://factordb.com/index.php?id=1000000000002850164,
Since this number is 242 digits, it looks like it would take a very long time to factor if it happened to be semiprime (is there any reason the number cannot be a semiprime?) so I wanted to ask if there are any easier algorithms known for factoring these types of numbers. 
20220924, 12:00  #2 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,153 Posts 
n! grows large much faster than n^2 which means there are much more primes greater than n that might divide n!+/1 for large integers.
The probability of n!+/1 being Prime approaches any random number of similar size being Prime the larger, n gets. AFAIK the only way to prove a number is a semiprime is to prove that it is composite and that it is not divisible by any prime less than its CubeRoot (not considering Prime squares as semiprimes). Welcome to the board. ETA: Or if it is divisible by a Prime p less than the CubeRoot of the number (n!+1), then prove that (n!+1)/p is also prime. Last fiddled with by a1call on 20220924 at 12:45 
20220924, 14:30  #3  
Apr 2020
5^{3}×7 Posts 
Quote:
I'm not aware of any website listing ECM work, but Sean Irvine (username "sean") has done a lot of ECM on these numbers. 

20220924, 17:45  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,153 Posts 
For the sake of completeness in regards to my last post, according to Wilsonโs theorem, n!+1 will always be divisible by Prime p if n=p1, so the probability of it being Prime is much less than any random number. :smile.
ETA: that is if n>2. Last fiddled with by a1call on 20220924 at 17:50 
20220924, 19:54  #5 
"Forget I exist"
Jul 2009
Dartmouth NS
8418_{10} Posts 

20220924, 21:58  #6  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}·11·227 Posts 
Quote:
And when that is done, there are thousands more. What is special about 140!+1 ? Code:
GMPECM 7.0.3 [configured with GMP 6.1.1, enableasmredc] [ECM] Input number is 140!+379 (242 digits) Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=1:3643500643 Step 1 took 267899ms Step 2 took 71418ms ... Run 7335 out of 9000: Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=1:157708634 Step 1 took 128403ms Step 2 took 38994ms ********** Factor found in step 2: 621207997473930408697081975516442147191068436669403293 Found prime factor of 54 digits: 621207997473930408697081975516442147191068436669403293 

20220925, 16:43  #7 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
37×313 Posts 

20220925, 17:02  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23404_{8} Posts 

20220925, 17:25  #9 
"Forget I exist"
Jul 2009
Dartmouth NS
20342_{8} Posts 
We have more theory to throw out there. No two consecutive numbers of form n!+1 can have shared factors.

20220930, 09:24  #10 
Aug 2004
New Zealand
2×5×23 Posts 
I've performed 30000 curves with B1=850M without success on this number.

20220930, 09:29  #11 
Aug 2004
New Zealand
2×5×23 Posts 
There are also various results in the literature (not particularly useful for finding factors) such as:
The largest prime factor of n!+1 exceeds n+(1o(1))ln n/ln ln n. Further, as n goes to infinity the ratio of the largest prime factor of n!+1 over n exceeds 2 + delta where delta is an effectively computable positive constant. [Erdos & Stewart 1976] 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factoring 2โฟ2 equivalent to factoring 2โฟ1(I think)  baih  Miscellaneous Math  9  20200921 07:11 
OpenCL GPU P1 Factoring and ECM Factoring  xx005fs  GPU Computing  3  20181027 14:49 