# In how many of the integer numbers between 0 and 10,000 does the digit 3 appear to the left of 4

In how many of the integer numbers between $0$ and $10\,000$ does the digit $3$ appear some place to the left of the digit $4$? This would include, for example, the numbers $34$, $374$, $4384$ and $3874$, but would not include $27$, $43$, $3650$ or $4333$.

So I am thinking you do $$8\cdot9\cdot1\cdot1+1\cdot9\cdot1+8\cdot1\cdot9\cdot1+1\cdot9\cdot9\cdot1 = 234$$ But I feel like that is too low.

-
You have created confusion between the header : in how many numbers 3 appears, and in the main part: how many numbers 3 appears some place to the left of 4. Please clarify ! – true blue anil Mar 14 at 5:00
ZERO if the numbers are binary.... – CiaPan Mar 15 at 8:47

Call such an integer good. Pad with initial $0$'s if necessary to make a $4$-digit string from $0000$ to $9999$.

The easy ones are the ones that begin with $3$. Any such string is good if the $3$-digit string after the initial $3$ contains a $4$. There are $10^3$ $3$-digit strings, of which $9^3$ have no $4$, giving $271$ with at least one $4$.

Now we count the "other" good strings. There are $9$ times as many as there are good strings that begin with $0$, which is the same as the number of $3$-digit good strings.

How many good $3$-digit strings are there? There are the ones that begin with $3$. The remaining $2$-digit string must contain a $4$. There are $19$ of these.

Then there are the ones that begin with something else. How many? $9$ times as many as there are good $4$-digit strings that begin with $00$. There is only $1$ of these.

We get a total of $271+9(19+(9)(1))$.

Remark: The same idea will take care of the count from say $000000$ to $999999$.

-
Sounds good to me. And a brute force count confirms that 523 is the correct number. – PM 2Ring Mar 14 at 7:19

We can describe the valid numbers with a FSA using the digits as alphabet (the upper bound on the number is not yet included):

Here the black numbers at the arrows denote the symbol used for the transition. If there is no such number every symbol that isn't used with another transition is valid. The red numbers denote the number of symbols that that result in the given target state.

States

A: No 3 found yet (initial state)

B: 3 found but no 4 found to the right of the first 3.

C: 4 found to the right of a 3 (final state)

We can represent this as a graph with the following adjacency matrix (weighted with number of symbols that can be used for each transition):

$$A=\begin{bmatrix}9&1&0\\0&9&1\\0&0&10\\\end{bmatrix}$$

Note that any path in this graph starting at vertex 1 corresponds to a number and every path also ending at vertex 3 is one of the numbers we want to count.

We only need to consider numbers 0, ..., 9999 since 10000 obviously doesn't fit the pattern. Therefore we only need to consider words with exactly 4 symbols ($\rightarrow$ path of length 4 in the graph).

Since we've chosen the edge weights of the graph appropriately the number to calculate can be directly read from last entry in the first row of the matrix

$$A^4=\begin{bmatrix}6561&2916&523\\0&6561&3439\\0&0&10000\\\end{bmatrix}$$

-
Might I suggest relabeling the nodes in the FSA with letters instead of numbers? This would be a bit more clear. – jpmc26 Mar 15 at 2:04
Using A as both a state and a matrix is a bit confusing too. – Paul Evans Mar 15 at 14:58
A good tool for a good job. – Orace Mar 15 at 15:03
Essentially a finite markov chain, but using 0-10 rather than probabilities. Very cool and the perfect tool for the job. – Mat Mar 15 at 15:56

Marking the first $3$ and the first $4$ after $3$, there are only $6$ cases:

$$\begin{array}{} 3&4&\bullet&\bullet&\implies& 10\cdot10 = 100\\ 3&\bullet&4&\bullet&\implies& 9\cdot 10 = 90\\ 3&\bullet&\bullet&4&\implies& 9\cdot9 =81\\ \bullet&3&4&\bullet&\implies& 9\cdot10 = 90\\ \bullet&3&\bullet&4&\implies& 9\cdot 9 = 81\\ \bullet&\bullet&3&4&\implies& 9\cdot9 = 81 \end{array}$$

