New Equivalents of Kurepa’s Hypothesis for Left Factorial ^†

Abstract

Kurepa’s hypothesis for the left factorial has been an unsolved problem for more than 50 years. In this paper, we have proposed new equivalents for Kurepa’s hypothesis for the left factorial. The connection between the left factorial and the continued fractions is given. The new equivalent based on the properties of the integer part of real numbers is proven. Moreover, a new equivalent based on the properties of two well-known sequences is given. A new representation of the left factorial is listed. Since derangement numbers are closely related to Kurepa’s hypothesis, we made some notes about the derangement numbers and defined a new sequence of natural numbers based on the derangement numbers. In this paper, we indicate a possible direction for further research through solving quadratic equations.

1. Introduction and Preliminaries

Pythagoras, a renowned Greek philosopher and mathematician who lived between 570 BC and 495 BC, believed that numbers could be used to express everything. He based his philosophy on the concept that mathematical relationships could describe the universe. According to Weil in [1], the birth of the modern number theory took place between 1621 and 1636. This was when Bachet (1581–1638), a French mathematician, published Diophantus’ book Aritmetica in Latin, along with his comments. Diophantus (around 200–284 AD) was a Greek mathematician known as the “father of algebra” for his revolutionary contributions to solving Diophantine equations. Diophantine equations are equations with integer solutions, and Diophantus developed methods for solving them. The connection between Pythagoras and Diophantus lies in the fact that Diophantus continued and developed the ideas and techniques used in Pythagoras’ studies of number theory. He advanced the study of Diophantine equations, which was part of Pythagoras’ number theory. Diophantus’s works greatly influenced the further development of number theory, including many concepts established by Pythagoras. Although their work was separated by centuries, it can be said that in his works, Diophantus inherited and expanded upon many of Pythagoras’ mathematical ideas and concepts, particularly regarding number theory. In this article, we will examine an unresolved problem in modern number theory. Namely, we will consider Kurepa’s hypothesis. Moreover, we point out the possibility of including Diophantine equations in solving Kurepa’s hypothesis and this could be a new direction in solving this open problem.

Kurepa’s hypothesis for the left factorial, or in short, Kurepa’s hypothesis, was formulated in 1971 by Đuro Kurepa (1907–1993) and is still an open problem. The purpose of this paper is to contribute to the ongoing efforts to understand and solve Kurepa’s hypothesis by providing new perspectives and connections to other mathematical concepts.

The paper is organized as follows. In the sequel of the introductory section, we present a historical overview and a brief review of the current status of Kurepa’s hypothesis. Then, we briefly introduce notation and basic concepts used in the following sections. Section 2 establishes the connection between the left factorial and the continued fractions. We prove a new equivalent based on the properties of the integer part of real numbers. We also list two new equivalents based on the properties of two well-known sequences. We will list a new representation of the left factorial. In addition, we made some remarks under the assumption that Kurepa’s hypothesis is not correct (in Section 2.2). Some properties of derangement numbers are proven in Section 2.3. Finally, in Section 3, we present conclusions and indicate possible directions for further research.

1.1. Historical Overview and Current State of Research

In [2], Kurepa proposed the hypothesis for the left factorial: For every natural number $n>1$, it holds

$$gcd(!n,n!)=2$$

where $gcd(a,b)$ is the greatest common divisor of integers a and b and the left factorial $!n$ is defined by

$$!0=0, !n=\sum _{k=0}^{n-1}k! (n\in \mathbb{N})$$

In the same paper, Kurepa gave an equivalent reformulation of the hypothesis [2] (Thm. 2.4, pg. 149):

$$!p\not\equiv 0(\mathrm{mod} p) \mathrm{for} p \mathrm{odd} \mathrm{prime}.$$

(1)

