Sunday, May 6, 2018

Simple formula with high prime output

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)$.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...