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

dc.contributor.advisor Harvey, David en_US
dc.contributor.author Rajkumar, Ramanan en_US
dc.date.accessioned 2022-03-23T10:09:47Z
dc.date.available 2022-03-23T10:09:47Z
dc.date.issued 2019 en_US
dc.description.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. en_US
dc.identifier.uri http://hdl.handle.net/1959.4/61941
dc.language English
dc.language.iso EN en_US
dc.publisher UNSW, Sydney en_US
dc.rights CC BY-NC-ND 3.0 en_US
dc.rights.uri https://creativecommons.org/licenses/by-nc-nd/3.0/au/ en_US
dc.subject.other Complexity en_US
dc.subject.other Kurepa's conjecture en_US
dc.subject.other Accumulating remainder tree en_US
dc.title Searching for a counterexample to Kurepa’s conjecture in average polynomial time en_US
dc.type Thesis en_US
dcterms.accessRights open access
dcterms.rightsHolder Rajkumar, Ramanan
dspace.entity.type Publication en_US
unsw.accessRights.uri https://purl.org/coar/access_right/c_abf2
unsw.identifier.doi https://doi.org/10.26190/unsworks/21191
unsw.relation.faculty Science
unsw.relation.originalPublicationAffiliation Rajkumar, Ramanan, Mathematics & Statistics, Faculty of Science, UNSW en_US
unsw.relation.originalPublicationAffiliation Harvey, David, Mathematics & Statistics, Faculty of Science, UNSW en_US
unsw.relation.school School of Mathematics & Statistics *
unsw.thesis.degreetype Masters Thesis en_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
public version.pdf
Size:
949.92 KB
Format:
application/pdf
Description:
Resource type