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

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

2010-05-11T17:27:26Z

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

Answer by Kevin Buzzard for What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ?

2010-05-11T18:53:43Z

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

Answer by Gjergji Zaimi for What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ?

2010-05-11T19:58:50Z

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

Answer by Terry Tao for What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ?

2010-06-09T06:05:10Z

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