How many odd $100$-digit numbers such that every two consecutive digits differ by exactly 2 are there?

My first idea was to calculate the number of all odd $100$-digit numbers which use only odd digits, which equals $5^{100}$, and then try to subtract the number of all bad numbers, but I couldn't calculate it.

Then I tried to establish recurrence relation, but I don't even know where to start.

For example, all $3$-digit numbers which satisfy above condition: $135$, $131$, $313$, $353$, $357$, $535$, $531$, $575$, $579$, $757$, $753$, $797$, $975$, $979$ .

Please help!

  • $\begingroup$ Can you please give example of one such number? $\endgroup$ – tatan Oct 12 '16 at 11:28
  • $\begingroup$ Sorry, I forgot. All $3$-digit numbers which satisfy above condition: $135$, $131$, $313$, $353$, $357$, $535$, $531$, $575$, $579$, $757$, $753$, $797$, $975$, $979$ . $\endgroup$ – mivan Oct 12 '16 at 11:30
  • $\begingroup$ I take it you mean "differ in absolute value"? So $202020\dots$ is a good example? $\endgroup$ – lulu Oct 12 '16 at 11:30
  • 2
    $\begingroup$ @tatan For instance, $13135753$, or $64246864$ for $8$ digits. It's like a bounded random walk. $\endgroup$ – Jean-Claude Arbaut Oct 12 '16 at 11:31
  • 1
    $\begingroup$ Can you please clarify your question? The number of odd $100$-digit numbers is NOT $5^{100}$. And then you switch to three digits, which can easily be done by hand... $\endgroup$ – lulu Oct 12 '16 at 11:32

To establish a recurrence relation you could proceed as follows (this is an answer not a comment for length, but won't solve the recurrence).

Let $a_n, b_n, c_n, d_n, e_n$ be respectively the number of $n$-digit numbers in your set beginning with the digits $1,3,5,7,9$ respectively. Then stripping the first digit gives $$a_n=b_{n-1}; b_n=a_{n-1}+c_{n-1}; c_n=b_{n-1}+d_{n-1};d_n=c_{n-1}+e_{n-1};e_n=d_{n-1}$$

Then observe that symmetry considerations give $a_n=e_n$ and $b_n=d_n$

This reduces the system to $3$ equations $$a_n=b_{n-1}$$$$ b_n=a_{n-1}+c_{n-1}$$$$ c_n=2b_{n-1}$$ and that immediately gives $c_n=2a_n$ and I'll leave it to you to solve from there, having got the system under some control.


A direct recurrence is difficult, but if we count something different, then it becomes easier. For each of the five digits $d \in \{1,3,5,7,9\}$, and for each number length $n$, we can count the number $A(d,n)$ of numbers satisfying your constraint. For each $d$, we have $A(d,1) = 1$. For $n > 1$, we have $A(n,1) = A(n-1,3)$, and $A(n,9) = A(n-1,7)$, and for the other digits $d$, we have $$ A(n,d) = A(n-1,d-2) + A(n-1,d+2). $$ This is still tedious for a human to compute, but a very short computer program should make this easy.


Define $D(n, e)$ as your number, length $n$ and ending with $e$.

$D(1, e) = 1, e \in \{1,3,5,7,9\}$

$D(n, 1) = D(n, 9) = D(n-1, 3)$

$D(n, 3) = D(n, 7) = D(n-1, 5) + D(n-1, 1)$

$D(n, 5) = D(n-1, 3) + D(n-1, 7) = 2*D(n-1, 3)$


Let $t_n$ be the number of good sequences of length $n$. for $d\in \{1,3,5,7,9\}$ let $d_n$ denote the number of good sequences that end in $d$. recursively"

$$1_n=3_{n-1}\quad 3_n=1_{n-1}+5_{n-1}\quad \cdots \quad 9_n=7_{n-1}$$

This is easy to implement, and we get $t_3=14$, $t_{100}=1914394633844940236720664 $.

the first few values are $\{5,8,14,24,42,72,126,\dots\}$ which is not recognized by OEIS...I doubt there is a pleasant closed formula for them.

Note: As remarked by @MarkBennet below, there is indeed a pleasant closed formula for these number, my doubts notwithstanding. This follows from the symmetry considerations well described in his posted solution.

  • $\begingroup$ After the first few terms each is three times the term two before it. $\endgroup$ – Mark Bennet Oct 12 '16 at 11:51
  • $\begingroup$ @MarkBennet True...not immediately sure why, though. $\endgroup$ – lulu Oct 12 '16 at 12:02
  • $\begingroup$ @MarkBennet Ah, symmetry does it. But I see you've covered that in your solution. $\endgroup$ – lulu Oct 12 '16 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.