16
$\begingroup$

Define $a_n$ as follows:
$$ a_1=1,\ \ a_{n+1}=na_n+1\ $$ At this time, the sequence $a_n$ is as follows: $$ a_n=\sum_{k=1}^{n}\frac{(n-1)!}{(k-1)!} $$ I made some discoveries about this sequence.
The first:$$a_k\equiv 0\pmod{m}\Rightarrow a_{k+Nm}\equiv 0\pmod{m}~~~~\forall k,m,N\in\mathbb{N}$$ The second:$$ n\geq 4\,\Rightarrow\,a_n ~\mathrm{is~composite} $$ I was able to prove the first, but not the second. My expectation is that the second is correct, but I'm not sure it can be proved. My friend used computer and check $a_n$ is composite for $4\leq n\leq 48$. After $a_{49}$, it is too large number to check on his computer. Please let me know if you come up with a proof method. Any help is welcome!

(I am a Japanese college student. I'm sorry for my poor English.)

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ This is oeis.org/A000522 $\endgroup$
    – Fredrik Johansson
    Commented Jul 27, 2020 at 6:58
  • $\begingroup$ $a_i$ is odd resp. even when $i$ is odd resp. even. So $a_i$ is certainly composite for all even $i$. $\endgroup$
    – Ben Smith
    Commented Jul 27, 2020 at 8:14
  • 2
    $\begingroup$ The series $a_{n+1}=\sum_{k=0}^{n} \frac{n!}{k!}$ can be written in another representation. That is $$a_{n+1}=2^n+\sum_{k=2}^{n} \binom{n}{k}2^{n-k}D_k$$. Where, $D_k$ is the number of derangements. $\endgroup$
    – Alapan Das
    Commented Jul 27, 2020 at 8:29

2 Answers 2

Reset to default
18
$\begingroup$

$a_n$ is composite for $4 \le n \le 2016$.

$a_{2017}$ appears to be prime (it passes a strong pseudoprime test). I have not tried to certify that it is prime (this would take a while as the number has 5789 digits).

Improve this answer
$\endgroup$
5
  • 10
    $\begingroup$ A pity this wasn't discovered $3$ years ago. $\endgroup$
    – Robert Israel
    Commented Jul 27, 2020 at 14:19
  • 2
    $\begingroup$ Mathematica seems to think that $a_{2017}$ is prime. I used the FactorInteger command, and after about 10 seconds, it says that $a_{2017}$ is the only prime factor. Mathematica's factorization algorithm is usually not this efficient, which suggests that either (a) Mathematica failed fantastically, of (b) $a_{2017}$ is a prime of a special form. Maybe the algorithm works faster for numbers passing the pseudoprime test that you used. $\endgroup$
    – 2734364041
    Commented Jun 22, 2021 at 0:15
  • 1
    $\begingroup$ Well, Magma didn't have such an easy time of it. It very quickly decided that $a_{2000}$ to $a_{2016}$ were composite, but at $a_{2017}$ my (quite powerful) laptop sat there for five minutes getting hotter and blowing out air before I aborted the computation. I suspect that Mathematica is lying to you about its confidence in its answer. $\endgroup$
    – Dave Benson
    Commented Oct 14, 2023 at 22:52
  • 1
    $\begingroup$ Yes, I believe Mathematica's FactorInt function with default settings is using the Lenstra elliptic-curve factorization method when run with input $a_{2017}$, which only shows that $a_{2017}$ has no small prime factors. To check if $a_{2017}$ is prime with certainty using Mathematica, one could try using the PrimalityProving package, though it would probably take a very, very, very long time to run. $\endgroup$
    – ho boon suan
    Commented Oct 15, 2023 at 2:15
  • 3
    $\begingroup$ This is broadly consistent with the (very crude) heuristic that each $a_n$ has a "probability" of $\approx \frac{1}{\log a_n} \approx \frac{1}{n \log n}$ of being prime; the sum $\sum_{n=2}^\infty \frac{1}{n \log n}$ diverges, but only double logarithmically, so one would tentatively expect an infinite number of counterexamples, but spread out extremely thinly, and it makes sense that the first one is only seen at $n \approx 2000$. $\endgroup$
    – Terry Tao
    Commented Oct 16, 2023 at 5:04
3
$\begingroup$

I just ran this independently for n=2017; confirmed that this number is in fact prime! So an is composite for 4≤n≤2016

I ran sympy.factorint on a i9-13900k for the 5789 digit number n=2017 and it only returned 1 and the number

I ran sympy.factorint on a i9-13900k for the 5789 digit number n=2017 and it only returned 1 and the number

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ That's does not bring much new as compared to the previous answer. Better be added as a comment, not an answer. $\endgroup$
    – Max Alekseyev
    Commented Oct 14, 2023 at 21:26
  • 2
    $\begingroup$ It would be nice to know what exactly you "ran". $\endgroup$
    – Gerry Myerson
    Commented Oct 14, 2023 at 23:26
  • 2
    $\begingroup$ I tried - wasn't able to add a comment due to my account being new. $\endgroup$
    – Conor Grogan
    Commented Oct 15, 2023 at 22:20
  • 1
    $\begingroup$ As I mentioned in a comment to the accepted answer on this post, Lenstra ECM only finds relatively small factors and does not guarantee primality. See the sympy documentation for this function; you can verify this behavior by setting only the use_ecm flag to True for the factorint function. $\endgroup$
    – ho boon suan
    Commented Oct 15, 2023 at 22:53
  • 2
    $\begingroup$ That said, sympy.ntheory.primetest.isprime uses a few seconds to show that $a_{2017}$, if not a prime, is at least a strong Baillie–PSW pseudoprime. The BPSW test is known to be correct up to $n=2^{64}$, and we don't know if BPSW pseudoprimes (i.e., composite numbers that fool the BPSW test into thinking they are prime) exist. (Similar tests are used by say Mathematica's PrimeQ and Maple's isprime, so one has to be quite careful when using a computer to check if a large number is prime.) $\endgroup$
    – ho boon suan
    Commented Oct 15, 2023 at 23:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .