mersenneforum.org Factoring n!+1
 Register FAQ Search Today's Posts Mark Forums Read

 2022-09-24, 10:02 #1 andreien   Sep 2022 18 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.
 2022-09-24, 12:00 #2 a1call     "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 Cube-Root (not considering Prime squares as semiprimes). Welcome to the board. ETA: Or if it is divisible by a Prime p less than the Cube-Root of the number (n!+1), then prove that (n!+1)/p is also prime. Last fiddled with by a1call on 2022-09-24 at 12:45
2022-09-24, 14:30   #3
charybdis

Apr 2020

53×7 Posts

Quote:
 Originally Posted by andreien 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.
It could certainly be a semiprime, and it's not suitable for SNFS, so if ECM fails to find a factor then GNFS would be the only option. It is technically within GNFS range as the record is 250 digits, but it would be an enormous effort taking a couple of thousand CPU-years and requiring some fancy hardware for the matrix step.

I'm not aware of any website listing ECM work, but Sean Irvine (username "sean") has done a lot of ECM on these numbers.

 2022-09-24, 17:45 #4 a1call     "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=p-1, 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 2022-09-24 at 17:50
2022-09-24, 19:54   #5
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts

Quote:
 Originally Posted by a1call according to Wilson’s theorem, n!+1 will always be divisible by Prime p if n=p-1, so the probability of it being Prime is much less than any random number. :smile. ETA: that is if n>2.
We have $n!\equiv 1\pmod p$ for $n=p-2$
As well.

2022-09-24, 21:58   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·11·227 Posts

Quote:
 Originally Posted by andreien 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.
Don't get fixated on 140!+1. What is wrong with trying to factor 140!+653 ? Can you?

And when that is done, there are thousands more. What is special about 140!+1 ?

Code:
GMP-ECM 7.0.3 [configured with GMP 6.1.1, --enable-asm-redc] [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

2022-09-25, 16:43   #7
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

37×313 Posts

Quote:
 Originally Posted by Batalov What is special about 140!+1 ?
Kolmogorov might like to have a word with you.

2022-09-25, 17:02   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

234048 Posts

Quote:
 Originally Posted by xilman Kolmogorov might like to have a word with you.
I made him an offer he couldn't refuse. Haven't heard from him.

 2022-09-25, 17:25 #9 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 203428 Posts We have more theory to throw out there. No two consecutive numbers of form n!+1 can have shared factors.
 2022-09-30, 09:24 #10 sean     Aug 2004 New Zealand 2×5×23 Posts I've performed 30000 curves with B1=850M without success on this number.
 2022-09-30, 09:29 #11 sean     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+(1-o(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]

 Similar Threads Thread Thread Starter Forum Replies Last Post baih Miscellaneous Math 9 2020-09-21 07:11 xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 03:39.

Sat Dec 3 03:39:56 UTC 2022 up 107 days, 1:08, 0 users, load averages: 1.18, 1.14, 1.16