Adding up, $523$.

Note: The first $4$ after the first $3$ has been marked, but this doesn't preclude a $4$ coming before the first $3$.

-
There are a little more, since some will have a $3$ before a $4$ and also a $4$ before a $3$. – André Nicolas Mar 14 at 5:18
Yea, thanks and (+1). Deleting for the nonce to examine if this route can lead somewhere ! – true blue anil Mar 14 at 5:48
The idea will work. Let $w$ be the number where a $3$ occurs before a $4$ but not the other way, and let $b$ be the number of ways both happen. Then we want $w+b$, and $2w+b$ is your $974$. If we can find $b$, we will be finished, and finding $b$ is not hard, one just has to be careful. – André Nicolas Mar 14 at 5:54
So this isn't correct? I feel like it is. – Ninjascroll86 Mar 14 at 7:29
523 is the correct answer as first given by Andre, I am also getting the same answer after correcting for the fact that the first digit can be $0$ if the number of digits is less than $4$. – true blue anil Mar 14 at 7:36

Let $a_n$ denote the number of strings of $n$ digits that contain at least one $3$ somewhere to the left of at least one $4$. You want to calculate $a_4$.

If $b = 0, 1, 2, 4, 5, \dots 9$, there are exactly $a_{n-1}$ such strings whose first digit is $b$. The number of such strings whose first digit is $3$ is the same as the number of $(n-1)$-digit strings containing at least one $4$, or $10^{n-1} - 9^{n-1}$.

Therefore $a_n$ can be calculated using the recurrence relation $$a_n = 9a_{n-1} + 10^{n-1} - 9^{n-1}, \quad a_1 = 0.$$

We have $a_2 = 1$, $a_3 = 28$, $a_4 = 523$.

Or: We can solve this linear recurrence relation to find $$a_n = 10^n - (n+9)9^{n-1}.$$ Then $a_4 = 10^4 - 13 \times 9^3 = 523.$

-

Here is my non-math answer: 523. I wonder if breaking the answer out into 6 cases yields duplicates. i.e. the same number could be counted in more than one case.

SYS@dbtstmra AS SYSDBA> SELECT COUNT(*) FROM ( SELECT LPAD( rownum, 4, '0') mynum FROM dba_tab_columns WHERE rownum < 10000 ) WHERE mynum LIKE '%3%4%';

COUNT(*)
----------
523

1 row selected.

Elapsed: 00:00:00.25

-
I think it's WHERE mynum LIKE '%3%4%'. – Alexander Mar 14 at 15:22
... or just seq 10000 | grep '3.*4' | wc -l -> 523. – Doorknob Mar 14 at 16:00
@Doorknob: you could probably save a few bytes my omitting the spaces around the pipes. Oh, this is not PCG? Well, then... :-) – Thomas Mar 14 at 16:25
@Thomas hahaha. Pyth, 16 bytes: lf:T"3.*4"0U^T4 – Doorknob Mar 14 at 16:28
@Doorknob seq 1e4|grep -c 3.\*4, if you're golfing :) – Digital Trauma Mar 14 at 21:28

Python:

>>> len([l for l in map(list, map(str, range(10001))) if '3' in l and '4' in l[l.index('3'):]])
523


Update:

The list map is not needed:

>>> len([l for l in map(str, range(10001)) if '3' in l and '4' in l[l.index('3'):]])
523

-
Minor: you could avoid materializing the list at all, e.g. sum('3' in l and '4' in l[l.index("3"):] for l in map(str, range(10001))). – DSM Mar 15 at 15:49

In C#:

using System.Text;

namespace ThreeBeforeFour {

class Program {

private const char firstDigit = '3';
private const char secondDigit = '4';
private const ulong upperLimit = 10000;

static void Main(string[] args) {
ulong count = 0UL;
for( ulong i = 0; i <= upperLimit; ++i ) {
string s = i.ToString();
int firstPos = s.IndexOf( firstDigit );
if( ( firstPos >= 0 ) && ( s.IndexOf( secondDigit, firstPos + 1 ) >= 0 ) ) {
Console.Write( s + ' ' );
count++;
}
}
Console.WriteLine();
Console.WriteLine(
"There are " + count + " integers between 0 and " + upperLimit + " that contain the digit " +
firstDigit + " followed by the digit " + secondDigit + "."
);
Console.WriteLine( "Press return." );
}

}

}


