Factoring n!+1

andreien · 2022-09-24, 10:02

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.

a1call · 2022-09-24, 12:00

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.

charybdis · 2022-09-24, 14:30

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.

a1call · 2022-09-24, 17:45

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.

science_man_88 · 2022-09-24, 19:54

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.

Batalov · 2022-09-24, 21:58

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

xilman · 2022-09-25, 16:43

Quote:

Originally Posted by Batalov

What is special about 140!+1 ?

Kolmogorov might like to have a word with you.

Batalov · 2022-09-25, 17:02

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.

science_man_88 · 2022-09-25, 17:25

We have more theory to throw out there. No two consecutive numbers of form n!+1 can have shared factors.

sean · 2022-09-30, 09:24

I've performed 30000 curves with B1=850M without success on this number.

sean · 2022-09-30, 09:29

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]

2022-09-24, 10:02	#1
andreien Sep 2022 1 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 928₁₆ 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, 17:45	#4
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2³×293 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think)	baih	Miscellaneous Math	9	2020-09-21 07:11
OpenCL GPU P-1 Factoring and ECM Factoring	xx005fs	GPU Computing	3	2018-10-27 14:49

2022-09-25, 17:25	#9
science_man_88 "Forget I exist" Jul 2009 Dartmouth NS 2·3·23·61 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 230₁₀ 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 E6₁₆ 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]