×

Improved algorithms for left factorial residues. (English) Zbl 1515.11123

Summary: We present improved algorithms for computing the left factorial residues \(!p=0!+1!+\dots+(p-1)!\bmod p\). We use these algorithms for the calculation of the residues \(!p\bmod p\), for all primes \(p\) up to \(2^{40}\). Our results confirm that Kurepa’s left factorial conjecture is still an open problem, as they show that there are no odd primes \(p<2^{40}\) such that \(p\) divides !\(p\). Additionally, we confirm that there are no socialist primes p with \(5<p<2^{40}\).

MSC:

11Y55 Calculation of integer sequences
11B65 Binomial coefficients; factorials; \(q\)-identities
68W30 Symbolic computation and algebraic computation

Software:

NTL; FLINT; gmp
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] V. Andrejić, On Kurepa’s left factorial conjecture, in: XIV Serbian Mathematical Congress, May 16-19, 2018, Kragujevac, Serbia, Book of abstracts, p. 96.
[2] Andrejić, V.; Tatarevic, M., Searching for a counterexample to Kurepa’s conjecture, Math. Comput., 85, 3061-3068 (2016) · Zbl 1360.11002
[3] Andrejić, V.; Tatarevic, M., On distinct residues of factorials, Publ. Inst. Math. (N.S.), 100, 101-106 (2016) · Zbl 1432.11016
[4] Bostan, A.; Gaudry, P.; Schost, E., Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput., 36, 1777-1806 (2007) · Zbl 1210.11126
[5] Costa, E.; Gerbicz, R.; Harvey, D., A search for Wilson primes, Math. Comput., 83, 3071-3091 (2014) · Zbl 1370.11003
[6] Granlund, T.; the GMP development team, GNU MP: the GNU multiple precision arithmetic library (2016), Version 6.1.2
[7] Guy, R., Unsolved Problems in Number Theory (2004), Springer-Verlag · Zbl 1058.11001
[8] Hart, W.; Johansson, F.; Pancratz, S., FLINT: fast library for number theory (2015), Version 2.5.2
[9] Harvey, D., NTT: a library for large integer arithmetic (2012), Version 0.1.2
[10] Kurepa, Đ., On the left factorial function !n, Math. Balk., 1, 147-153 (1971) · Zbl 0224.10009
[11] Rajkumar, R., Searching for a counterexample to Kurepa’s conjecture in average polynomial time (2019), School of Mathematics and Statistics, UNSW Sydney, Master’s thesis
[12] Shoup, V., NTL: a library for doing number theory (2016), Version 10.3.0
[13] Trudgian, T., There are no socialist primes less than 10^9, Integers, 14 (2014), #A63 · Zbl 1336.11009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.