Cyclic Digits

Today we shall have a look at a neat little trick that is more commonly seen in computational contests, but occasionally makes an appearance in Olympiad problems as well.

Let $X=\overline{d_{n-1}d_{n-2}\dots d_0}_b= \sum_{i=0}^{n-1} d_ib^i$ be an integer in base- $b$ where $0 \le d_i \le b-1$ for all $0 \le i \le n-1$ , as usual. Observe that if $\rho(X)=\overline{d_{n-2}\dots d_0d_{n-1}}$ is the integer obtained by moving the first digit to the end,

$\rho(X)=bX-d_{n-1}(b^n-1)$

Hence, it is clear that $\rho(X) \equiv bX \pmod{b^n-1}$ . More generally, $\rho^k(X) \equiv b^kX \pmod{b^n-1}$ . Thus an $n-$ digit base- $b$ number modulo $b^n-1$ is naturally a circular string of digits. Multiplying by $b$ rotates the circle by one position, and a carry beyond the $n-$ th position wraps back to the first position.

Let us begin with the following classical problem.

Example 1 (IMO Shortlist 1993 N3)

Let $a,b,n$ be positive integers, $b > 1$ and $b^n-1\mid a.$ Show that the representation of the number $a$ in the base $b$ contains at least $n$ digits different from zero.

Suppose $a=\sum_{i=1}^tc_ib^{e_i}$ where $1\le c_i \le b-1$ where $t$ is the number of non-zero digits of $a$ . We wish to show that $t$ is at least $n$ , given that $a$ is a multiple of $b^n-1$ . Our goal then turns to showing that the sum of digits of $a$ is at least $n(b-1)$ , since each digit is at most $b-1$ .

Naturally, since $b^n\equiv 1 \pmod{b^n-1}$ , the first thing to try is reducing every exponent $e_i \pmod{n}$ . Replacing $e_i \equiv r_i \pmod{n}$ , we can define $S_0 =\sum_{i=1}^t c_ib^{r_i}$ which since $S_0 \equiv a \pmod{b^n-1}$ implies $S_0 \ge b^n-1$ .

But, this alone is useless. Note that a digit sitting in the $b^{n-1}-$ position contributes far more to the sum $S_0$ than a digit at the units position. We are trying to bound the number of non-zero digits — which should not depend on their positions, but our inequalities are highly position dependent.

To see what I mean, consider the example $b=10$ and $n=3$ . We want to understand multiples of $10^3-1=999$ , so reducing the powers of $10$ modulo $999$ gives

$a \equiv A+10B+100C \pmod{999}$

for positive integers $A,B,C$ . Thus, $A+10B+100C$ is a multiple of $999$ whenever $a$ is. However, $C$ is weighted 100 times as much as $A$ , and $B$ is weighted 10 times as much, so this does not tell us much about $A+B+C$ , the actual digit sum.

However, multiplication by $10$ shows that $10A+100B+C$ is a multiple of $999$ , and similarly that $100A+B+10C$ is a multiple of $999$ . Hence, each of these are at least $999$ so summing and dividing across by 111 immediately spits out the inequality $A+B+C \ge 27$ , which matches our target.

The key idea is that the contribution by a non-zero digit is not felt only from its current position but throughout all of the possible positions in the $n-$ digit number. This intuition appears time and time again in these kinds of problems.

Returning to our problem, for $0 \le j \le n-1$ , define the sums

$S_j = \sum_{i=1}^t c_ib^{e_i+j \pmod{n}}$ .

In other words, throw the digits onto a circle, and then rotate it exactly $j$ steps. Note that as we perform the rotations, any digit $c_i$ visits each of the $n$ positions exactly once. So its total contribution to $S_0+S_1+\dots S_{n-1}$ is exactly

$c_i(b^0+b^1+\dots + b^{n-1})=c_i\frac{b^n-1}{b-1}$ .

Summing across all the $t$ non-zero digits we have,

$\sum_{i=0}^{n-1}S_i = \frac{b^n-1}{b-1}\sum_{i=1}^t c_i$

which since $S_0,\dots , S_{n-1}$ are all multiples of $b^n-1$ implies

