Solution #27

We want to find all x1 such that x1, x2, ..., x20 is an f-generated sequence in which x20 is the first 1.

If x20 is 1, then x19 must be 10. From here, we can work backward either by subtracting 1 or by multiplying by 10.

However, if we subtract 1 nine times in a row, we will be back to 1. So in the backtracking from x19 to x10, there must be at least one multiplying by 10. With two options at each step, we get 2⁹ ways of backtracking from x19 to x10, and after subtracting the option of subtracting 1 nine times in a row, we are down to 2⁹-1.

Now we must backtrack nine more steps to x1. Given that there must have been a multiplying by 10 somewhere in the backtracking from x19 to x10, x10 is greater than 10. Thus we can subtract 1 each time without danger of dropping to 1, and both options are available as we move from x10 to x1, giving 2⁹ ways of doing this backtracking.

However, there cannot be a string of ten consecutive backtracking moves in which we subtract 1 -- if there were, some element in that string would be a multiple of 10, which would require the "divide by 10" rule going forward.

So we have a preliminary total of 2⁹(2⁹ - 1) possibilities, from which we need to subtract the possibilities in which there are ten consecutive -1 moves. But we have already blocked the option of having ten consecutive -1 moves at the start of the backtracking, so we only need to count the "ten consecutive -1" options that are preceded by a "multiply by 10" backtracking move.

There are a total of 18 backtracking moves, not counting the forced initial move of multiplying by 10. We require a sequence "*10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1", but the other seven moves are free. Those seven moves can be filled in 2⁷ ways, and the sequence can be placed in 8 ways. So 8*2⁷ arrangements must be eliminated.

Thus gives a total of 2⁹(2⁹ - 1) - 8*2⁷ = 260,608 sequences.