The output of this program is:

34 134 234 304 314 324 334 340 341 342 343 344 345 346 347 348 349 354 364 374 3
84 394 434 534 634 734 834 934 1034 1134 1234 1304 1314 1324 1334 1340 1341 1342
1343 1344 1345 1346 1347 1348 1349 1354 1364 1374 1384 1394 1434 1534 1634 1734
1834 1934 2034 2134 2234 2304 2314 2324 2334 2340 2341 2342 2343 2344 2345 2346
2347 2348 2349 2354 2364 2374 2384 2394 2434 2534 2634 2734 2834 2934 3004 3014
3024 3034 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3054 3064 3074 3084
3094 3104 3114 3124 3134 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3154
3164 3174 3184 3194 3204 3214 3224 3234 3240 3241 3242 3243 3244 3245 3246 3247
3248 3249 3254 3264 3274 3284 3294 3304 3314 3324 3334 3340 3341 3342 3343 3344
3345 3346 3347 3348 3349 3354 3364 3374 3384 3394 3400 3401 3402 3403 3404 3405
3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421
3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437
3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453
3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469
3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485
3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3504 3514
3524 3534 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3554 3564 3574 3584
3594 3604 3614 3624 3634 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3654
3664 3674 3684 3694 3704 3714 3724 3734 3740 3741 3742 3743 3744 3745 3746 3747
3748 3749 3754 3764 3774 3784 3794 3804 3814 3824 3834 3840 3841 3842 3843 3844
3845 3846 3847 3848 3849 3854 3864 3874 3884 3894 3904 3914 3924 3934 3940 3941
3942 3943 3944 3945 3946 3947 3948 3949 3954 3964 3974 3984 3994 4034 4134 4234
4304 4314 4324 4334 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4354 4364
4374 4384 4394 4434 4534 4634 4734 4834 4934 5034 5134 5234 5304 5314 5324 5334
5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5354 5364 5374 5384 5394 5434
5534 5634 5734 5834 5934 6034 6134 6234 6304 6314 6324 6334 6340 6341 6342 6343
6344 6345 6346 6347 6348 6349 6354 6364 6374 6384 6394 6434 6534 6634 6734 6834
6934 7034 7134 7234 7304 7314 7324 7334 7340 7341 7342 7343 7344 7345 7346 7347
7348 7349 7354 7364 7374 7384 7394 7434 7534 7634 7734 7834 7934 8034 8134 8234
8304 8314 8324 8334 8340 8341 8342 8343 8344 8345 8346 8347 8348 8349 8354 8364
8374 8384 8394 8434 8534 8634 8734 8834 8934 9034 9134 9234 9304 9314 9324 9334
9340 9341 9342 9343 9344 9345 9346 9347 9348 9349 9354 9364 9374 9384 9394 9434
9534 9634 9734 9834 9934
There are 523 integers between 0 and 10000 that contain the digit 3 followed by
the digit 4.
Press return.
`
-

As David shows, the formula for this with $d$ digits is

$$10^d - (d+9)9^{d-1}$$

We can prove this without the recurrence by showing that there are $9^d + d9^{d-1}$ ($=(d+9)9^{d-1}$) numbers where $3$ does not appear before $4$.

There are $9^d$ $d$-digit string with no $4$ at all, giving us $9^d$.

Every other $d$-digit string has at least one $4$. Suppose the rightmost occurrence of $4$ is at digit $i \in [1, d]$, then every number before it has $9$ choices (anything but $3$, by assumption) and every number after it has $9$ choices (anything but $4$). This gives us our $d9^{d-1}$.

Adding the two together gives us all numbers where $3$ is not before $4$, and since there are $10^d$ digits, the answer above is shown to be correct.

-