Over the past fifty years, there have been many attempts to find a solution to Kurepa’s hypothesis, and the problem remains open. This problem is listed in Guy’s [3] (Problem B44), Koninck–Mercier’s [4] (Problem 37), and in Sandor–Cristici’s [5] books and has been studied by numerous researchers. Some of them provided equivalents to Kurepa’s hypothesis [6,7,8,9,10,11,12], some performed computer tests, looking for a counterexample or calculating the left factorial residues [13,14,15,16,17,18]. Most recently, Andrejić, Bostan, and Tatarević, in their paper [19], showed that Kurepa’s hypothesis is valid for $p<2^{40}$. At the same time, Rajkumar [20] independently used the same method as Andrejić, Bostan, and Tatarević [19], but he studied in detail only the theoretical aspects, without program implementation. Numerous papers are dedicated to the generalization of the left factorial function [21,22,23,24], the extension to complex numbers [25,26,27], and the connection with well-known polynomials and functions [28,29,30,31]. In [32], the authors reviewed some of the problems in number theory posed by Kurepa, including Kurepa’s hypothesis, and presented some of the known results concerning them. In 1971, Kurepa, in his paper [33], proved some new left factorial propositions. Some considerations and inequalities for the left factorial are given by Malešević in [34,35,36,37]. Several identities involving the left factorial are given in [38,39]. In [40,41,42], the authors considered the connection between the left factorial and trees. More recent investigations of Kurepa’s hypothesis are given in papers [43,44,45]. There are several announcements about the final solution of Kurepa’s hypothesis [46], even published papers with incorrect proof [47]. More details on the historical background of Kurepa’s hypothesis and its impact on solving other open problems can be found in [46].

Let us emphasize once again that the aim of this paper is to present new equivalents to Kurepa’s hypothesis and to point out new possibilities for researching problems related to Kurepa’s hypothesis. There are various equivalents of the hypothesis and their importance is that they may help to solve the problem of whether Kurepa’s hypothesis is correct or not.

1.2. Preliminaries

Let $\mathbb{N}$ be the set of natural numbers (positive integers). Let $\left[t\right]$ denote the integer part of a real number t, and $e\approx 2.71828$ is Euler’s number.

Let us recall some statements proven by Mijajlović [16] and Šami [11], which we will use in the sequel. It holds that

$$!n\equiv {(-1)}^{n-1}{S}_{n-1}(\mathrm{mod} n) \mathrm{for} \mathrm{all} n>2$$

(2)

where $S_n$ are the derangement numbers cf. ([48] (p. 65), [49] (p. 182), [21]) defined by

$$S_n:=n!\sum _{\nu =0}^n\frac{{(-1)}^{\nu }}{\nu !} (n\ge 0)$$

(3)

The derangement numbers $S_n$ satisfy the following recurrence relation

$$S_n=n{S}_{n-1}+{(-1)}^n, \mathrm{with} S_0=1.$$

(4)

Bell numbers are defined by

$$B_n:=\sum _{k=0}^{n-1}\left(\genfrac{}{}{0pt}{}{n-1}{k}\right)B_k \mathrm{with} B_0:=1.$$

(5)

Based on the properties of Bell numbers, Barsky and Benzaghou in [47] and Sun and Zagier in [10] showed the following equivalent of Kurepa’s hypothesis for any prime number p:

$$!p\equiv B_{p-1}-1(\mathrm{mod} p)$$

(6)

2. Results

We start this section by listing the equivalents of Kurepa’s hypothesis.

2.1. Equivalents of Kurepa’s Hypothesis

We will now state the equivalent of Kurepa’s hypothesis based on the properties of continued fractions. The continued fraction (see [50])

$$r_0+\frac{t_1}{r_1+\frac{t_2}{\dots +\frac{t_{n-1}}{r_{n-1}+\frac{t_n}{r_n}}}}$$

is denoted by

$$r_0+\frac{t_1|}{| r_1}+\frac{t_2|}{| r_2}+\dots +\frac{t_n|}{| r_n}=\frac{x_n}{y_n}$$

where the sequences ${\left\{x_n\right\}}_{n=0}^{\infty }$ and ${\left\{y_n\right\}}_{n=0}^{\infty }$ are given by

$$\begin{array}{lll}{x}_0=r_0, & x_1=r_0{r}_1+t_1, & x_n=r_n{x}_{n-1}+t_n{x}_{n-2},\end{array}$$

(7)

$$\begin{array}{lll}{y}_0=1, & y_1=r_1, & y_n=r_n{y}_{n-1}+t_n{y}_{n-2}.\end{array}$$

(8)

Theorem 1. 

Let $n\in \mathbb{N}$, $n>2$. Then

