2016/04/30 by Sajed Haque, Jeffrey Shallit, Haque, Sajed +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Coding theory and cryptography #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1605.00092
openalex publication_date 2016/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The discriminator of an integer sequence s = (s(i))i >=0, introduced by Arnold, Benkoski, and McCabe in 1985, is the map Ds(n) that sends n >= 1 to the least positive integer m such that the n numbers s(0), s(1), ..., s(n-1) are pairwise incongruent modulo m. In this note we consider the discriminators of a certain class of sequences, the k-regular sequences. We compute the discriminators of two such sequences, the so-called "evil" and "odious" numbers, and show they are 2-regular. We also give an example of a k-regular sequence whose discriminator is not k-regular. Finally, we examine sequences that are their own discriminators, and count the number of length-n finite sequences with this property.