Perl Weekly Challenge 126: Count Numbers

Input: $N = 15
Output: 8

Input: $N = 25
Output: 13

Let's first focus on generating numbers without a 9. It is not hard to see that \(N^{\text{th}}\) non-negative integer without a 9 can be found by converting \(N\) into base-9. This gives the following sequence:

\(N\)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	...
\(N_9\)	0	1	2	3	4	5	6	7	8	10	11	12	13	14	15	16	17	18	20	21	22	23	24	25	26	27	28	30	31	32	33	...
9-free	0	1	2	3	4	5	6	7	8	10	11	12	13	14	15	16	17	18	20	21	22	23	24	25	26	27	28	30	31	32	33	...

If we want to generate the \(N^{\text{th}}\) non-negative integer missing a digit other than 9, as a first step, we still start with convert \(N\) into base-9. Then, of the converted number, we replace the digits 0-8 with the nine digits which are allowed. So, in the case we want numbers without a 1, we convert \(N\) into base-9, then replace 1 by 2, 2 by 3, 3 by 4, etc, till we replace 8 by 9. Any 0 remains as is.

This gives the following table:

\(N\)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	...
\(N_9\)	0	1	2	3	4	5	6	7	8	10	11	12	13	14	15	16	17	18	20	21	22	23	24	25	26	27	28	30	31	32	33	...
1-free	0	2	3	4	5	6	7	8	9	20	22	23	24	25	26	27	28	29	30	32	33	34	35	36	37	38	39	40	42	43	44	...

This is sequence A052383 in the OEIS.

Note that if \(P\) is the \(N^{\text{th}}\) 1-free number, then there are \(N\) 1-free numbers between 1 and \(P\).

We don't want to calculate the \(N^{\text{th}}\) 1-free number, instead we want the reverse. The procedure described above can be simply reversed: starting from the 1-free number, we replace each of the digits 2-9 with the digits 1-8, and we interpret the resulting number as a base-9 number.

But there is one more step we need to do. While we can find the answer for a 1-free number, the input may contain a 1. Consider a number \(N\), and let \(M\) be the largest integer \(\leq N\) such that \(M\) contains no 1. Now there are as many numbers between 1 and \(N\) which do not contain a 1, as there are numbers between 1 and \(M\) which do not contain a 1. This is easy to see: if the amount of numbers which do not contain a 1 differs, there must be a number \(p\), \(M < p \leq N\) which contains a 1. But that contradicts the definition of \(M\). Note that if \(N\) does not contain a 1, then \(M = N\).

Given a number \(N\), it's easy to calculate \(M\), where \(M\) is the largest number less or equal to \(N\) which does not contain a 1: find the leftmost 1 in \(N\), replace this by a 0, and change any following digit by a 9. If \(N\) does not contain a 1, the number is left unmodified.

So, we need to do three things:

1. Find the largest number smaller than the input number which does not contain a 1.
2. Subtract 1 from each non-zero digit.
3. Convert the resulting number from base 9 to base 10.

All three things can be done in a single left to right pass.

The described algorithm is performed in a single left to right pass of the input number. Since the third step involves multiplication of an increasingly larger number, each pass is going to be linear in the number of digits of the input; and we need a number of passes which is linear in the number if digits as well. Which means that if our input number consists of \(d\) digits, the running time of our algorithm is bounded by \(\mathcal{O} (d^2)\). (\(\mathcal{O}(d)\) if you consider multiplication to be a constant time operation).

A tempting way of solving this problem would be to inspect all the numbers from 1 till \(N\), discarding the ones containing a 1, and tallying the remainders. But if we look at the running time of this algorithm, we'll see this is \(\Omega (d \cdot 10^{d-1})\), where \(d\) is the the number of digits of the input number.

How dramatic the difference between both implementations is is shown in the table below. First column is the input number \(N\). Second column is the time (in microseconds) of the solution described above (Perl implementation shown below), while the third column is the running time of:

$n = <>;
my $result = grep {!/1/} 1 .. $n;

All times are in microseconds:

\(N\)	Time (μsec)
10	0.518	4
20	0.846	8
50	0.751	19
100	1.103	38
200	1.158	82
500	0.963	184
1000	1.242	364
2000	1.347	759
5000	1.239	1896
10000	1.400	3732
20000	1.446	7650
50000	1.542	17511
100000	1.389	38033
200000	1.804	75876
500000	1.781	168706
1000000	1.596	412139
2000000	1.885	510239
5000000	1.921	1531234
10000000	1.789	3452088
20000000	2.089	8721964
50000000	2.115	470332870

In our implementation, an input of a 1,000 digits spits out the answer in less than 0.02 seconds. The naïve way would not finish before the universe ends.

As described above in the section Discussion, we find the answer using a couple of left to right passes of the input number. We can even condense this in a single left to right pass.

We'll keep two variables to keep state, $result, which at the end contains our answer, and $seen_one, to determine whether we have spotted a 1 in our input number. They are both initialized to 0:

my $result   = 0;
my $seen_one = 0;

Then for each digit of our input number ($n) we first multiply $result by 9 (since we're converting from base-9 to base-10):

foreach my $digit (split // => $n) {
    $result *= 9;

Then we have a three (or four, but in the fourth case, we don't do anything) cases:

• If we have seen a 1 in the input ($seen_one), we add 8 to $result. The 8 is a combination of finding the largest 1-free number not exceeding the input, and the shifting of digits by 1.
• Else, if $digit is 1, we set $seen_one to true. We don't have to add anything to $result in this case, as this is the first 1 in the input number, and this would be a 0 when getting the largest 1-free number smaller than the input number, and a 0 doesn't contribute when converting bases.
• Else, if $digit isn't 0, we add $digit - 1 to $result.

In the fourth cases, $digit equals 0. In that case, nothing needs to be done.

if    ($seen_one)   {$result += 8}
elsif ($digit == 1) {$seen_one = 1}
elsif ($digit)      {$result += $digit - 1}

Now all that is left to be done is print the result:

say $result;

Find the full program on GitHub.