# Can I search for factors of $\ (11!)!+11!+1\$ efficiently?

Is the number $$(11!)!+11!+1$$ a prime number ?

I do not expect that a probable-prime-test is feasible, but if someone actually wants to let it run, this would of course be very nice. The main hope is to find a factor to show that the number is not prime. If we do not find a factor, it will be difficult to check the number for primality. I highly expect a probable-prime-test to reveal that the number is composite. "Composite" would be a surely correct result. Only if the result would be "probable prime", there would remain slight doubts, but I would be confident with such a test anyway.

Motivation : $$(n!)!+n!+1$$ can only be prime if $$\ n!+1\$$ is prime. This is because a non-trivial factor of $$\ n!+1\$$ would also divide $$\ (n!)!+n!+1\$$. The cases $$\ n=2,3\$$ are easy , but the case $$\ n=11\$$ is the first non-trivial case. We only know that there is no factor upto $$\ p=11!+1\$$

What I want to know : Can we calculate $$(11!)!\mod \ p$$ for $$\ p\$$ having $$\ 8-12\$$ digits with a trick ? I ask because pari/gp takes relatively long to calculate this residue directly. So, I am looking for an acceleration of this trial division.

• Damn Peter, back at it again with the large prime numbers 😉 – Maximilian Janisch Dec 18 '19 at 18:28
• By the way, this number is so huge that it would be a record prime. – Peter Dec 18 '19 at 18:29
• There is probably no better way to calculate a factorial mod $p$, as it would turn Wilson's theorem into a prime testing algorithm. But $11!$ is only about $4e7$, so a proper implementation in e.g. C should be fast enough for single query (in less than a second). It's a different story if you want to test for ~$1e6$ primes, though. – WhatsUp Dec 18 '19 at 18:33
• I'd say your chance is very low with this "test divide" approach, at least without any heuristic on the form of a possible divisor. – WhatsUp Dec 18 '19 at 18:54
• Peter your number has 286,078,171 decimal digits. Too large for a primality test in the next decade I guess. – Martin Hopf Dec 19 '19 at 17:09

I let $$p_1=1+11!$$ for convenience. By Wilson's theorem if there's a prime $$p$$ that divides $$1+11!+(11!)! = p_1 + (p_1-1)!$$ then

$$(p-1)!\equiv -1\pmod p$$

And also

$$(p_1-1)!\equiv -p_1$$

So

$$(p-1)(p-2)...p_1\cdot(p_1-1)!\equiv -1$$

$$(p-1)(p-2)...p_1\cdot p_1\equiv 1$$

This way I was able to check all the primes from $$p_1$$ to 74000000 in 12 hours. This gives a 3.4% chance of finding a factor according to big prime country's heuristic. The algorithm has bad asymptotic complexity because to check a prime $$p$$ you need to perform $$p-11!$$ modular multiplications so there's not much hope of completing the calculation.

Note that I haven't used that $$p_1$$ is prime, so maybe that can still help somehow. Here's the algorithm in c++:

// compile with g++ main.cpp -o main -lpthread -O3

#include <iostream>
#include <vector>
#include <string>

#include <boost/process.hpp>

namespace bp = boost::process;

const constexpr unsigned int p1 = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 + 1; // 11!+1
const constexpr unsigned int max = 100'000'000;                                    // maximum to trial divide
std::vector<unsigned int> primes;
unsigned int progress = 40;

void trial_division(unsigned int n) { // check the primes congruent to 2n+1 mod 16
for(auto p : primes) {
if(p % 16 != (2 * n + 1)) continue;
uint64_t prod = 1;
for(uint64_t i = p - 1; i >= p1; --i) {
prod = (prod * i) % p;
}
if((prod * p1) % p == 1) {
std::cout << p << "\n";
}
if(n == 0 && p > progress * 1'000'000) {
std::cout << progress * 1'000'000 << "\n";
++progress;
}
}
}

int main() {
bp::ipstream is;
bp::child primegen("./primes", std::to_string(p1), std::to_string(max), bp::std_out > is);
// this is https://cr.yp.to/primegen.html
// the size of these primes don't really justify using such a specialized tool, I'm just lazy

std::string line;
while (primegen.running() && std::getline(is, line) && !line.empty()) {
primes.push_back(std::stoi(line));
} // building the primes vector

// start 8 threads, one for each core for on my computer, each checking one residue class mod 16
// By Dirichlet's theorem on arithmetic progressions they should progress at the same speed
// the 16n+1 thread owns the progress counter

t0.join();
t1.join();
t2.join();
t3.join();
t4.join();
t5.join();
t6.join();
t7.join();
}


I only need to multiply integers of the order of $$11!$$ so standard 64 bit ints suffice.

EDIT: Divisor found! $$1590429889$$

So first of all, the Wilson's theorem trick slows down instead of speeding up after $$2p_1$$. Secondly, the trial division function is nearly infinitely parallelizable, which means that it's prone to being computed with a GPU. My friend wrote an implementation that can be found here. This can be run on CUDA compatible nvidia GPUs. Finding the factor took about 18 hours on a Nvidia GTX Titan X pascal.

• Since I do not expect a prime divisor to be found until the end of this bounty, I reward the relatively large search limit with an accept and 100 reputation points. – Peter Jan 5 '20 at 15:54
• @Peter divisor found! – Sophie Jan 12 '20 at 19:11
• Impressive @sophie! The divisor is very low compared with the statistically based expectations (see big prime country's answer). Do you have any idea why it happened? – Oscar Lanzi Jan 12 '20 at 20:26
• The chance of finding a divisor up to 1590429889 is 17.3% aka about one sixth. I think if I tried to find a special meaning every time I got a stroke of luck equivalent to rolling 6 on a dice I'd go insane. – Sophie Jan 12 '20 at 22:46
• @Sophie $(1)$ Thank you for the search. My bounty was well invested :) $(2)$ Does this estimate consider that there cannot be a prime factor less than 11! ? $(3)$ 1:6 is not so low after all $(4)$ Apparently, your software is much much faster than pari/gp. $(5)$ Did you search by brute force (meaning that there is no smaller prime factor) ? – Peter Jan 13 '20 at 8:29

By Mertens' theorem, we have

$$\prod_{p < n} \left(1 - \frac{1}{n}\right) \sim \frac{e^{-\gamma}}{\log(n)},$$

In particular, if you do "trial division" of a large number $$N \gg b^2$$ for $$a < p < b$$ with $$a$$ and $$b$$ very large, you expect to fail to find a factor approximately

$$\prod_{a < p < b} \left(1 - \frac{1}{p} \right) \sim \frac{\log(a)}{\log(b)}$$

of the time. In your case, you have $$a \sim 11!$$. So, for example, to have a 50% chance of finding a factor, you would want to take $$\log(b) \sim 2 \log(a)$$, or $$b \sim a^2$$. For $$b = 11!$$, this would involve trial division to primes well over $$10^{15}$$, and in particular (estimating using the prime number theorem) more than 10 trillion primes. That seems a little unlikely to ever be possible.

Note that $$11!$$ is about $$39$$ million. If you wanted merely to check the next 10 million primes after $$11!$$ (involving taking $$b$$ around $$230$$ million or so), your chance of finding a factor would be less than 10%.

In particular, even if you speed up your computation of $$(11!)! \pmod p$$ for $$p \sim 10^{10}$$ to one second (on pari currently it seems to take around 13 seconds), it would then take 80 days to have a 10% chance of finding an answer.