6

I stumbled on a claim on the internet the other day, which alleged that the following formula tests the primality for integers $n\geq2$: $$ \left\lceil\left|\left\{\frac{\left(n+\left\lceil\frac{n}{2}\right\rceil\right)!}{n!n\left\lceil\frac{n}{2}\right\rceil !}\right\}-\frac{1}{n}\right|\right\rceil =\begin{cases} 0,\quad \text{if }n\text{ is prime} \\ 1,\quad \text{if }n\text{ is composite} \end{cases} $$ where $|\cdot|$ is absoulte value, $\lceil\cdot\rceil$ is ceiling function and $\{\cdot\}$ denotes the fractional part.

I test it in Mathematica for $2\leq n\leq5000$ and it seems correct in this range. Code below:

ClearAll["Global`*"] 
f[n_]:=Ceiling[Abs[FractionalPart[(n+Ceiling[n/2])!/(n!n(Ceiling[n/2])!)]-1/n]];
For[i=2,i<=5000,i++,
If[((f[i]==0&&PrimeQ[i]==True)||(f[i]==1&&PrimeQ[i]==False))==False,Print[i," is false"]];
]

Since the formula involves factorial $n!$, its computational efficiency could not be very high. Nonetheless, I have following questions:

  1. Could this formula be valid for the primality test of all $n\geq2$?
  2. If it is a valid formula, does anyone know where this formula comes from?
avocado
  • 61
  • 3
    I'd like to know where you found this claim : particularly because it's difficult to search for this formula in isolation, so I was wondering if you found any other keyword or mathematical term that was used along with this formula, so I could search using that keyword as well. – Sarvesh Ravichandran Iyer Aug 21 '21 at 06:08
  • 1
    Never have seen this formula, maybe it is based on the Wilson theorem because of the factorial. You are right that it has no practical value. – Peter Aug 21 '21 at 07:05
  • You can replace $\lceil \frac{n}{2} \rceil$ with $\lfloor \sqrt{n} \rfloor$ so $\left{\frac{\left(n+\left\lfloor\sqrt{n}\right\rfloor\right)!}{n!n\left\lfloor\sqrt{n}\right\rfloor !}\right}=\left{\frac{(n+1)(n+2)\cdots (n+\left\lfloor\sqrt{n}\right\rfloor)}{n\left\lfloor\sqrt{n}\right\rfloor!}\right}$ which is equal to $\frac{1}{n}$ if $n$ is prime and $\frac{q+1}{n}$ if $n=p q$ with $p<q$ – user140242 Aug 21 '21 at 18:24
  • 1
    @avocado You can simplify the expression to be $\binom{n + \left\lceil \frac{n}{2} \right\rceil}{n} \equiv 1 \pmod{n}$ being true iff $n$ is prime. The "if" part can be fairly easily shown using Lucas's theorem, but I'm not sure how to possibly show the "only if" part. – John Omielan Aug 21 '21 at 19:07

0 Answers0