Ponder This Challenge - December 2024 - Counting numbers with specific digits

Denote by $\omega_d(n)$ the size of the set of all natural numbers between $1$ and $n$ that have the digit $d$ in their usual decimal representation. For example, $\omega_1(1456)=728$ and $\omega_7(1456)=352$.

We see that for $n=1456$, we have $\frac{\omega_1(n)}{n} = \frac{1}{2}$, i.e., exactly 50% of the numbers up to 1456 contain the digit 1. For $d=7$, we have $\frac{\omega_7(n)}{n} = \frac{22}{91}$.

Your goal: For each $d$ between 1 and 9, find the maximum value of $n$ for which $\frac{\omega_d(n)}{n} = \frac{1}{2}$.

An optional goal: Find a simple formula $f(d)$ giving those maximum values for as many values of $d$ as possible.

A bonus "*" will be given for finding the maximum value of $n$ for which $\frac{\omega_1(n)}{n} = \frac{3}{4}$ (i.e., only solve the case $d=1$. but for $\frac{3}{4}$ this time).

Solution

• Click here to view the solution

  December 2024 Solution:

  The solution for 1/2 is [1062880, 2125762, 3188644, 4251526, 5314408, 6377290, 17006110, 18068992, 19131874].

  The solution for 3/4 is 10167463313312

  A simple formula giving the solutions is $2\left(d\cdot9^{k}-1\right)$ where $k=6$; this gives the correct values for $d=1,2,3,4,5,6$ (and for $d=7,8,9$ gives values which result in $\frac{\omega_d(n)}{n} = \frac{1}{2}$ but are not maximal). Other (non-maximal) values resulting in 1/2 also corresponds to this formula for other values of $k$. To solve the problems efficiently, it is useful to have

  1. An efficient algorithm for computing $\omega_d(n)$.
  2. An upper bound on the value of $n$ for which $\frac{\omega_d(n)}{n} = \frac{1}{2}$ is possible.

  For a simple recursive algorithm for $\omega_d(n)$, first note that any $n$ can be written as $n=q\cdot 10^t+r$ where $r<10^t$, i.e. we split $n$ by taking its most significant digit $q$ and the rest of the number $r$.

  For example, if $n=5627$ then $n=5\cdot10^3+627$ so in this case, $q=5, t=3$ and $r=627$.

  Now note that we have the relation $\omega\_{d}\left(n\right)=\begin{cases} \left(r+1\right)+\omega\_{d}\left(n-\left(r+1\right)\right) & q=d\\ \omega\_{d}\left(r\right)+\omega\_{d}\left(n-\left(r+1\right)\right) & q\ne d \end{cases}$

  Using this relation, computing $\omega\_{d}\left(n\right)$ is immediate even for very large values of $n$.

  For an upper bound, first note that computing $\omega\_d(10^m)$ is very easy: The total number of $m$-length strings of digits is $10^m$, and the number of such strings not containing $d$ is $9^m$, so up to and not including $10^m$ we have $10^m-9^m$ such strings. If $d=1$ we also count $10^m$ itself, so all in all $\omega\_d(10^m)=10^m-9^m+\delta\_{1d}$ with $\delta$ being the usual Kronecker's delta.

  This upper bound shows that as $n$ tends to infinity, the proportion $\frac{\omega\_d(n)}{n}$ tends to 1. Combined with a quick way to compute $\omega\_d(n)$ for specific numbers and using smart search methods (even binary search is efficient here, given a better understanding of the behaviour of $\omega\_d(n)$) this solves both the standard problem and the bonus.

  We do not know of an analytical way to solve the problem. Some of you suggested beautiful approaches based in one way or another on the formula $2\left(d\cdot9^{k}-1\right)$ described above which generalizes to $A\cdot \left(d\cdot9^{k}-1\right)$ when we want to find the proportion $\frac{A-1}{A}$; e.g. for $\frac{3}{4}$ choosing $A=4$ we obtain the formula $4\cdot \left(d\cdot9^{k}-1\right)$ which correctly yields 10167463313312 for $k=13, d=1$ However, as the counterexamples for the formula for $A=2$ and $d=7,8,9$ show, it does not always work.

