Есть решение для всех n, не кратных 5.
Если есть мысли, как справиться с этим случаем - присоединяйтесь.

Очевидно, что при четных n данное выражение дает составное число.
Значит, надо рассмотреть только нечетные n.

Рассмотрим n как выражение 10k+t, где t = 1, 3, 5, 7, 9.

(10k+1)⁴=(10k)⁴+4(10k)³+6(10k)²+4(10k)+1[$8801$]1 mod 10
(10k+3)⁴=(10k)⁴+4(10k)³*3+6(10k)²*3²+4(10k)*3³+3⁴[$8801$]1 mod 10
(10k+7)⁴=(10k)⁴+4(10k)³*7+6(10k)²*7²+4(10k)*7³+7⁴[$8801$]1 mod 10
(10k+9)⁴=(10k)⁴+4(10k)³*9+6(10k)²*9²+4(10k)*9³+9⁴[$8801$]1 mod 10

Т.о., n⁴[$8801$]1 mod 10 для рассмотренных n.

64ⁿ=2⁶ⁿ
Если n=10k+1, то 6n mod 4 = 2
Если n=10k+3, то 6n mod 4 = 2
Если n=10k+7, то 6n mod 4 = 2
Если n=10k+9, то 6n mod 4 = 2

В любом случае 6n имеет остаток 2 при делении на 4. Но т.к. 2^4m+2[$8801$]4 mod 10, то 64ⁿ[$8801$]4 mod 10 для рассмотренных n.

Отсюда имеем: n⁴+64ⁿ[$8801$](1 mod 10)+(4 mod 10) = 5 mod 10, т.е. делится на 5.

Поэтому данное выражение дает в результате составное число для всех n, не кратных 5.

Что могу сказать про нечетные числа, кратные 5.

Прямая проверка n=5 дала составное число 1073742449 = 82595573 * 13.

Обозначим n=10k+5.
Тогда:
A_k=64ⁿ=2^60k+30

При этом A_k mod 13 = 12 при всех k.

Однако B_k=n⁴ = 1 mod 13 не при всех k.
Я нашел следующие значения k:
0, 2, 10, 12, 13 и 15.

При этом n= 5, 25, 105, 125, 135, 155.

Дальше получаются очень большие выражения, Excel не справляется.
64ⁿ растет очень быстро, 64¹⁵>10²⁷, что опять же не позволяет посчитать выражение в Excel.

Для справки: пакет Mathematica 6 анализирует простоту чисел вида n^4+64^n для n от 1 до 10000 за 27 мин. Если же n<=4000, то время затрачивается от 0,031 c. до 34 c.
И все же, без аналитики не обойдешься. Хотя, может быть, задачу можно свести к перебору конечного числа случаев. Я не думал об этом.
С уважением

Ну так его ж еще надо скачивать и устанавливать...
А эксель всегда под рукой.
Не догадался на множители разложить, посчитал, что в лоб получится. Однако кратные 5 числа оказались крепким орешком...