2023/09/22 by Matteo Ferrari, Florian Luca, Ferrari, Matteo +3
Mathematics · Physics and Astronomy · #11B39 #11B50 #Advanced Mathematical Identities #Advanced Mathematical Theories and Applications #Analytic Number Theory Research #FOS: Mathematics #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2309.12843
openalex publication_date 2023/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The family of Shallit sequences consists of the Lucas sequences satisfying the recurrence Un+2(k)=(4k+2)Un+1(k) -Un(k), with initial values U0(k)=0 and U1(k)=1 and with k≥ 1 arbitrary. For every fixed k the integers \Un(k)\n≥ 0 are distinct, and hence for every n≥ 1 there exists a smallest integer Dk(n), called discriminator, such that U0(k),U1(k),…,Un-1(k) are pairwise incongruent modulo Dk(n). In part I it was proved that there exists a constant nk such that Dk(n) has a simple characterization for every n≥ nk. Here, we study the values not following this characterization and provide an upper bound for nk using Matveev's theorem and the Koksma-Erdos-Turán inequality. We completely determine the discriminator Dk(n) for every n≥ 1 and a set of integers k of natural density 68/75. We also correct an omission in the statement of Theorem 3 in part I.