$$!n\equiv {(-1)}^{n-1}(n-1)!·\left(1-\frac{1|}{| 1}+\frac{1|}{| 1}+\frac{2|}{| 2}+\dots +\frac{n-2|}{| n-2}\right)(\mathrm{mod} n).$$

Proof. 

From equation (see [50])

$$\sum _{j=0}^n{c}_j=c_0+\frac{c_1|}{| 1}-\frac{\frac{c_2}{c_1}|}{| 1+\frac{c_2}{c_1}}-\dots -\frac{\frac{c_n}{c_{n-1}}|}{| 1+\frac{c_n}{c_{n-1}}}, c_j\ne 0, j\ge 1$$

for $c_0=0$ and $c_j=\frac{{(-1)}^{j+1}}{j!}, j=1,2,\dots ,n-1,$ we obtain

$$\begin{array}{ccc}\hfill \sum _{j=1}^{n-1}\frac{{(-1)}^{j+1}}{j!}& =& 0+\frac{1|}{| 1}+\frac{\frac{1}{2}|}{| 1-\frac{1}{2}}+\dots +\frac{\frac{1}{n-1}|}{| 1-\frac{1}{n-1}}\hfill \\ & =& 0+\frac{1|}{| 1}+\frac{1|}{| 1}+\frac{2|}{| 2}+\dots +\frac{n-2|}{| n-2}=\frac{x_{n-1}}{y_{n-1}}.\hfill \end{array}$$

Using relations (7) and (8), we have

$$\begin{array}{ccc}& x_0=0, x_1=1, x_n=(n-1)(x_{n-1}+x_{n-2}),& \\ & y_0=1, y_1=1, y_n=(n-1)(y_{n-1}+y_{n-2}).\end{array}$$

The sequence ${\left\{x_n\right\}}_{n=0}^{\infty }$ is the already mentioned sequence A002467 in [51] and

$$x_n=n!-S_n$$

is valid for it, while the sequence ${\left\{y_n\right\}}_{n=0}^{\infty }$ is the well-known sequence A000142 in [51] and is also calculated by the formula:

$$y_n=n!.$$

Hence, we have proven our theorem by (2). □

Before we present one of our main results, we state an elementary statement that is easy to prove:

$$n-1\ge \left[\frac{(n-1)!}{e}\right]-n\left[\frac{(n-1)!}{ne}\right]\ge 0 (n\in \mathbb{N}).$$

(9)

The main result of the paper is the following theorem:

Theorem 2. 

For p to be an odd prime number, it holds

$$p-1>\left[\frac{(p-1)!}{e}\right]-p\left[\frac{(p-1)!}{pe}\right]⟺Kurep{a}^{’}s hypothesis.$$

Proof. 

(⇒) Let us assume the opposite: Kurepa’s hypothesis is incorrect, i.e., there is some odd prime number p such that (see (2)) $S_{p-1}\equiv 0(\mathrm{mod} p)$ and the inequality is correct. On the other hand, $a\in \mathbb{N}$ such that $S_{p-1}=pa$ and

$$\left[\frac{(p-1)!}{e}\right]-p\left[\frac{(p-1)!}{pe}\right]<p-1.$$

Hence, the inequality of (9) produces

$$1\le ap-p\left[\frac{(p-1)!}{pe}\right]<p,$$

and consequently

$$\frac{1}{p}\le a-\left[\frac{(p-1)!}{pe}\right]<1,$$

which is a contradiction since the number $a-\left[\frac{(p-1)!}{pe}\right]$ is an integer.

(⇐) Suppose that the inequality

$$p-1>\left[\frac{(p-1)!}{e}\right]-p\left[\frac{(p-1)!}{pe}\right]$$

is incorrect for some odd prime number p, i.e.,

$$\left[\frac{(p-1)!}{e}\right]-p\left[\frac{(p-1)!}{pe}\right]=p-1$$

for some odd prime number p. Then, $\left[\frac{(p-1)!}{e}\right]+1=p\left[\frac{(p-1)!}{pe}\right]+p$ for that odd prime number p. It follows

$$S_{p-1}=p\left[\frac{(p-1)!}{pe}\right]+p.$$

Thus, $S_{p-1}\equiv 0(\mathrm{mod} p)$, and consequently, $!p\equiv 0(\mathrm{mod} p)$, which is a contradiction to Kurepa’s hypothesis. □

Lemma 1. 

Let n be an even natural number. Then

