2
$\begingroup$

To explain the process, I was working on some ProjectEuler.net problems and I had just figured out a formula to solve for triangle numbers efficiently. The next problem needed me to solve for factorials. At the time (before I found out there is not a known equation where you can input n and get the nth factorial) I thought maybe I would work on relating the nth triangle, and n with the nth factorial.

After some time playing around with this, I found that:

If $F_n = n!$ and $T_n$ is the $n^{th}$ triangular number then $F_n\text{ (mod $T_n$)} = n$ if and only if $n+1$ is prime

After some research I found that this is very closely related to Wilson's Theorem:

$( n − 1 ) ! \equiv − 1 ( \text{ mod $n$} )$

I also understand that Triangle Numbers are very closely related to $n$ given the formula mentioned earlier $T_n = {n(n+1) \above 1.5pt 2}$. But these two statements do not seem to explain away the relation between:

$F_n \text{ (mod $T_n$)} \equiv F_n\text{ mod(n+1)}$

At least not in a way that I am grasping. Admittedly, I feel like I'm missing something very basic. So, I have spent my free time for about a week now trying to prove a lack of significance here. Mostly by factoring out various numbers and seeing how n and Tn relate. They obviously do achieve similar results when dividing other numbers besides Fn, but the reason that it lines up for every Fn still seems to escape me.

So I guess my question is: is this completely insignificant? And if not, are there other materials or proofs that could help me dive into this problem further? I can not find many papers written about the relationship between triangles, primes, factorials. Other than this one:

http://www.integers-ejcnt.org/l50/l50.pdf

but this does not seem to be congruent with my problem.

Python code: def get_fact_num(n): fact = 1 for x in range(1,n+1): fact = fact*(x) return fact def get_tri_num(n): tri_num = (n*(n+1))/2 return tri_num def prime_test(n): tri = get_tri_num(n) fact = get_fact_num(n) mod = fact % tri mod2 = fact % (n+1) print n,"::",tri,":",mod,":",mod2 for x in range(4,2000): prime_test(x)

$\endgroup$
  • $\begingroup$ you might be interested to know that there are efficient ways to calculate the factorial, including convergent series. There are also non-convergent but asymptotic series that will work nicely for large values of $n$ in $n!$. $\endgroup$ – Brevan Ellefsen Aug 11 '16 at 19:25
  • 1
    $\begingroup$ I think you mean to write $T_n={n(n+1)\over2}$, not ${n(n-1)\over2}$. Consider $n=4$, so that $n+1=5$ is prime. We have $4!=24\equiv4$ mod $10$, but not mod $6$. $\endgroup$ – Barry Cipra Aug 11 '16 at 19:49
  • $\begingroup$ Thanks @BarryCipar that was just a mistake. you can see my python code is "n+!." $\endgroup$ – B.O'Dell Aug 11 '16 at 20:08
  • $\begingroup$ @BrevanEllefsen do you have a link or example? $\endgroup$ – B.O'Dell Aug 11 '16 at 20:08
  • 1
    $\begingroup$ Quick and dirty estimation is $\sqrt{2\pi n}n^ne^{-n}\left(1+O(\frac 1 n)\right)$. This is the first term in an infinite series that is asymptotically equal (and is known as Stirling's Approximation ). However, this series is not convergent... for a convergent series you can use the one on the page linked above entitled "A convergent version of Stirling's formula" although some hurdles will still be required. Not necessarily the fastest way to calculate factorials, but I thought you might nevertheless be interested. $\endgroup$ – Brevan Ellefsen Aug 11 '16 at 20:11
2
$\begingroup$

Your two statements are equivalent to saying the following:

$n! = -1 + (n+1)j$ for odd prime $n+1$ and integer $j$.

$n! = n + \frac{n(n+1)k}{2}$ for odd prime $n+1$ and integer $k$.

Let $m=j-1$ and $q = \frac{nk}{2}$ (which will be an integer since $n+1$ is prime so $n$ is an even number and will divide by the denominator of $2$), then these equations become

$n! = n + (n+1)m$ for odd prime $n+1$ and integer $m$.

$n! = n + (n+1)q$ for odd prime $n+1$ and integer $q$.

Exact same expressions. The result isn't all that significant, it just happens to give the same result because of Wilson's Theorem and the fact that triangle numbers also involve $(n+1)$. Since we peel off $n+1$ from the modulus of the first equation and change it to $(n+1) + (-1) = n$, this is why it happens to be the same.

$\endgroup$
1
$\begingroup$

Case 1: $n = 2m-1$ is odd, $T_n = m(2m-1)$. $n! \equiv 0 \mod m$ and $\equiv 0 \mod 2m-1$, thus $\equiv 0 \mod T_n$.

Case 2: $n = 2m$ is even, $T_n = m(2m+1)$. $n! \equiv 0 \mod m$. If $2m+1$ is prime, then $n! \equiv -1 \mod 2m+1$, so $n! \equiv n \mod T_n$ by the Chinese Remainder Theorem (since $n \equiv 0 \mod m$ and $n \equiv -1 \mod 2m+1$). If $2m+1$ is not prime, $n! \equiv 0 \mod 2m+1$ and $n! \equiv 0 \mod T_n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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