Fibonacci is Life

Let $a_n$ be the number of positive integers made up of digits $1, 3, 4$ such that the sum of its digits is $n$ ; we're looking for $a_{42}$ .

By simple case check, we can see that $a_1 = 1$ (1), $a_2 = 1$ (11), $a_3 = 2$ (111, 3), and $a_4 = 4$ (1111, 13, 31, 4). We also have $a_n = a_{n-1} + a_{n-3} + a_{n-4}$ for $n \ge 5$ ; removing the last digit gives a positive integer made up of digits $1, 3, 4$ with sum of its digits being one of $n-1, n-3, n-4$ depending on the digit that's removed. Then we can just plug it in to a spreadsheet program or something to find $S = a_{42} = 313679521$ , so $\sqrt{S} = \boxed{17711}$ .