56
$\begingroup$

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.

$\endgroup$
  • 15
    $\begingroup$ Damn Peter, back at it again with the large prime numbers 😉 $\endgroup$ – Maximilian Janisch Dec 18 '19 at 18:28
  • 10
    $\begingroup$ By the way, this number is so huge that it would be a record prime. $\endgroup$ – Peter Dec 18 '19 at 18:29
  • 3
    $\begingroup$ 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. $\endgroup$ – WhatsUp Dec 18 '19 at 18:33
  • 2
    $\begingroup$ 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. $\endgroup$ – WhatsUp Dec 18 '19 at 18:54
  • 2
    $\begingroup$ Peter your number has 286,078,171 decimal digits. Too large for a primality test in the next decade I guess. $\endgroup$ – Martin Hopf Dec 19 '19 at 17:09
36
+100
$\begingroup$

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>

#include <thread>

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
    std::thread t0(trial_division, 0);
    std::thread t1(trial_division, 1);
    std::thread t2(trial_division, 2);
    std::thread t3(trial_division, 3);
    std::thread t4(trial_division, 4);
    std::thread t5(trial_division, 5);
    std::thread t6(trial_division, 6);
    std::thread t7(trial_division, 7);

    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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Jan 5 '20 at 15:54
  • 10
    $\begingroup$ @Peter divisor found! $\endgroup$ – Sophie Jan 12 '20 at 19:11
  • 2
    $\begingroup$ 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? $\endgroup$ – Oscar Lanzi Jan 12 '20 at 20:26
  • 10
    $\begingroup$ 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. $\endgroup$ – Sophie Jan 12 '20 at 22:46
  • 1
    $\begingroup$ @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) ? $\endgroup$ – Peter Jan 13 '20 at 8:29
28
+25
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.