mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-09-24, 10:02   #1
andreien
 
Sep 2022

1 Posts
Question 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.
andreien is offline   Reply With Quote
Old 2022-09-24, 12:00   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22×52×23 Posts
Default

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
a1call is offline   Reply With Quote
Old 2022-09-24, 14:30   #3
charybdis
 
charybdis's Avatar
 
Apr 2020

87410 Posts
Default

Quote:
Originally Posted by andreien View Post
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.
charybdis is offline   Reply With Quote
Old 2022-09-24, 17:45   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22·52·23 Posts
Default

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
a1call is offline   Reply With Quote
Old 2022-09-24, 19:54   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by a1call View 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.
We have \[n!\equiv 1\pmod p\] for \[n=p-2\]
As well.
science_man_88 is offline   Reply With Quote
Old 2022-09-24, 21:58   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·1,997 Posts
Question

Quote:
Originally Posted by andreien View Post
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
Batalov is offline   Reply With Quote
Old 2022-09-25, 16:43   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

71×163 Posts
Default

Quote:
Originally Posted by Batalov View Post
What is special about 140!+1 ?
Kolmogorov might like to have a word with you.
xilman is online now   Reply With Quote
Old 2022-09-25, 17:02   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111000000012 Posts
Default

Quote:
Originally Posted by xilman View Post
Kolmogorov might like to have a word with you.
I made him an offer he couldn't refuse. Haven't heard from him.
Batalov is offline   Reply With Quote
Old 2022-09-25, 17:25   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

We have more theory to throw out there. No two consecutive numbers of form n!+1 can have shared factors.
science_man_88 is offline   Reply With Quote
Old 2022-09-30, 09:24   #10
sean
 
sean's Avatar
 
Aug 2004
New Zealand

2·5·23 Posts
Default

I've performed 30000 curves with B1=850M without success on this number.
sean is offline   Reply With Quote
Old 2022-09-30, 09:29   #11
sean
 
sean's Avatar
 
Aug 2004
New Zealand

2×5×23 Posts
Default

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]
sean is offline   Reply With Quote
Reply

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 2020-09-21 07:11
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 19:04.


Sun Nov 27 19:04:27 UTC 2022 up 101 days, 16:33, 0 users, load averages: 1.65, 1.31, 1.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”