Simple formula with high prime output

Question

In doing unrelated calculations I was a bit flabbergasted when I found that the formula

$f(n)=8 + 3(5^n)$

gives prime numbers for $n=0,1,2,3$; so I checked further and found:

Out of the first 401 natural numbers (that is, $n=0,1,...,400$) 19 of these have $f(n)$ prime. They are: 0, 1, 2, 3, 7, 9, 14 19, 21, 24, 38 , 48, 49, 59, 69, 86, 131, 174, 399. (Easily checked on Wolfram-Alpha)

I do not at all know what a reasonable number of primes would be out of this, but I expect fewer than this would be expected, given how large the numbers become. My very lax reasoning is below:

The expected density of primes given the number of primes less than $8+3(5^{400})$ (using $Li(n)=\int_2^n\frac{1}{log(x)}dx$ to estimate $\pi(x)$) is about $Li(3\cdot5^{400})\approx 0.00155$. For 200, $Li(3\cdot 200)\approx0.00357$ is the approximate density. So we should expect somewhere on the order of magitude of a density of $0.002$ for primes in the range $3\cdot 5^{174}$ to $3\cdot 5^{400}$.

However, since by the end of the sequence there is about 1 prime for every 200 attempts, or about $0.005$, which is more than twice the expectation (granted 399 is luckily just scraping under 400).

My question: Is there any way to see if this sequence is more likely to generate primes than other sequences? Further, is this a pattern that is already known in some fashion?

Interesting side note: the same pattern holds for small numbers (I haven't checked very far) for the similar sequence $g(n)=4+3(5^n)$.

Answer 1

The numbers $a_n:=8+3\cdot 5^n$ all have remainder $-1$ modulo $6$. Therefore the a priori probability of $a_n$ being prime is about $${3\over\log a_n}\approx {3\over\log 5}\cdot{1\over n}\ .$$ Summing these over $n\in[1 .. 400]$ gives an expectation $$E\approx{3 \log 400\over\log 5}\approx 11.2\ .$$

Answer 2

$$f(n+1)=5\cdot f(n)-32$$ which also turns this into: $$5^n\cdot 11-{5^n-1\over 4} \cdot 32$$ via Iteration , which you can see simplifies to the original description. The first shows it to always be 3 mod 5 after the first. mod by 6, and you can show since 11 is -1 mod 6 they all will be. Together by CRT, this makes them all 23 mod 30 after the first. $$30\cdot k+23$$ where k iterates $$5\cdot k+2$$ starting at $k=0$. means from the second k value on we have a number of form $$150\cdot j+83$$ etc. I'd suggest sieving via a sieve of sundaram style sieve eventually. it is known any odd number of form: $$2\cdot (2\cdot l\cdot m+l+m)+1$$ is composite with both k and j above 0. try to prove when your inputs can be of this form.