$$n-1>\left[\frac{(n-1)!}{e}\right]-n\left[\frac{(n-1)!}{ne}\right].$$

Proof. 

Let

$$S_{n-1}=an+r, a,r\in {\mathbb{N}}_0, 0\le r\le n-1.$$

For an even number $n>1$, $S_{n-1}$ is an even number. Then, $0\le r<n-1$. Using the well-known statement (see [23] (Pr. 2.3., p. 7))

$$S_n=\left[\frac{n!}{e}\right]+\frac{1+{(-1)}^n}{2} (n\in \mathbb{N}),$$

(10)

we have

$$\left[\frac{(n-1)!}{e}\right]=S_{n-1}=an+r (0\le r<n-1).$$

(11)

Using (3), (10), and (11), we obtain

$$\begin{array}{ccc}\hfill \left[\frac{(n-1)!}{ne}\right]& =& \left[\frac{1}{n}\left(S_{n-1}+(n-1)!\sum _{k=n}^{\infty }\frac{{(-1)}^k}{k!}\right)\right]\hfill \\ & =& \left[a+\frac{b+r}{n}\right]=a+\left[\frac{b+r}{n}\right].\hfill \end{array}$$

Since $r<n-1$, $\frac{1}{e}={\sum }_{k=0}^{\infty }\frac{{(-1)}^k}{k!}$ and for an even natural number n is valid

$$0\le b=(n-1)!\sum _{k=n}^{\infty }\frac{{(-1)}^k}{k!}<1,$$

which follows

$$\left[\frac{b+r}{n}\right]=0.$$

Thus,

$$\left[\frac{(n-1)!}{ne}\right]=a.$$

(12)

Based on equations (11) and (12), we obtain

$$\left[\frac{(n-1)!}{e}\right]-n\left[\frac{(n-1)!}{ne}\right]=r<n-1,$$

which completes the proof. □

In addition to Kurepa’s hypothesis equivalents given on the basis of the properties of integer sequences, (3) and (5) in [9] (sequence A002467 in [51]) and [41] (pg. 10) (sequences A052169, A051398, A051403, and A002720 in [51]) are listed equivalently, using the five well-known integer sequences. In addition to these seven sequences, we will now list two more well-known integer sequences.

The integer sequence ${\left\{a_n\right\}}_{n=0}^{\infty }$ (sequence A000296 in [51]) is defined as follows:

$$a_n:={(-1)}^n+\sum _{k=0}^{n-1}{(-1)}^{n+k+1}{B}_k \mathrm{with} a_0:=1.$$

The integer sequence ${\left\{b_n\right\}}_{n=1}^{\infty }$ (sequence A138378 in [51]) denotes the number of embedded coalitions in an n-person game [52].

Lemma 2. 

Let $p>3$ be a prime number. Then:

$$\begin{array}{ccc}\hfill !p& \equiv & a_{p-1}(\mathrm{mod} p),\hfill \\ \hfill !p& \equiv & 1-b_{p-1}(\mathrm{mod} p).\hfill \end{array}$$

Proof. 

On the basis of (6) and $B_p\equiv 2(\mathrm{mod} p)$ (see [6]) and $\left(\genfrac{}{}{0pt}{}{p-1}{k}\right)\equiv {(-1)}^k$, we have proof of the first equivalence. The proof of the second equivalence follows from the basis (6) and [52] (Th. 1). □

Finally, we present a new representation of the left factorial in the following lemma:

Lemma 3. 

Let $n\in \mathbb{N}$. Then

$$!(2n+1)=1+\frac{1}{2}\sum _{k=1}^n\frac{(2k+1)!}{k}.$$

Proof. 

We present our proof through an induction on n. The statement for $n=1$ is clearly true. Let $m\in \mathbb{N}$ be given and suppose that the statement is true for $n=m$:

$$\begin{array}{ccc}\hfill !(2m+3)& =& !(2m+1)+(2m+1)!+(2m+2)!\hfill \\ & =& 1+{\displaystyle \frac{1}{2}}\sum _{k=1}^m\frac{(2k+1)!}{k}+(2m+1)!(2m+3) (\mathrm{by}\mathrm{induction}\mathrm{hypothesis})\hfill \\ & =& 1+{\displaystyle \frac{1}{2}}\sum _{k=1}^m\frac{(2k+1)!}{k}+{\displaystyle \frac{(2m+3)!}{2(m+1)}}\hfill \\ & =& 1+{\displaystyle \frac{1}{2}}\sum _{k=1}^{m+1}\frac{(2k+1)!}{k}.\hfill \end{array}$$

