How many digits across all multiples of 1829?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

How many digits across all multiples of 1829?

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ISL 2022 N5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1593 posts

#1 h Jul 9, 2023, 4:41 AM • 1 Y

Y by GeoKing

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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1593 posts

#2 h Jul 9, 2023, 4:42 AM • 5 Y

Y by hdnlz, bhan2025, Kingsbane2139, BR1F1SZ, wizixez

Solution

This post has been edited 1 time. Last edited by MarkBcc168, Aug 2, 2024, 9:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

63 posts

jrsbr

#3 h Jul 9, 2023, 2:39 PM

Y by

I found a solution for this that finds a $T$ such that all values of $d_i(T)$ are equal. From this we find what the problem asks for.

Let $n=1829$ . We first define $d_{i,j}(T)$ to be the amount of times the digit $i$ appears in the multiples of $n$ until $T$ , in the $j$ -th position (from right to left). First, we note that $d_{i,j}(n(10^j+l))-d_{i,j}(nl)$ does not depend on the value of $i$ , since the multiples of $n$ between $n(10^j+l)$ and $nl$ generate a complete residue system modulo $10^l$ .
Also, note that $d_{i,j}(0)=0$ , and therefore, by taking $l=0,10^j,2\cdot10^j,\dots$ , we must have that $d_{i,j}(nv10^j)$ does not depend on the value of $i$ . See that this directly implies that $d_{i,j'}(nv10^j)$ does not depend on the value of $i$ , for any $j'\leq j$ .

Now we take $T=10^k(10^m-1)$ , where $k>\varphi(n)$ and $n\mid10^m-1$ . We'll prove that $d_1(T)=d_2(T)=\dots=d_9(T)$ .
First, notice that
$d_i(T)=\sum_{1\leq j\leq m+k}d_{i,j}(T)=\sum_{1\leq j\leq k}d_{i,j}(T)+\sum_{k+1\leq j\leq m+k}d_{i,j}(T).$ See that the first summation does no depend on the value of $i$ , since $10^k\mid T$ .
Now, for each multiple of $n$ with a certain digit $i$ in the $a$ -th position, we can swap this digit with the digit in the $b$ -th position when $\varphi(n)\mid a-b$ and keep the divisibility. Thus, we can make a bijection between the multiples of $n$ up until $T$ with $i$ in the $a$ -th position, where $a>k$ , with the multiples of $n$ until $T$ with $i$ in some position $b$ , where $b<k$ . Since we know that $d_{i,b}(T)$ does not depend on $i$ , we conclude that $d_{i,a}(T)$ also does not depend on the value of $i$ .

This implies that any of the summations depend on the value of $i$ , and thus our result is proven. To finish the problem, we just need to take $T-1$ , since $d_9(T)$ will be smaller than the rest, and we're done. $\blacksquare$

This post has been edited 1 time. Last edited by jrsbr, Jul 9, 2023, 2:44 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

63 posts

jrsbr

#4 h Jul 9, 2023, 2:44 PM • 1 Y

Y by Phorphyrion

Also, why $1829$ ? Any number that satisfies $(10,n)=1$ would have done the trick. Why? Why? Why?

This post has been edited 1 time. Last edited by jrsbr, Jul 9, 2023, 2:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1593 posts

#5 h Jul 9, 2023, 3:19 PM • 4 Y

Y by khina, hdnlz, Tellocan, sabkx

It's the year that the famous Norwegian mathematician, Niels Henrik Abel died.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Complete_quadrilateral

144 posts

Complete_quadrilateral

#6 h Jul 10, 2023, 7:48 AM

Y by

MarkBcc168 wrote:

Thus, for each $k$ , the $k$ -th digits have the same distribution as the unit digit. However, the sequence of unit digits is periodic with a period $10$ , so there are exactly two possible values. This implies that the total distribution of all digits must have two possible values, done.

What if those two values aren't distinct? It is easily fixable tho.

This post has been edited 1 time. Last edited by Complete_quadrilateral, Jul 10, 2023, 7:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7305 posts

DottedCaculator

#7 h Jul 20, 2023, 10:17 AM • 2 Y

Y by centslordm, wizixez

Note that the digits of $1829N$ and $1829cN$ are the same for $c=\frac{10^n}{10^n-1}$ , and $1829cN$ has the same distribution of digits in each position by cyclic symmetry since $1829cN$ and $1829cN10^k$ form the same residues modulo $10^n-1$ . The units digit of $1829N$ have exactly two distinct frequencies, so there are exactly two distinct numbers in $d_i(T)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1665 posts

awesomeming327.

#8 h Aug 4, 2023, 5:26 PM • 1 Y

Y by milky-way-galaxy

Let $k$ be one of the infinitely many numbers such that $1829\mid 10^k-1$ and let $T=10^k-1$ .

We suppose that all numbers have leading zeroes so that there are exactly $k$ digits. Consider one number divisible by $1829$ , and we will cyclically shift it: $\overline{a_1\dots a_{k}}$ . Let this number be also written as $10a_0+a_k\equiv 0\pmod {1829}$ , and we will show that $10^{k-1}a_k+a_0\equiv 0\pmod {1829}$ . Indeed, note that
$10(10^{k-1}a_k+a_0)=10a_0+a_k+a_k(10^k-1)\equiv 0\pmod {1829}$ so our claim is true. If any number is divisible by $1829$ , then so are all of its cyclic shifts. Therefore, if $f_1,f_2,\dots, f_9$ are the number of times digits $1,2,\dots,9$ appear as a units digit of some multiple of $1829$ with $k$ digits, then $d_i(T)=kf_1$ , so it suffices to prove the same thing for $f_1,\dots,f_9$ , which is trivial by $\pmod {10}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

873 posts

#9 h May 15, 2024, 11:05 PM

Y by

Choose $10^k$ such that $1829|10^k-1$ then, $1829|\overline{a_1a_2\dots a_k}\Rightarrow 1829|\overline{a_{k}a_1a_2\dots a_{k-1}}$ So the occurrence of each non-zero digit in a certain position has the same frequency as that digit in the units place. However the units digit cycles with period $10$ so we are finished.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lian_the_noob12

173 posts

lian_the_noob12

#10 h Aug 2, 2024, 5:19 PM

Y by

DottedCaculator wrote:

Note that the digits of $1829N$ and $1829cN$ are the same for $c=\frac{10^n}{10^n-1}$ , and $1829cN$ has the same distribution of digits in each position by cyclic symmetry since $1829cN$ and $1829cN10^k$ form the same residues modulo $10^n-1$ . The units digit of $1829N$ have exactly two distinct frequencies, so there are exactly two distinct numbers in $d_i(T)$ .

If $c=\frac{10^n}{10^{n}-1}$ then $1829cN$ will not be a integer for many $N$ so how can this be a multiple of $1829?$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lian_the_noob12

173 posts

lian_the_noob12

#11 h Aug 2, 2024, 5:22 PM

Y by

MarkBcc168 wrote:

Solution

I didn't understand what you meant by these -

"Thus, for each $k$ , the $k$ -th digits have the same distribution as the unit digit. However, the sequence of unit digits is periodic with a period $10$ , so there are exactly two possible values. This implies that the total distribution of all digits must have two possible values, done"

Question told all of the multiples from $1$ to $T$ so we have to consider $1829,3658,5487,...$ but it seems like all of the solutions just considers the multiples having $k$ digits such that $1829|10^{k} -1$ Please help me to understand

This post has been edited 1 time. Last edited by lian_the_noob12, Aug 2, 2024, 5:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1593 posts

#12 h Aug 2, 2024, 9:37 PM

Y by

For example, if $1829$ is replaced with $37$ , then all multiple of $37$ up to $999$ is

Take one entry, say 148. Then, their cyclic rotations are 481 and 814; both are in the table. The cyclic rotation argument implies that the first, second, and third columns in this table have the same set of digits (in particular, all columns have 2 of $\{0,3,6\}$ and 3 of $\{1,2,4,5,7,8,9\}$ ). It then suffices to only consider the set of unit digits, which is periodic, so it has only two distinct numbers.

This post has been edited 1 time. Last edited by MarkBcc168, Aug 2, 2024, 9:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lian_the_noob12

173 posts

lian_the_noob12

#13 h Aug 3, 2024, 11:38 AM

Y by

MarkBcc168 wrote:

For example, if $1829$ is replaced with $37$ , then all multiple of $37$ up to $999$ is

Take one entry, say 148. Then, their cyclic rotations are 481 and 814; both are in the table. The cyclic rotation argument implies that the first, second, and third columns in this table have the same set of digits (in particular, all columns have 2 of $\{0,3,6\}$ and 3 of $\{1,2,4,5,7,8,9\}$ ). It then suffices to only consider the set of unit digits, which is periodic, so it has only two distinct numbers.

But how did you get idea of it? The number was $1829$ it would impossible to try it like you tried with $37$
And why you got idea of trying $37$ instead of $1829$ How did you know their multiples before $T=10^t$ will be cyclic? It seems magical two me, How a people can find such an idea? :/

And how did you sure for $1829$ that there are exactly two distinct values for unit digits? What if there is exactly one distinct number like unit digits $74185296307418529630$

This post has been edited 3 times. Last edited by lian_the_noob12, Aug 3, 2024, 11:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1720 posts

OronSH

#14 h Mar 17, 2025, 5:22 PM • 1 Y

Y by megarnie

Pick $T=10^{n\cdot\varphi(1829)}-1$ . The number of multiples of $1829$ from $1$ to $T$ must be $1\pmod{10}$ so the units digit is $9$ exactly one more time than it is any of the other digits.

However observe that $1829\mid\overline{abc\dots z}\implies 1829\mid\overline{abc\dots z0}\implies 1829\mid\overline{bc\dots za}$ , so by cyclic shifting the multiples of $1829$ that are $\le T$ we get the same set. Thus the digits in any other position have the same occurrences as in the units digit, so $d_1(T)=\dots=d_8(T)\ne d_9(T)$ as desired.

This post has been edited 1 time. Last edited by OronSH, Mar 17, 2025, 5:22 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a