62
$\begingroup$

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$).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ May 12, 2010 at 7:15
  • 3
    $\begingroup$ 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)!... $\endgroup$
    – Terry Tao
    Jun 9, 2010 at 5:58

4 Answers 4

25
$\begingroup$

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".

$\endgroup$
4
  • $\begingroup$ Why was this answer accepted? As far as I can tell, it doesn't solve the problem. $\endgroup$ May 12, 2010 at 1:20
  • 2
    $\begingroup$ @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. $\endgroup$
    – S. Carnahan
    May 12, 2010 at 1:34
  • 1
    $\begingroup$ being a unit --> $\textit{not}$ being a unit $\endgroup$ Jun 8, 2010 at 16:58
  • 25
    $\begingroup$ 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. $\endgroup$ Nov 27, 2012 at 8:15
29
$\begingroup$

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).

$\endgroup$
1
14
$\begingroup$

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!]

$\endgroup$
4
  • 7
    $\begingroup$ 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? $\endgroup$ May 11, 2010 at 19:37
  • 1
    $\begingroup$ 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$ $\endgroup$ May 11, 2010 at 19:43
  • 2
    $\begingroup$ If a prime less than 100.000 divided it, wouldn't that be a contradiction what is written in the question? $\endgroup$ May 11, 2010 at 20:07
  • 10
    $\begingroup$ @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. $\endgroup$ May 11, 2010 at 21:37
11
$\begingroup$

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]

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Arimakat
    Jul 31, 2015 at 1:05

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