mersenneforum.org Factoring n!+1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

2×3×23×61 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

2·33·5·37 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

26×181 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

999010 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 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 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 E616 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 09:55.

Wed Dec 7 09:55:43 UTC 2022 up 111 days, 7:24, 0 users, load averages: 0.69, 0.80, 0.83

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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