Consider all possible 1000 digit positive base 10 integers all of whose digits are odd. For how many of these integers, do each pair of adjacent digits differ precisely by 2 ?

Note: Try to solve this problem analytically, although computer program/ spreadsheet solutions are welcome.

(In reply to computer-aided solution by Charlie)

 Extending the table, we can confirm a pattern seen in the shorter table:

For n-digit numbers
          number that end in:
 n         1      3      5      7      9   total
 -         -      -      -      -      -   -----
 2         1      2      2      2      1      8
 3         2      3      4      3      2     14
 4         3      6      6      6      3     24
 5         6      9     12      9      6     42
 6         9     18     18     18      9     72
 7        18     27     36     27     18    126
 8        27     54     54     54     27    216
 9        54     81    108     81     54    378
10        81    162    162    162     81    648
11       162    243    324    243    162   1134
12       243    486    486    486    243   1944
13       486    729    972    729    486   3402
14       729   1458   1458   1458    729   5832
15      1458   2187   2916   2187   1458  10206
16      2187   4374   4374   4374   2187  17496
17      4374   6561   8748   6561   4374  30618
18      6561  13122  13122  13122   6561  52488
19     13122  19683  26244  19683  13122  91854

For even n, the number of integers ending in the digit 1 is 3^((n/2)-1). The same number end in 9 and twice as many end in each of the other three possible ending digits.

The total is therefore 8 * 3^((n/2)-1). In the particular instance of n = 1000, the answer would be 8 * 3^499, which is indeed what was found numerically via the iterations performed, given in my preceding post.

Posted by Charlie on 2008-09-22 17:47:13