A Problem on Prime and Composite Numbers Relation

145 Views Asked by At

I was fighting with this question for about five days and I’m unable to get a mathematical proof.

Question: Let imagine a natural number and a prime number $q$ and $k$ respectively such that $k>q$ and $k$ is the nearest prime number with respect to $q$: $$ f(n)= q n + k \qquad \text{where $n<k$}. $$ How can we calculate the number of values of $n$ so that $f(n)$ will always be a prime number for some values of $q$?

Example: let $q=4$, then the nearest prime number which is greater than $4$ is $5$, so $k=5$: $$ f(n) = 4n + 5, \qquad \text{here $n<5$}. $$ If $n$ is $2$ and $3$ then $f(n)$ are prime numbers, so the total values of $n$ are $2$.

Similarly for $q = 6$ then $k = 7$: $$ f(n) = 6n + 7, \qquad \text{here $n<7$}. $$

If $n$ is $1$,$2$,$4$,$5$ and $6$ then $f(n)$ are primes. So the total number of values of $n$ are $5$ which satisfy our conditions.

1

There are 1 best solutions below

0
On

This is more comment than answer, so I'm making it Community Wiki in case anyone wants to extend or correct the sequence.

The question defines a function

$$P(q)=\#\{n\mid1\le n\lt k\text{ and }nq+k\text{ is prime, where }k\text{ is prime and }\pi(k)-\pi(q)=1\}$$

(Note, $\pi(k)-\pi(q)=1$ is a way of saying that $k$ is the first prime greater than $q$.) For example,

$$P(6)=\#\{n\mid1\le n\lt k\text{ and }6n+7\text{ is prime}\}=\#\{1,2,4,5,6\}=5$$

since $13$, $19$, $31$, $37$, and $43$ are prime but $25$ is not. Similarly we have

$$P(1)=1,\quad P(2)=2,\quad P(3)=2,\quad P(4)=2,\quad P(5)=2,\\\quad P(7)=2,\quad P(8)=5,\quad P(9)=4,\quad P(10)=5$$

so we have a sequence beginning

$$1,2,2,2,2,5,2,5,4,5,\ldots$$

The OEIS does not (yet) recognize this sequence, even without the initial $1$. (Caveat: I've done all the arithmetic and counting in my head, so I wouldn't mind if someone doublechecked the sequence.) This doesn't prove anything, of course, but it suggests there's no simple relation that describes the sequence.