# What is the limit of gcd(1! + 2! + … + (n-1)! , n!) ?

Let $s_n = \sum_{i=1}^{n-1} i!$ and let $g_n = \gcd (s_n, n!)$. Then it is easy to see that $g_n$ divides $g_{n+1}$. The first few values of $g_n$, starting at $n=2$ are $1, 3, 3, 3, 9, 9, 9, 9, 9, 99$, where $g_{11}=99$. Then $g_n=99$ for $11\leq n\leq 100,000$.

Note that if $n$ divides $s_n$, then $n$ divides $g_m$ for all $m\geq n$. If $n$ does not divide $s_n$, then $n$ does not divide $s_m$ for any $m\geq n$.

If $p$ is a prime dividing $g_n$ but not dividing $g_{n-1}$ then $p=n$, for if $p<n$ then $p$ divides $(n-1)!$ and therefore $p$ divides $s_n-(n-1)!=s_{n-1}$, whence $p$ divides $g_{n-1}$.

So to show that $g_n\rightarrow \infty$ it suffices to show that there are infinitely many primes $p$ such that $1!+2!+\cdots +(p-1)! \equiv 0$ (mod $p$).

• A straightforward generalization of this question is perhaps: Which integers $a,b$ with non-zero $b$ give rise to an unbounded sequence $g_n=\mathrm{gcd}(a+b\sum_{i=1}^{n-1}i!,n!)$? Buzzards answer below suggests that this should happen generically. – Roland Bacher May 12 '10 at 7:15
• It seems to me that the sufficient condition is almost necessary. If for instance 1! + ... + (p-1)! is not divisible by p for any p>11, then the only primes that can divide g_n are 3 and 11, and by looking at the n=9 and n=22 cases, we see that 3^3 and 11^2 are never factors, so the limit is 99. But I don't see how to make real progress on understanding 1! + ... + (p-1)!... – Terry Tao Jun 9 '10 at 5:58

This is so close to the Kurepa conjecture which asserts that $\gcd\left(\sum_{k=0}^{n-1}k!,n!\right)=2$ for all $n\geq 2$, which was settled in 2004 by D. Barsky and B. Benzaghou "Nombres de Bell et somme de factorielles". So what they proved is that $K(p)=1!+\cdots+(p-1)!\neq -1\pmod{p}$ for any odd prime $p$. This goes against Kevin Buzzard's heuristic that $K(p)$ is random mod $p$. Let me mention two ways you can restate the fact $p|K(p)$:

a) It is equivalent to $K(\infty)=\sum_{k=1}^{\infty}k!$ not being a unit in $\mathbb Z_p$.

b) It is equivalent to $\mathcal B_{p-1}=2\pmod{p}$ where $\mathcal{B} _n$ is the $n$th Bell number. (It is easy to show that $\mathcal B _{p}=2\pmod{p}$)

I forgot to mention that the conjecture that $p>11$ doesn't divide $K(p)$ is in question B44 of R. Guy's "Unsolved Problems in Number theory".

• Why was this answer accepted? As far as I can tell, it doesn't solve the problem. – Qiaochu Yuan May 12 '10 at 1:20
• @Qiaochu: I imagine it was accepted because the last line described the current (or recent) status of the problem, as interpreted in the last line of the question. The first bit just gives an indication that naive heuristics don't necessarily apply here. – S. Carnahan May 12 '10 at 1:34
• being a unit --> $\textit{not}$ being a unit – Victor Protsak Jun 8 '10 at 16:58
• By the way, the "proof" of the Kurepa conjecture turned out to be false. Here's an extract from the Erratum à l'article Nombres de Bell et somme de factorielles [MR2817943]:  As pointed out to us by Farid Bencherif and Joseph Oesterlé, there are some irreparable calculation errors in the proof of Theorem 3 of our article. Theorem 3 and its proof (the Kurepa conjecture) are therefore withdrawn, and the Kurepa conjecture ($0!+1!+⋯+(p−1)!\not\equiv0\pmod p$,for prime $p\ge3$) is not proved. – Chandan Singh Dalawat Nov 27 '12 at 8:15

An amusing (but perhaps useless) observation: the property $1! + \ldots + (p-1)! = 0 \hbox{ mod } p$ is also equivalent to the matrix product property

$$\left( \begin{array}{ll} 1 & 1 \\\ 0 & 1 \end{array} \right) \begin{pmatrix} 2 & 1 \\\ 0 & 1 \end{pmatrix} \ldots \begin{pmatrix} p & 1 \\\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\\ 0 & 1 \end{pmatrix} \hbox{ mod } p.$$

Another reformulation: if $f: F_p \times F_p \to F_p$ is the map $f(x,y) := (x-1,xy+1)$, then $f^p(0,0) = (0,1)$, where $f^p$ is the p-fold iterate of f.

A third reformulation: $p | \lfloor (p-2)!/e \rfloor$ (assuming p is odd).

Here's my guess: it might be out of reach to prove that $g_n$ tends to infinity, but it probably does, because $1!+2!+\ldots+(p-1)!$ is a "random" number mod $p$, so the chances that it's divisible by $p$ is about $1/p$, and the sum of the reciprocals of the primes diverges. This isn't a proof of anything, but it's a heuristic indicating that probably the $g_n$ diverge. [Of course there might be other heuristics suggesting it doesn't!]

• Do you have a reason to believe that the expression is particular random - bearing in mind such formulas as (p-1)!=-1 and $((p-1)/2)!)^2=1$? and other symmetries? – Thomas Kragh May 11 '10 at 19:37
• According to the OEIS (research.att.com/~njas/sequences/A057245 ), $3$ and $11$ are the only primes less than $27390$ for which the sum is divisible by $p$ – Kevin P. Costello May 11 '10 at 19:43
• If a prime less than 100.000 divided it, wouldn't that be a contradiction what is written in the question? – Thomas Kragh May 11 '10 at 20:07
• @Thomas Kragh: I don't think your observations convince me that the sum is anything but random. You know what a couple of the terms are mod p but you don't know what most of them are. The reason I believe it's random is that we see that in practice it's sometimes 0 mod p and sometimes it's not. The sum of the reciprocals of the primes up to 100,000 is 2.7 so again it's not surprising that we find 2 primes which have the property required. – Kevin Buzzard May 11 '10 at 21:37

The current state of search is that $g_n=99$ for $11\leq n\leq 10,000,000,000$. I'll mention that Kurepa's conjecture, which means that $s_p\neq -1\pmod p$ holds for odd primes $p$, is true for $p<10^{10}$. It is interesting that $s_p=1\pmod p$ holds for $p=6,855,730,873$, and this is the first such prime after $p=31$ and $p=373$.

Searching for a counterexample of Kurepa's conjecture, arXiv:1409.0800 [math.NT]

• The cited article is updated till $p<2^{34}$, nothing interesting is found, so $g_n=99$ for $11\leq n\leq 17,179,869,184$. – Arimakat Jul 31 '15 at 1:05

## protected by LuciaNov 8 '15 at 17:33

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?