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.

I came to the same 239 digit number* as did Charile but using a big number calculator to find the answer to the following equation plugging in 1000 for the value of x such that x is the number of digits and n being the total number of distinct numbers of odd digits where adjacent digits have a difference of exactly 2 from their neighboring digits:

n = (8 + 6*(x mod 2)) * 3^{([x/2] - 1)}, such that x > 1

The above equation was derived by examining the number of new numbers formed with each appendage of a digit, with [A] as the FLOOR function of A and (A mod B) as A modulo B.

(If I did my equation correctly, for 999 digits the solution would be 14*3⁴⁹⁸. Perhaps Charlie might be kind enough to confirm this.)


* 8*3⁴⁹⁹ =
9696077812231983157969404554544885098139569340
2670994774256095553548267177557054624529355367
9450367554884792067584102820076158173787015097
1464648244416540208005805666092704920033424756
4175501893260240990907073543274689029307039454
340293336.

Edited on September 23, 2008, 3:10 am

Edited on September 24, 2008, 4:55 am

Posted by Dej Mar on 2008-09-23 02:58:22