Simple formula with product 1 mod 4

Question

How many $n$-digit positive integers satisfy that the product of its digits makes 1 remainder $\pmod 4$?

What I know is that each digit is odd and I know a really long formula. If $a_n$ is the number of $n$- digit numbers satisfying the conditions, then my formula uses $a_1,\dots, a_n$, but I believe there exist an easier, shorter formula.

Answer 1

Let $a_n$ be the number of $n$-digit positive integers satisfying the product of its digits is $1\pmod{4}$. Let $b_n$ be the number of $n$-digit positive integers satisfying that the product of its digits is $3\pmod{4}$. Note that $a_n+b_n=5^n$ since every $n$-digit number consisting entirely of odd-digits falls into exactly one of these cases and vice versa and so $b_n=5^n-a_n$.

To create a string of length $n+1$, we can take a string of length $n$ whose product is $1\pmod{n}$ and tack on a 1,5, or 9 at the end or we can take a string of length $n$ whose product is $3\pmod{n}$ and tack on a 3 or 7 at the end, giving $a_{n+1}=3a_n+2b_n=3a_n+2(5^n-a_n)=a_n+2\cdot 5^n$.

This along with an initial condition of $a_1=3$ gives a recurrence formula for the number you wish to count. This can then be solved for a closed form if you so desire and will be of the form $a_n=c+d\cdot 5^n$ for some constants $c$ and $d$.

Answer 2

Each of the $n$ digits must be odd and there must be an even number of 3s and 7s (because these digits are equal to $3 \mod 4$).

So for each even number of digits from 0 to $n$ - call this even number $m$ - we (a) count the number of ways to choose $m$ digits from $n$ and (b) multiply this by $2^m3^{n-m}$ because $m$ digits can be 3 or 7 and the remaining $n-m$ digits can each be 1, 5 or 9.

So we want to find the sum of the even terms in binomial expansion of $(3+2)^n$. A trick to pick out the even terms is to notice that in the binomial expansion of $(3-2)^n$ the odd terms become negative (because they contain an odd power of $-2$). So the sum of the even terms is:

$\frac{1}{2}((3+2)^n+(3-2)^n))=\frac{1}{2}(5^n+1)$