Return to Answer

There are even stronger conjectures in the literature:

1. D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.htm

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

Update: Computing the first values of least primes 1 mod p, and checking the OEIS http://oeis.org/A035095

where we find the comment:

"Formula: According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2+1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1)=A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence."

It seems, the last half sentence is the injectivity you are looking for, based on an explicit bound of your $f(p)$.

Further, in http://oeis.org/A066674 we find the discussion, if the two sequences above are the same, with related comments by Poonen and Bach.

There are even stronger conjectures in the literature:

1. D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.htm

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

Update: Computing the first values of least primes 1 mod p, and checking the OEIS http://oeis.org/A035095

where we find the comment:

"Formula: According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2+1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1)=A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence.

• Franklin T. Adams-Watters, Jun 18 2010"

It seems, the last half sentence is the injectivity you are looking for, based on an explicit bound of your $f(p)$.

Further, in http://oeis.org/A066674 we find the discussion, if the two sequences above are the same, with related comments by Poonen and Bach.

There are even stronger conjectures in the literature:

1. D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.html

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

There are even stronger conjectures in the literature:

1. D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.htm

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

Update: Computing the first values of least primes 1 mod p, and checking the OEIS http://oeis.org/A035095

where we find the comment:

"Formula: According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2+1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1)=A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence."

It seems, the last half sentence is the injectivity you are looking for, based on an explicit bound of your $f(p)$.

Further, in http://oeis.org/A066674 we find the discussion, if the two sequences above are the same, with related comments by Poonen and Bach.

There are even stronger conjectures in the literature:

1. D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.htm

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.

There are even stronger conjectures in the literature:

1. D.R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals. Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2079092

quoting from the first few lines: "... if $(l,k)=1$, there exists a prime $p$ satisfying $$p \equiv l \bmod k, \quad p\leq k^2, \quad (k\geq 2).$$ Indeed the bound for $p$ may presumably be reduced to $p \ll k(\log k)^2$. "

Actually, Heath-Brown unconditionally proves that there are many (i.e. the expected number) $P_2$ numbers smaller than $k^{2-\delta}$, for small $0\leq \delta \leq 0.035$. Maybe this gives a partial result for your injectivity question.

Further references:

A paper by A. Granville (Least primes in arithmetic progressions. Th'{e}orie des nombres (Quebec, 1987), 306–321, de Gruyter, Berlin, 1989) http://www.dms.umontreal.ca/~andrew/1989.html

points to an even more explicit version of a least prime conjecture: following a heuristic of Wagstaff, see http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528061-7/ , McCurley observed that this heuristic implies: $\lim\sup_{k\rightarrow \infty} \frac{p(k)}{k(\log k)^2} =2$.

A final comment: Your function $f(p)$ is (presumably) injective on the primes, but not on all integers. (Say 11 is the least prime 1 mod 10, and the least 1 mod 5). This may explain why others, possibly, did not study the question from your point of view.