Thus, the statement holds for $n=m+1$, and the proof of the induction step is complete. □

Let us define the integer sequence ${\left\{c_n\right\}}_{n=1}^{\infty }$ as follows:

$$c_1=1, c_n=c_{n-1}+\frac{(2n-1)!}{2n-2}.$$

(13)

For example, the first few terms of this sequence are $1,4,34,874,\dots .$

Corollary 1. 

For the integer sequence ${\left\{c_n\right\}}_{n=1}^{\infty }$ defined by (13), the following identity holds:

$$!(2n+1)=c_{n+1} (n\in \mathbb{N}).$$

Proof. 

It follows from Lemma 3. □

2.2. Some Remarks on the Assumption That Kurepa’s Hypothesis Is Not Correct

Theorem 3. 

Let prime number $p>3$ be the smallest number, for which it holds

$$!p\equiv 0(\mathrm{mod} p).$$

(14)

Then, exist the natural numbers $a\in \mathbb{N}$ and odd numbers $b,c\in \mathbb{N}$, for which the Diophantine equation is valid:

$$b^2+{(2a+c)}^2={(2a(p-1)-c)}^2+{(2a+b)}^2.$$

(15)

Proof. 

The proof is simple and rests upon the property of the derangement numbers (3).

Let p, $p>3$, be the smallest prime number for which (14) is valid. Then,

$$!(p-1)\not\equiv 0(\mathrm{mod} p-1),$$

and using (2), we obtain

$$(\exists a\in \mathbb{N})(a(p-1)<S_{p-2}<(a+1)(p-1)).$$

Relation (4) produces

$$a{(p-1)}^2+1<S_{p-1}<(a+1){(p-1)}^2+1.$$

(16)

From relations (14), (2), and (16), it follows that $b,c\in \mathbb{N}$ exists and

$$a{(p-1)}^2+b=S_{p-1}=pc.$$

(17)

It follows

$$a{p}^2-(2a+c)p+a+b=0.$$

(18)

Using (17) and (4), we have

$$(p-1)S_{p-2}=p(c-1)+p-1,$$

which implies

$$p-1\left|p\right(c-1),$$

i.e.,

$$p-1|c-1.$$

(19)

Hence,

$$(\exists \gamma \in \mathbb{N}), c=(p-1)\gamma +1.$$

Thus, c is an odd number.

Analogously, using (17), we have

$$a{(p-1)}^2=c(p-1)+(c-1)-(b-1).$$

It follows, by (19), $p-1|b-1$ and

$$b=(p-1)\beta +1 \mathrm{for} \mathrm{some} \beta \in \mathbb{N}.$$

It is not difficult to show that it is:

$$p-1<b<{(p-1)}^2.$$

Diophantine equation (15) and equation (18) are equivalent, which completes the proof. □

Corollary 2. 

If the solutions of the quadratic Equation (18) denote as $p_1\in \mathbb{N}$ and $p_2\in \mathbb{N}$, then coefficient a in (18) is an odd natural number and exists the odd natural numbers $b_1$ and $c_1$, such that:

$$p^2-(c_1+2)p+b_1+1=0.$$

Proof. 

By Vieta’s formulas, we have $a|b$ and $a|c$, i.e., $b=a{b}_1$ and $c=a{c}_1$, ($b_1,c_1\in \mathbb{N}$), respectively. □

Remark 1. 

Let the notation of the Corollary 2 hold. If $p_1\notin \mathbb{N}$ and $p_2\notin \mathbb{N}$, then Kurepa’s hypothesis is true.

2.3. Notes on Derangement Numbers

Theorem 4. 

For $n\in \mathbb{N}$ and arbitrary $s\in {\mathbb{N}}_0$, it holds