Solvers

• Alex Fleischer (2/12/2024 5:59 PM IDT)
• *Lazar Ilic (3/12/2024 10:46 AM IDT)
• *Lorenz Reichel (3/12/2024 11:10 AM IDT)
• *Serge Batalov (3/12/2024 12:30 PM IDT)
• *Daniel Chong Jyh Tar (3/12/2024 12:34 PM IDT)
• *Alper Halbutogullari (3/12/2024 1:50 PM IDT)
• *Bertram Felgenhauer (3/12/2024 2:24 PM IDT)
• Paul Revenant (3/12/2024 2:40 PM IDT)
• *Yi Jiang (3/12/2024 3:12 PM IDT)
• *Hugo Pfoertner (3/12/2024 4:04 PM IDT)
• *Dieter Beckerle (3/12/2024 8:06 PM IDT)
• *Dan Dima (3/12/2024 9:47 PM IDT)
• Nadir S. (3/12/2024 11:39 PM IDT)
• *Yan-Wu He (4/12/2024 2:01 AM IDT)
• Victor Chang (4/12/2024 6:04 AM IDT)
• Loukas Sidiropoulos (4/12/2024 7:23 AM IDT)
• *Guangxi Liu (4/12/2024 8:36 AM IDT)
• *Sanandan Swaminathan (4/12/2024 9:21 AM IDT)
• Blaine Hill (4/12/2024 11:44 AM IDT)
• Evert van Dijken (4/12/2024 12:31 PM IDT)
• *Michael Liepelt (4/12/2024 12:58 PM IDT)
• *Gary M. Gerken (4/12/2024 3:38 PM IDT)
• *Michael Vahle (4/12/2024 4:22 PM IDT)
• *Sam Fischer (4/12/2024 4:33 PM IDT)
• *Ashfaque Shaikh (4/12/2024 5:41 PM IDT)
• Jeffrey Harris (4/12/2024 5:59 PM IDT)
• *Hakan Summakoğlu (4/12/2024 6:49 PM IDT)
• *Karl-Heinz Hofmann (4/12/2024 7:45 PM IDT)
• *King Pig (5/12/2024 1:56 AM IDT)
• William Han (5/12/2024 2:54 AM IDT)
• *Arthur Vause (5/12/2024 11:10 AM IDT)
• *Juergen Koehl (5/12/2024 11:58 AM IDT)
• *Vladimir Volevich (5/12/2024 12:50 PM IDT)
• *Latchezar Christov (5/12/2024 3:18 PM IDT)
• Cameron Ritson (5/12/2024 11:25 PM IDT)
• Mark J. Murphy (6/12/2024 12:13 AM IDT)
• *John Spurgeon (6/12/2024 4:04 AM IDT)
• Thomas Egense (6/12/2024 12:04 PM IDT)
• Fabio Michele Negroni (6/12/2024 7:57 PM IDT)
• Noam Zaks (6/12/2024 9:34 PM IDT)
• Tamir Ganor & Shouky Dan (7/12/2024 12:48 PM IDT)
• Janko Sustersic (7/12/2024 3:49 PM IDT)
• Ganghun (Jason) Kim (7/12/2024 6:58 PM IDT)
• *Amos Guler (7/12/2024 9:17 PM IDT)
• Reiner Martin (8/12/2024 2:29 AM IDT)
• *Julian Ma (8/12/2024 2:56 AM IDT)
• *Abdul Isik (8/12/2024 8:20 AM IDT)
• *Sanjay Rao (8/12/2024 11:23 AM IDT)
• *Adrian Neacsu (9/12/2024 12:44 AM IDT)
• Gyozo Nagy (9/12/2024 9:11 AM IDT)
• *Soonho You (9/12/2024 9:18 AM IDT)
• *Bart De Vylder (9/12/2024 11:34 AM IDT)
• *Robin Guilliou (9/12/2024 3:33 PM IDT)
• *Pål Hermunn Johansen (10/12/2024 12:24 AM IDT)
• Shirish Chinchalkar (10/12/2024 2:24 AM IDT)
• *Stéphane Higueret (10/12/2024 10:28 AM IDT)
• *Paul Lupascu (10/12/2024 11:16 AM IDT)
• *Sri Mallikarjun J (10/12/2024 3:56 PM IDT)
• *Ankit Aggarwal (10/12/2024 4:52 PM IDT)
• *Nyles Heise (10/12/2024 8:35 PM IDT)
• Dominik Reichl (10/12/2024 9:15 PM IDT)
• *Daniel Bitin (10/12/2024 11:59 PM IDT)
• *Guglielmo Sanchini (11/12/2024 4:52 PM IDT)
• John Tromp (11/12/2024 6:05 PM IDT)
• Benjamin Cha (11/12/2024 8:59 PM IDT)
• *Kang Jin Cho (12/12/2024 5:19 PM IDT)
• *Franciraldo Cavalcante (12/12/2024 10:29 PM IDT)
• *Abhinav Bana (13/12/2024 6:17 AM IDT)
• Suyeong Hahn (14/12/2024 4:39 PM IDT)
• *Seth Cohen (15/12/2024 3:48 AM IDT)
• *David Dunkley (15/12/2024 4:48 AM IDT)
• *Andreas Stiller (16/12/2024 6:50 PM IDT)
• Rudy Cortembert (16/12/2024 11:32 PM IDT)
• Terry Lee (17/12/2024 3:47 AM IDT)
• *Piyush Agrawal (17/12/2024 5:34 PM IDT)
• *Fakih Karademir (18/12/2024 9:02 PM IDT)
• *Tim Walters (19/12/2024 8:51 PM IDT)
• Marcelo De Barros (20/12/2024 1:52 AM IDT)
• *Matt Cristina (21/12/2024 3:03 AM IDT)
• Stefan Wirth (21/12/2024 4:56 PM IDT)
• *Karl D’Souza (21/12/2024 5:53 PM IDT)
• Mohit Garg (21/12/2024 6:18 PM IDT)
• Clive Tong (21/12/2024 10:47 PM IDT)
• *Andrea Andenna (22/12/2024 10:30 AM IDT)
• *Chris Shannon (25/12/2024 7:12 AM IDT)
• *Marco Bellocchi (27/12/2024 2:03 AM IDT)
• Evan Semet (27/12/2024 4:13 AM IDT)
• *Ido Meisner (28/12/2024 1:11 AM IDT)
• *Kyle Askine (28/12/2024 7:08 AM IDT)
• *David Greer (28/12/2024 6:22 PM IDT)
• *Alex Izvalov (28/12/2024 8:44 PM IDT)
• *Motty Porat (29/12/2024 2:57 AM IDT)
• *Shashwath Murthy (29/12/2024 9:55 AM IDT)
• *Jared Kittleson (29/12/2024 9:30 PM IDT)
• *Harald Bögeholz (31/12/2024 5:10 PM IDT)
• *Stephen Ebert (31/12/2024 9:42 PM IDT)
• *Alex Newman & Eric Niblock (31/12/2024 10:05 PM IDT)
• *Dezhi Zhao (1/1/2025 4:23 AM IDT)
• *Oscar Volpatti (1/1/2025 12:18 PM IDT)
• *Erik Wünstel (1/1/2025 6:10 PM IDT)
• Radu-Alexandru Todor (2/1/2025 1:36 AM IDT)
• *Li Li (2/1/2025 8:43 PM IDT)
• *Karl Mahlburg (4/1/2025 10:40 PM IDT)