Bounds for sets of remainders
Omkar Baraskar, Ingrid Vukusic · 2025
Read Bounds for sets of remainders by Omkar Baraskar, Ingrid Vukusic (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20853.txt.
Introduction
Omkar Baraskar and Ingrid Vukusic count remainders in twenty twenty-five. For a number n, look at its remainders when divided by each smaller k up to half of n. Count how many distinct remainders appear. That simple sequence is catalogued in the OEIS, yet it had barely been studied.
The authors prove the count grows linearly with n, with an explicit constant. The error term shrinks by a doubly logarithmic factor. They then study jumps between consecutive counts. The count can rise by at most one, yet it can fall by arbitrarily large amounts. Those falls are still bounded by a slow-growing function. Iterated remainder sets, tied to Pierce expansions, get size bounds as well. Readers meet a humble sequence with surprising structure.
Catalog record
| CREATOR | Omkar Baraskar, Ingrid Vukusic |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20853
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bounds for sets of remainders Thanks: Research of the second author supported by NSERC grant 2024-03725. Omkar Baraskar, Ingrid Vukusic Abstract . Let s ( n ) s(n) be the number of different remainders n mod k n\bmod k , where 1 ≤ k ≤ ⌊ n / 2 ⌋ 1\leq k\leq\lfloor n/2\rfloor . This rather natural sequence is sequence A283190 in the OEIS and while some basic facts are known, it seems that surprisingly it has barely been studied. First, we prove that s ( n ) = c ⋅ n + O ( n / ( log n log log n ) ) s(n)=c\cdot n+O(n/(\log n\log\log n)) , where c c is an explicit constant. Then we focus on differences between consecutive terms s ( n ) s(n) and s ( n + 1 ) s(n+1) . It turns out that the value can always increase by at most one, but there exist arbitrarily large decreases. We show that the differences are bounded by O ( log log n ) O(\log\log n) . Finally, we consider “iterated remainder sets”. These are related to a problem arising from Pierce expansions, and we prove bounds for the size of these sets as well. 2020 Mathematics Subject Classification 11N37, 11A07, 11B83 1. Introduction Let us fix an integer n . Then a natural question is the following: Which are the remainders r=n\bmod k ? The sum of such remainders with 1\leq k\leq n was already considered by Édouard Lucas [ 5 , p. 373] and more recently in [ 8 , 10 , 3 ] . In the present paper, we are simply interested in the number of distinct remainders. Surprisingly, it seems that this has barely been studied. If k>n , then we get r=n for all k . If \lfloor n/2\rfloor+1\leq k\leq n , then r=n-k , so in this range we simply get all the integers between 0 and \lceil n/2\rceil-1 . Therefore, the interesting cases are where 1\leq k\leq\lfloor n/2\rfloor , and we define the set S(n):=\{n\bmod k\colon k\in\{1,2,\ldots,\lfloor n/2\rfloor\}\}. Note that clearly S(n)\subseteq\{0,1,\ldots,\lfloor n/2\rfloor-1\} . Now let us define s(n):=\lvert S(n)\rvert. In other words, s(n) is the number of different values n\bmod k for 1\leq k\leq\lfloor n/2\rfloor . This is precisely sequence A283190 in the OEIS (On-Line Encyclopedia of Integer Sequences) [ 6 ] . The first few numbers of the sequence are presented in Table 1 . n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 s(n) 0 1 1 1 2 1 2 2 2 3 4 2 3 3 3 4 5 3 Table 1 . First eighteen values of s(n) . Although it seems like a very natural sequence, it was entered into the OEIS only in 2017 by Thomas Kerscher. Robert Israel then observed that s(n)/n seems to converge to approximately 0.2296 . He asked about the actual value of the constant on the StackExchange website [ 4 ] . This was answered by the user Empy2 (and added as a comment to the OEIS entry by Michael Peake): (1) \lim_{n\to\infty}\frac{s(n)}{n}=\sum_{p\in\mathbb{P}}\frac{1}{p(p+1)}\cdot\prod_{\begin{subarray}{c}q\in\mathbb{P},\\ q<p\end{subarray}}\left(1-\frac{1}{q}\right)\approx 0.2296. The answer on the StackExchange website also contains an explanation for why this is true. While the argument is relatively simple, we haven’t been able to find a rigorous proof in print. In this paper, in Section 3 , we give a proof of ( 1 ), including a bound for the error term. Then we investigate the differences between consecutive terms of s(n) . Looking at the first few values of the sequence s(n) , one sees that the values of s(n+1) compared to s(n) usually either stay the same or increase or decrease by 1 . They never seem to increase by more than 1 , but sometimes they decrease by 2 or, as it turns out, even more. In Section 4 we show that these differences can get arbitrarily large, while being double logarithmically bounded in terms of n . In Section 5 , we generalize the set S(n)=:S_{1}(n) to “iterated remainder sets” via S_{j+1}(n):=\{n\bmod{k}\colon k\in S_{j}(n)\setminus\{0\}\} for j\geq 1 . These sets are related to an older problem arising from Pierce expansions. This problem was considered in [ 9 , 2 , 1 ] , and the main question is still open: If we fix a positive integer n , choose another integer 1\leq a\leq n , and repeatedly set a:=n\bmod a , what is the largest number of steps performed before reaching a=0 ? More on this and the relation to our iterated remainder sets in Section 5 . In Section 6 we prove some bounds for these sets. Finally, in Section 7 we pose some open problems. But first of all, we present all main results in the next section. 2. Main results and some lemmas Let us define the constant from ( 1 ), namely c:=\sum_{p}\frac{1}{p(p+1)}\cdot\prod_{\begin{subarray}{c}p^{\prime}<p\end{subarray}}\left(1-\frac{1}{p^{\prime}}\right)\approx 0.2296. In Section 3 we will prove the following asymptotics for s(n) . Theorem 1 . We have s(n)=c\cdot n+O\left(\frac{n}{\log n\log\log n}\right). In particular, \lim_{n\to\infty}\frac{s(n)}{n}=c. We do not believe that our bound for the error term is sharp. Numerical experiments suggest that perhaps O(n^{1/3}) might be closer to the truth; see Section 7 . In any case, we know that overall s(n) grows linearly, but due to the error term this does not give us much information on the differences s(n+1)-s(n) . As mentioned in the introduction, looking at the first few values of s(n) , it seems that the values of s(n+1) compared to s(n) usually either stay the same or increase or decrease by 1 . It turns out that they never increase by more than 1 , but sometimes they do decrease by 2 or even more. For example, s(131)=33 and s(132)=30 . The first time that the value decreases by 4 happens at n=17291 , where s(17291)=3975 and s(17292)=3971 . We have searched up to n=10^{7} and have not found a decrease by more than 4 in this range. However, it turns out that there do exist arbitrarily large decreases, and we will give a construction for such n . On the other hand, we can prove bounds on the decreases in terms of n . In Section 4 we will, in particular, prove the following results. Theorem 2 . For n\geq 1 we have s(n)-O(\log\log n)\leq s(n+1)\leq s(n)+1. Moreover, \liminf_{n\to\infty}s(n+1)-s(n)=-\infty. Now let us define the sets of iterated remainders of n inductively by \displaystyle S_{0}(n) \displaystyle:=\{1,2,\ldots,\lfloor n/2\rfloor\}\quad\text{and} \displaystyle S_{j}(n) \displaystyle:=\{n\bmod{k}\colon k\in S_{j-1}(n)\setminus\{0\}\}\quad\text{for }j\geq 1. Note that, in particular, S(n)=S_{1}(n) . Moreover, analogously to s(n) , we define s_{j}(n):=\lvert S_{j}(n)\rvert. In Section 6 , we will prove the following bounds. Theorem 3 . For j\geq 0 we have \frac{1}{(j+2)!}\leq\liminf_{n\to\infty}\frac{s_{j}(n)}{n}\leq\limsup_{n\to\infty}\frac{s_{j}(n)}{n}\leq\frac{1}{j+2}. While the bounds are clearly not sharp (for example, set j=1 and compare to Theorem 1 ), it seems that for j\geq 2 there is indeed a gap between the limit inferior and limit superior; see Section 7 . Before moving on, we state two simple lemmas. All results on s(n) will be based on the following equivalence. Lemma 1 . Let r\in\{0,1,\ldots,\lfloor n/2\rfloor-1\} . Then r\in S(n) if and