December 2024 - 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.