$\frac{b^n-1}{b-1}\sum_{i=1}^t c_i \ge n(b^n-1)$ so $\sum_{i=1}^t c_i \ge n(b-1)$ !

Now, this next problem might seem a bit unreasonable — especially for those who haven’t seen this trick before. So, it is best to first attempt 2025 CMIMC A5, which is basically the same problem but far less scary.

Example 2 (IMO Shortlist 2022 N5)

For each $1\leq i\leq 9$ and $T\in\mathbb N$ , define $d_i(T)$ to be the total number of times the digit $i$ appears when all the multiples of $1829$ between $1$ and $T$ inclusive are written out in base $10$ . Show that there are infinitely many $T\in\mathbb N$ such that there are precisely two distinct values among $d_1(T)$ , $d_2(T)$ , $\dots$ , $d_9(T)$ .

The idea is to pick $T=10^{k}-1$ where $\phi(1829) \mid k$ since $1829|10^k-1$ for this choice of $k$ , and write every integer multiple of 1829 upto $T$ as a $k-$ digit string, allowing leading zeros. Hence, for any multiple $\overline{a_ta_{t-1}\dots a_1}$ of 1829, it’s cyclic rotation $\overline{a_{t-1}\dots a_1a_t}$ is equivalent modulo $10^k-1$ and is hence also divisible by 1829.

Now, since 1829 is a bit of a mouthful, let us pick the smaller choice 37 instead. Why 37? Because it so happens that 37 is a factor of 999, so $T$ remains within our sights. The list of multiples of 37 up to 999 goes as follows,

037, 074, 111, 148, 185, 222, 259, 296, 333, 370, 407, 444, 481, 518, 555, 592, 629, 666, 703, 740, 777, 814, 851, 888, 925, 962, 999

We now group the multiples which are cyclic shifts of each other, while allowing for leading zeros,

037
370
703

074
740
407

148
481
841

185
851
518

259
592
925

296
962
629

and of course, 111, 222, 333, 444, 555, 666, 777, 888 and 999.

Notice that the distribution of digits in the hundreds, tens and units places are exactly identical! Hence, we only need focus on the units position.

Returning to the problem, the multiples of 1829 from 1 to our choice of $T$ have the same distribution of digits in each of the positions from $10^{t-1}$ through the units position. Hence, we only need to count the number of times each non-zero digit occurs in the units position. However, since 1829 and 10 are relatively prime, the units digit of multiples of 1829 are periodic modulo 10.

Observe that the number of multiples of 1829 from 1 to $T$ is $\frac{T}{1829} \equiv \frac{-1}{-1} \equiv 1 \pmod{10}$ , so each of the digits 0 through 8 occur $\lfloor \frac{T}{18290} \rfloor$ times while 9 occurs $\lceil \frac{T}{18290} \rceil$ times, implying that $d_1(T)=d_2(T)=\dots = d_8(T) \ne d_9(T)$ , as desired.

For the finale, we shall have a look at a problem of a more constructive flavour. The solution to this problem can seem almost magical without the underlying motivation of cyclic shifts.

Example 3 (USAMO 2013/5)

Given positive integers $m$ and $n$ , prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

Well, by now you know the drill — we would love to be able to find some integer $c$ such that the two multiples $cn$ and $cm$ are cyclic shifts of each other. Note that it suffices to deal with the case where $n$ is relatively prime to 10 and $n<m$ (confirm why!).

Consider $c$ and $k$ such that $10cm-10^k+1=cn$ . If we can find $k$ such that $cm$ has leftmost digit 1 at the $10^k-$ position, we would be done. Rearranging, $c= \frac{10^k-1}{10m-n}$ . However observe,

$99\dots 9.9=\frac{10^k-1}{10} < \frac{10^k-1}{10m-n}m < \frac{10^k-1}{9}=11\dots 1$

which implies that the leading digit is indeed at the $10^k-$ position and is 1. We now need to pick $k$ such that this choice of $c$ is an integer, which is straightforward.

Cyclic Digits

Published by Lasitha Jayasinghe

Leave a comment Cancel reply

Share this:

Related

Published by Lasitha Jayasinghe

Leave a comment Cancel reply