Searching for a counterexample to Kurepa’s conjecture in average polynomial time

Download files
Access & Terms of Use
open access
Copyright: Rajkumar, Ramanan
Abstract
The left factorial of n is defined to be 0! + 1! + ··· + (n − 1)! and is denoted by !n. Kurepa conjectured that !n is not divisible by n for n > 2 and showed that it was sufficient to check the conjecture for odd primes p. We provide a survey of articles written on the search for a counterexample to Kurepa’s conjecture and analyse the complexity of the algorithms used. These algorithms are all linear in p; that is, exponential in logp. We develop the first known algorithm whose complexity is polynomial in logp when averaged over primes.
Persistent link to this record
Link to Publisher Version
Additional Link
Author(s)
Rajkumar, Ramanan
Supervisor(s)
Harvey, David
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2019
Resource Type
Thesis
Degree Type
Masters Thesis
UNSW Faculty
Files
download public version.pdf 949.92 KB Adobe Portable Document Format
Related dataset(s)