$$\begin{array}{l}{\displaystyle S_{n-1}+\sum _{k=0}^{2s+\frac{1+{(-1)}^n}{2}}{(-1)}^{k+1-\frac{1+{(-1)}^n}{2}}\prod _{j=0}^k\frac{1}{n+j}<}\\ <\frac{(n-1)!}{e}\hfill \\ <S_{n-1}+\sum _{k=0}^{2s-1+\frac{1+{(-1)}^n}{2}}{(-1)}^{k+1-\frac{1+{(-1)}^n}{2}}\prod _{j=0}^k\frac{1}{n+j},\hfill \end{array}$$

where, for $s=0$, the sum ${\sum }_{k=0}^{-1}=0$.

Proof. 

The well-known statement (10) produces

$$S_{n-1}-\frac{1}{n}<\frac{(n-1)!}{e}<S_{n-1}.$$

Analogously,

$$S_{n+1}-\frac{1}{n+2}<\frac{(n+1)!}{e}<S_{n+1}.$$

Using relation (3), we obtain

$$S_{n-1}-\frac{1}{n}+\frac{1}{n(n+1)}-\frac{1}{n(n+1)(n+2)}<\frac{(n-1)!}{e}<S_{n-1}-\frac{1}{n}+\frac{1}{n(n+1)}.$$

Through an induction for $s\in {\mathbb{N}}_0$ inequalities $<\frac{(n+2s-1)!}{e}<$, we have proof of our theorem for odd n. Similarly, by the procedure, we prove the assertion for n even number. □

Corollary 3. 

For $n\in \mathbb{N}$, it holds

$$\begin{array}{ccc}\hfill S_n& =& \frac{n!}{e}+{(-1)}^{n+1}\sum _{k=0}^{\infty }{(-1)}^{k+1}\prod _{j=0}^k\frac{1}{n+1+j}\hfill \\ & =& \frac{n!}{e}+{(-1)}^{n+1}n!\sum _{k=0}^{\infty }\frac{{(-1)}^{k+1}}{(n+k+1)!}\hfill \\ & =& \frac{\mathsf{\Gamma }(n+1,-1)}{e},\hfill \end{array}$$

where $\mathsf{\Gamma }(z,a)$ is the incomplete gamma function defined by (see [53] (Equation (79), pg. 11))

$$\mathsf{\Gamma }(z,a)={\int }_0^a{e}^{-t}{t}^{z-1}dt (\Re \left(z\right)>0;|arg\left(a\right)|<\pi ).$$

The last equation is well-known.

Remark 2. 

In [19], the authors showed that Kurepa’s hypothesis is valid for $p<2^{40}$. According to (2), there is a sequence of natural numbers ${\left\{{\alpha }_n\right\}}_{n=4}^{2^{40}}$ such that

$${\alpha }_n(n+1)<S_n<({\alpha }_n+1)(n+1).$$

Then, we define the sequence ${\left\{{\alpha }_n\right\}}_{n=4}^{\infty }$ as follows:

$${\alpha }_n:=\left[\frac{S_n}{n+1}\right].$$

We have

$${\alpha }_n\in \{1,7,37,231,1648,13349,121360,1223714,13554987,163628066,\dots \}.$$

The sequence of natural numbers ${\left\{{\alpha }_n\right\}}_{n=4}^{\infty }$ has not been defined so far according to [51]. It is not difficult to show that it is

$${\alpha }_n:=\left[\frac{n!}{(n+1)e}\right] (n<2^{40}).$$

Remark 3. 

For $n>1$ odd natural number, the multiple application of Formula (4) provides the following result:

$$S_{n-1}\equiv {(-1)}^{k}k!·S_{n-(k+1)}+!k(\mathrm{mod} n) (k=1,2,\dots ,n-1).$$

3. Conclusions

The hypothesis for the left factorial given by Professor Kurepa is a long-standing open problem. Numerous attempts to solve this problem have not brought us closer to answering the question of whether the hypothesis is correct or not. Thus, any exploration of the concepts associated with this hypothesis may lead to its resolution. We have proposed several new facts concerning the hypothesis for the left factorial, which may suggest new research directions for this open problem. So far, neither continued fractions nor quadratic equations have been used to solve this problem. Formulated hypothesis equivalences and proposed congruence’s for the left factorial, as well as a newly defined sequence can contribute to the final solution of the problem, either by proving the hypothesis or by finding a counterexample. Further research will be related to the search for a more efficient way to calculate the left factorial and solve quadratic equations based on the properties of derangement numbers listed in this paper.