1
$\begingroup$

Relative prime density of $f(n)$

Definition

Number of primes of $f(n)$

Using the prime counting function $\pi(n)$, we can define the number of primes $\pi_{nbr}$ of a function $f(n)$ from $n=1$ to $k$ as:

$$\pi_{nbr}(f(n),k)=\sum_{n=1}^{k}\pi(f(n))-\sum_{n=1}^{k}\pi(f(n)-1)$$

Expected number of primes of $f(n)$

The prime number theorem states that the probability that a integer $n$ is prime is $\approx\frac{1}{\log n}$, so we can define the expected number of primes $\pi_{exp}$ of a function $f(n)$ from $n=1$ to $k$ as:

$$\pi_{exp}(f(n),k)=\sum_{n=1}^{k}\frac{1}{\log f(n)}$$

Relative prime density of $f(n)$

For a function $f(n)$ from $n=1$ to $k$, if we take the number of primes over the expected number of primes, we get the relative prime density $\rho_{rel}$ of $f(n)$:

$$\rho_{rel}(f(n),k)=\frac{\pi_{nbr}(f(n),k)}{\pi_{exp}(f(n),k)}=\frac{\sum_{n=1}^{k}\pi(f(n))-\sum_{n=1}^{k}\pi(f(n)-1)}{\sum_{n=1}^{k}\frac{1}{\log f(n)}}$$

In other words, if you choose a random integer of the form $f(n)$, not greater than $f(k)$, you have $\rho_{rel}(f(n),k)$ times more chance of finding a prime number than if you choose from any integer not greater than $f(k)$.



Observations

A) $\rho_{rel}$ of the $n^{th}$ prime $p_{n}$

$$\rho_{rel}(p_{n},k)=\frac{\pi_{nbr}(f(n),k)}{\pi_{exp}(f(n),k)}=\frac{k}{\sum_{n=1}^{k}\frac{1}{\log p_{n}}}$$

We know from the PNT that the expected number of primes $\pi_{exp}$ of a function $f(n)$ from $n=1$ to $k$ can also be defined as:

$$\pi_{exp}(f(n),k)\sim\frac{k}{\log f(k)}$$

in the sens that:

$$\lim_{k\rightarrow\infty}=\frac{\frac{k}{\log f(k)}}{\sum_{n=1}^{k}\frac{1}{\log f(n)}}=1$$

Therefore, we get:

$$\rho_{rel}(p_{n},k)=\frac{\pi_{nbr}(f(n),k)}{\pi_{exp}(f(n),k)}\sim\frac{k}{\frac{k}{\log p_{k}}}\sim\log p_{k}$$

And finally: $$\lim_{k\rightarrow\infty}\rho_{rel}(p_{n},k)=\log\infty=\infty$$




   $k$                    $\rho_{rel}(p_{n},k)$                 $\log p_{k}$                       $\frac{\log p_{k}}{\rho_{rel}(p_{n},k)}$

2^1         0.850002        1.098612        1.29248
2^2         1.146733        1.945910        1.69691
2^3         1.603961        2.944438        1.83572
2^4         2.216540        3.970291        1.79121
2^5         2.965244        4.875197        1.64411
2^6         3.816873        5.739792        1.50379
2^7         4.726268        6.577861        1.39176
2^8         5.653045        7.389563        1.30718
2^9         6.571521        8.208219        1.24905
2^10        7.467793        9.007121        1.20612
2^11        8.338007        9.790486        1.17419
2^12        9.183391        10.56805        1.15077
2^13        10.00733        11.33877        1.13304
2^14        10.81376        12.10350        1.11926
2^15        11.60615        12.86383        1.10836
2^16        12.38744        13.61905        1.09942
2^17        13.15982        14.37085        1.09202
2^18        13.92501        15.11873        1.08572
2^19        14.68433        15.86372        1.08031



B) $\rho_{rel}$ of $f(n)=xn-1$

$$\rho_{rel}(xn-1,k)=\frac{\pi_{nbr}(xn-1,k)}{\pi_{exp}(xn-1,k)}=\frac{\sum_{n=1}^{k}\pi(xn-1)-\sum_{n=1}^{k}\pi(xn-2)}{\sum_{n=1}^{k}\frac{1}{\log(xn-1)}}$$

When we compute $\rho_{rel}(xn-1,k)$ for different values of $x$ , we can clearly see that the values converge, and that:

$$\lim_{k\rightarrow\infty}\rho_{rel}(xn-1,k)=\prod_{x\equiv0\pmod p}\left(1+\frac{1}{p-1}\right)$$


   $x$      $\rho_{rel}(xn-1,10^{5})$      $\prod_{x\equiv0\pmod p}\left(1+\frac{1}{p-1}\right)$

2       1.990876        2
3       1.487079        1.5
4       1.992607        2
5       1.241260        1.25
6       2.987535        3
7       1.161095        1.1666666
8       1.980295        2
9       1.493497        1.5
10      2.494988        2.5
11      1.096479        1.1
12      2.986270        3
13      1.084067        1.083333333
14      2.323696        2.333333333
15      1.863521        1.875
16      1.987482        2
17      1.065104        1.0625
18      2.995015        3
19      1.041543        1.055555556
20      2.483307        2.5
21      1.745753        1.75
22      2.198750        2.2
23      1.046219        1.045454545
24      2.978536        3
25      1.252011        1.25
26      2.152474        2.166666667
27      1.495796        1.5
28      2.330276        2.333333333
29      1.039471        1.035714286
30      3.733861        3.75



Questions

I'm trying to answer the following questions:

1) Show that:

$$\lim_{k\rightarrow\infty}\rho_{rel}(xn-1,k)=\frac{\sum_{n=1}^{k}\pi(xn-1)-\sum_{n=1}^{k}\pi(xn-2)}{\sum_{n=1}^{k}\frac{1}{\log(xn-1)}}=\prod_{x\equiv0\pmod p}\left(1+\frac{1}{p-1}\right)$$

2) Prove/disprove the following conjecture:

The limit $\lim_{k\rightarrow\infty}\rho_{rel}(f(n),k)$ is defined for any functions except $f(n)=p_{n}$ , where $p_{n}$ is the $n^{th}$ prime.

3) Prove/disprove the following conjecture:

There exists no function $f(n)$ such that $\rho_{rel}(f(n),k)\geq\rho_{rel}(p_{n},k)$ for sufficiently large values of $k$ , where $p_{n}$ is the $n^{th}$ prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.