You can also eliminate non-multiples of 5 when you consider mod 5. This leaves only n that are congruent to 5 mod 10.

Not sure how to deal with those.. but the first 200 of them are composite.

Maybe you can factor them. Let f(n) = n^4 + 4^n. There might be a pattern here: (note: f(25) is not given as prime factorization, rather I multiplied some primes to get two factors close together.)

f(5) = 17 * 97

f(15) = 29153 * 36833

f(25) = 33350257 * 33759857

f(35) = 34350564553 * 34368914633

Difference between the two factors shows a pattern:

80 = 2^4 * 5

7680 = 2^9 * 3 * 5

409600 = 2^14 * 5 * 5

18350080 = 2^19 * 5 * 7