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.

If the puzzle were for 1-digit numbers, the answer would be 5, as there'd be one such number for each of the 5 allowable digits.

If we want to keep track of what the answers would be for increasing numbers of digits in the integers in question, we can do that by keeping separate counts for integers ending in each of the five particular digits that such integers can end in.  An n-digit integer can end in a 1 as often as an (n-1)-digit number can end in a 3. An n-digit number can end in a 3 as often as an (n-1)-digit number can end in either a 1 or a 5, and so forth.

A table of the first 9 generations is as follows:

For n-digit numbers
          number that end in:
  n       1    3    5    7    9   total
  -       -    -    -    -    -   -----
  1       1    1    1    1    1      5
  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

 
So for example if the puzzle had referred to 9-digit numbers rather than 1000-digit numbers, the answer would have been 378.
 
Allowing the program that generated the above table to continue to n=1000, gives:
 
Ending in 1:
 1212009726528997894746175569318110637267446167533387434678201194419353339719463
18280661694209931295944360599008448012852509519771723376887143308103055206752600
07257082615881150041780945521937736657530123863384192909336128663379931792536667
 
Ending in 3:
 2424019453057995789492351138636221274534892335066774869356402388838706679438926
36561323388419862591888721198016896025705019039543446753774286616206110413505200
14514165231762300083561891043875473315060247726768385818672257326759863585073334
 
Ending in 5:
 2424019453057995789492351138636221274534892335066774869356402388838706679438926
36561323388419862591888721198016896025705019039543446753774286616206110413505200
14514165231762300083561891043875473315060247726768385818672257326759863585073334
 
Ending in 7:
 2424019453057995789492351138636221274534892335066774869356402388838706679438926
36561323388419862591888721198016896025705019039543446753774286616206110413505200
14514165231762300083561891043875473315060247726768385818672257326759863585073334
 
Ending in 9:
 1212009726528997894746175569318110637267446167533387434678201194419353339719463
18280661694209931295944360599008448012852509519771723376887143308103055206752600
07257082615881150041780945521937736657530123863384192909336128663379931792536667
 
Total:
 9696077812231983157969404554544885098139569340267099477425609555354826717755705
46245293553679450367554884792067584102820076158173787015097146464824441654020800
58056660927049200334247564175501893260240990907073543274689029307039454340293336

That total is approximately 9.6960778122319839832 x 10^238.

  10   dim D(10),NewD(10)
  20   for I=1 to 9 step 2:D(I)=1:next
  30   for G=2 to 1000
  35    erase NewD():dim NewD(10)
  40    for I=1 to 9 step 2
  50      for J=I-2 to I+2 step 4
  60        if J>0 and J<10 then NewD(I)=NewD(I)+D(J)
  70      next J
  80    next I
  90    for I=1 to 9 step 2
 100      D(I)=NewD(I)
 110    next
 115    if G<10 then gosub 500
 120   next G
 200   for I=1 to 9 step 2
 210     print D(I)
 220     T=T+D(I)
 230   next
 250   print:print T
 260   Tot=log(T)/log(10):T1=int(Tot):T2=10^(Tot-int(Tot))
 270   print T2;"x 10^";T1
 300   end
 
 500   Sum=0:print using(3,0),G;:print "   ";
 510   for I=1 to 9 step 2
 520     print using(5,0),D(I);
 530     Sum=Sum+D(I)
 540   next
 550   print using(7,0),Sum
 590   return

Edited on September 22, 2008, 3:01 pm

Posted by Charlie on 2008-09-22 15:00:34