What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T07:46:29Z http://mathoverflow.net/feeds/question/24265 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24265/what-is-the-limit-of-gcd1-2-n-1-n What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ? Robin Tucker-Drob 2010-05-11T17:27:26Z 2010-06-09T06:38:02Z <p>Let <code>$s_n = \sum_{i=1}^{n-1} i!$</code> and let <code>$g_n = \gcd (s_n, n!)$</code>. 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$.</p> <p>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$.</p> <p>If $p$ is a prime dividing $g_n$ but not dividing $g_{n-1}$ then $p=n$, for if <code>$p&lt;n$</code> then $p$ divides $(n-1)!$ and therefore $p$ divides $s_n-(n-1)!=s_{n-1}$, whence $p$ divides $g_{n-1}$.</p> <p>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$).</p> http://mathoverflow.net/questions/24265/what-is-the-limit-of-gcd1-2-n-1-n/24277#24277 Answer by Kevin Buzzard for What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ? Kevin Buzzard 2010-05-11T18:53:43Z 2010-05-11T18:53:43Z <p>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!]</p> http://mathoverflow.net/questions/24265/what-is-the-limit-of-gcd1-2-n-1-n/24286#24286 Answer by Gjergji Zaimi for What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ? Gjergji Zaimi 2010-05-11T19:58:50Z 2010-06-09T04:00:03Z <p>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)$:</p> <p>a) It is equivalent to $K(\infty)=\sum_{k=1}^{\infty}k!$ not being a unit in $\mathbb Z_p$.</p> <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}$)</p> <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".</p> http://mathoverflow.net/questions/24265/what-is-the-limit-of-gcd1-2-n-1-n/27556#27556 Answer by Terry Tao for What is the limit of gcd(1! + 2! + ... + (n-1)! , n!) ? Terry Tao 2010-06-09T06:05:10Z 2010-06-09T06:38:02Z <p>An amusing (but perhaps useless) observation: the property $1! + \ldots + (p-1)! = 0 \hbox{ mod } p$ is also equivalent to the matrix product property</p> <p>$$\left( \begin{array}{ll} 1 &amp; 1 \\ 0 &amp; 1 \end{array} \right) \begin{pmatrix} 2 &amp; 1 \\ 0 &amp; 1 \end{pmatrix} \ldots \begin{pmatrix} p &amp; 1 \\ 0 &amp; 1 \end{pmatrix} = \begin{pmatrix} 0 &amp; 0 \\ 0 &amp; 1 \end{pmatrix} \hbox{ mod } p.$$</p> <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.</p> <p>A third reformulation: $p | \lfloor (p-2)!/e \rfloor$ (assuming p is odd).</p>