Problem:
For each positive integer n, find the number of n-digit positive integers that satisfy both of the following conditions:
- no two consecutive digits are equal, and
- the last digit is a prime.
Solution:
First solution. Let us call a positive integer great if it has no consecutive digits equal and its last digit is prime. Let p(n) denote the number of great n-digit numbers, so the problem is asking us to compute p(n). We claim that p(n)=2⋅59n−(−1)n​.
For n≥2, we say an n-digit number is good if it ends in a prime digit and has no two consecutive digits equal among its first n−1 digits. Since the first n−1 digits and the last digit may be treated independently, the number of good n-digit numbers is 4⋅9n−1.
Clearly, any great number is good. On the other hand, a good n-digit number fails to be great if its last two digits are equal. By disregarding the last digit, such good-but-not-great numbers are in bijection with great (n−1)-digit numbers. Thus, for n≥2, we have the equation p(n)= 4⋅9n−1−p(n−1). (If n=1, we have p(1)=4⋅90=4.) Applying this recursively, we find that
p(n)=4⋅(9n−1−9n−2+9n−3−⋯+(−1)n−2⋅9+(−1)n−1)=4⋅109n−(−1)n​
as claimed.
Second solution. Define great numbers and p(n) as above. For n≥3, we will count the number of great n-digit numbers by considering two cases:
- If the second digit is 0 , then note that the third digit must be non-zero, so the last n−2 digits form a great number. Meanwhile, the first digit can be any non-zero digit. Thus, there are 9⋅p(n−2) great n-digit numbers of this form.
- If the second digit is not 0 , then the last n−1 digits form a great number, while there are 8 possibilities for the first digit (it can be any non-zero digit not equal to the second digit). This gives 8⋅p(n−1) great n-digit numbers of this form.
We conclude that p(n)=8p(n−1)+9p(n−2) for all n≥3. This is a second order recurrence, which we may solve by factoring its characteristic polynomial t2−8t−9=(t−9)(t+1). The factorization implies that p(n) takes the form p(n)=A⋅9n+B⋅(−1)n for some constants A and B. We can solve the system
9A−B=p(1)=4
81A+B=p(2)=32
which yields A=52​ and B=−52​, so that
p(n)=52(9n−(−1)n)​
The problems on this page are the property of the MAA's American Mathematics Competitions