1
vote
1answer
170 views

A square-squareroot integer race sequence involving primes

I wonder what is the expected behavior of this process? Let $f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$. $g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$. Now iterate as ...
6
votes
2answers
911 views

Probability that randomly chosen integers from a restricted set of natural numbers are coprime

We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is $$ P(k) = \frac{1}{\zeta(k)}. $$ I am looking at a special case of ...
8
votes
2answers
642 views

Random pseudoprimes vs. primes

(Edit. What I called "pseudoprimes" are known as "Cramér random primes" in the literature, of which I was unaware.) Say that a set $S$ of natural numbers is a set of pseudoprimes if they are (a) ...
1
vote
1answer
335 views

Probability that p and q are both prime provided q-p=2r

Hello, I would like to know whether there is a way, thanks to the prime number theorem, to give some kind of an equivalent of the probability that two positive integers $p$ and $q$ less than a given ...
3
votes
2answers
395 views

using distribution of primes to generate random bits?

In his popular science book The Music of the Primes, Marcus du Sautoy tries to link the truth of the Riemann Hypothesis to the "randomness" of the primes. To do this, he invokes the idea of a "fair ...
12
votes
4answers
1k views

What results would follow from or imply “randomness” of the primes?

This question on random versions of deterministic problems reminded me that many conditional results in number theory hold if the primes are in some sense random, and it is common knowledge that the ...
18
votes
3answers
774 views

Can Gauss sums derandomize any heuristic arguments?

I've always been fascinated by the fact that the classical Gauss sum has absolute value $\sqrt p$, which is exactly what we would expect if we were to interpret the Gauss sum as a random walk. In ...
4
votes
2answers
436 views

What does the probabilistic model suggest the error term in the PNT should be?

Let $\Lambda(n)$ be the von Mangoldt function. The prime number theorem is equivalent to the statement that $\sum_{n \leq N} \Lambda(n) \approx N$. Defining $\lambda_{*}(n)= \Lambda(n)-1$ we may ...
10
votes
6answers
924 views

Density of numbers having large prime divisors (formalizing heuristic probability argument)

I want to prove that the set of natural numbers n having a prime divisor greater than $\sqrt{n}$ is positive. I have a heuristic argument that this density should be $\log 2$, which is approximately ...
5
votes
6answers
1k views

Primes are pseudorandom?

I've been reading the wonderful slides by Terry Tao and thought about this question. Primes appear to be quite random, and the formal statement should be that there are some characteristics of primes ...