analytic-number-theorynumber theoryprime numbers
It is well known and easy to prove that the smallest prime factor of an integer $n$ is at most equal to $\sqrt n$. What can be said about the largest prime factor of $n$, denoted by $P_1(n)$? In particular:
What is the probability that $P_1(n)>\sqrt n$ ?
More generally, what is the expected value of the size of $P_1(n)$, measured by $\frac{\log P_1(n)}{\log n}$ ?
A quick and dirty answer... (I began before Will answered...)
I first address the following question: what is the probability $\pi_n$ that a number has the n-th prime $p_n$ as smallest prime factor.
A random number is even with proba ${1\over 2}$, so the smallest prime factor will be 2 with probability ${1\over 2}$.
An odd number is a multiple of 3 with proba ${1\over 3}$, so the smallest prime factor will be $3$ with proba ${1\over 2\cdot 3}$.
If it is not dividable by 2 or 3, which happens with probability $1 - {1\over 2} - {1\over 6} = {1\over 3} $, this will be $5$ with proba ${1\over 5}\times{1\over 3} = {2 \over 2\cdot 3 \cdot 5}$.
Then it will be 7 with proba ${1\over 7} \times (1 - {1\over 2} - {1\over 6} - {1\over 15}) = {1\over 7} \times {4 \over 15} = {8 \over 2\cdot 3 \cdot 5\cdot 7}$.
Denoting this probability by $\pi_n$ and by $p_n$ the sequence of primes, we have $\pi_1 = {1\over 2}$ and $\pi_{n} = {1 \over p_n} \left( 1 - \sum_{i=1}^{n-1} \pi_i\right)$.
Edit I take some time to see the connection between this answer and Will’s. I compute the totient function :
$\phi(2) = 1$, $\phi(2\cdot3) = 1\cdot 2$, $\phi(2\cdot 3\cdot 5) = 1 \cdot 2 \cdot 4$. Denoting $p_n\# = \prod_{i\le n} p_i$, it appears that in the first few terms I get the following : $$\pi_n = {\phi(p_{n-1}\#) \over p_n\#},$$ which is slightly different – but Will is computing an expectation, and he is right cf edit 6 below.
Edit 2 This is logical from the definition of totient function : $\phi(p_{n-1}\#)\over p_{n-1}\#$ is the proportion numbers which are not dividable by $p_1, \dots, p_{n-1}$ ; multiply by $1\over p_n$ to get the proportion of numbers which are not dividable by $p_1, \dots, p_{n-1}$ but dividable by $p_n$.
If one manage to prove by recurrence that the above defined $\pi_n$ coincide with this, the fact that the sum is 1 should be clear.
Edit 3 It is not difficult to complete. If we prove that for all $n$, $$1 - \sum_{i\le n} \pi_i = {\phi(p_n\#) \over p_n\#},$$ we are done. This is true for $n=1, 2$. The induction step is: $$\begin{array}{rcl} 1 - \sum_{i\le n+1} \pi_i &=& \left(1 - \sum_{i\le n} \pi_i\right) - \pi_{n+1} \\ &=& \left(1 - \sum_{i\le n} \pi_i\right)\left( 1 - {1\over p_{n+1}}\right)\\ &=& \left({\phi(p_n\#) \over p_n\#} \right) \left( {p_{n+1} - 1\over p_{n+1}}\right)\\ &=& { \phi(p_n\#) \times (p_{n+1} - 1) \over p_n\# \times p_{n+1} }\\ &=& {\phi(p_{n+1}\#) \over p_{n+1}\#} \end{array},$$ so we are done.
Edit 4 Using Euler’s trick, we have easily that $$1 - \sum_{i=1}^\infty \pi_i = \prod_p \left(1-{1\over p}\right) = { 1 \over \sum_{n=1}^\infty {1\over n}} = 0,$$ which can surely be rewritten respecting the modern standards... I am not familiar with analytic number theory, but I am sure this product is a classic.
Edit 5 Yes, it is a classic, cf Merten’s third theorem, which tells that $\prod_{p\le n} \left(1-{1\over p}\right) \sim {e^{-\gamma}\over \log n}$. Using $p_n \sim n \log(n)$ we get that
$$1 - \sum_{i=1}^n \pi_i = \prod_{p\le p_n} \left(1-{1\over p}\right) \sim {e^{-\gamma}\over \log n + \log\log n} \sim {e^{-\gamma}\over \log n }$$ and $$ \pi_n \sim {e^{-\gamma}\over n \log^2 n},$$ which gives you the asymptotic behaviour of this sequence.
Edit 6 In fact I didn’t adress the original question but this is possible now. The smallest prime factor of a number taken uniformly between 1 and $p_n-1$ is $p_k$ with probability $\simeq {\pi_k \over \sum_{\ell<n}\pi_\ell}$. Its expectation is $$ { \sum_{\ell < n} p_\ell\pi_\ell \over \sum_{\ell < n} \pi_\ell} \sim \sum_{\ell < n} p_\ell\pi_\ell = \sum_{\ell < n} {\phi(p_\ell\#) \over p_\ell\#},$$ as Will first stated (oh my God, why did that took me so long?). The above equivalent shows that this goes to infinity as $n\rightarrow\infty$. Comparing to an integral leads to a $O\left( {p_n \over \log p_n} \right)$.
What you are trying to calculate is the median largest prime factor of $f(n)=n^2+1$, where $1\leq n\leq x$. This will be a function of $x$, which we denote by $M_{n^2+1}(x)$, and this will grow to infinity as $x$ grows to infinity.
To get a handle on things, lets first take a step back, and ask an easier question:
What is the median largest prime factor of the integers $n$ in the range $1\leq n\leq x$?
Let us denote this function by $M(x)$. This question was raised on Math Overflow, and I proved that we have the asymptotic $$M(x)\sim e^{\frac{\gamma-1}{\sqrt{e}}}x^{\frac{1}{\sqrt{e}}},\ \ \ \ \ \ \ \ \ \ (1)$$ where $\gamma$ is the Euler Mascheroni constant. See the corresponding paper on the arXiv for details.
So what about $n^2+1$? This seems like it must be significantly more difficult, as now we are dealing with the prime factors of a polynomial, which usually increases the complexity of a problem significantly. Modifying section $4$ of the paper I mentioned above, we can relate the problem to $$\psi_{f}(x,y)=\left|\{n\leq x:\ P(f(n))\leq y\}\right|$$ when $f(n)=n^2+1$, where $P(n)$ denotes the largest prime factor of $n$. Unfortunately, not too much is known about $\psi_f(x,y)$ when $f$ is a polynomial of degree $2$ or higher. The specific case $f(n)=n^2+1$ has been looked at by Dartyge, and Harman, where they give lower bounds on the order of magnitude for $u=\frac{\log x}{\log y}$ in a fairly small range. To obtain an asymptotic however, we would need something stronger - a precise asymptotic for $\psi_{n^2+1}(x,y)$, where $f(n)=n^2+1$, with error of size $\frac{x}{\log^2 x}$. (That is, we need to know the $\frac{x}{\log x}$ term as well) Under a major assumption, Martin proves that we do in fact have $$\psi_F(x,y)\sim x\rho\left(\frac{\log F(x)}{\log y}\right)$$ when $F$ is an irreducible polynomial, and where $\rho$ is the Dickman de Bruijn rho function. ($u=\frac{\log x}{\log y}$ will lie in a particular bounded range) Using Martin's result, and the methods I mentioned above, we are able to obtain that your quantity is $$M_{n^2+1}(x)\approx x^{2/\sqrt{e}}.$$ Note that this requires assuming a version of Hardy and Littlewood's second conjecture.
Personally, I am not entirely satisfied without an asymptotic. I believe that Martin's work can be modified to show that $$\psi_F(x,y)=x\Lambda\left(F(x),y\right)+O_F\left(\frac{x}{\log^2 x}\right)$$ for $u=\frac{\log x}{\log y}$ in a particular bounded range, and where $\Lambda(x,y)$ is a function appearing in de Bruijn's original paper on the subject. Using the expansion for $\Lambda(x,y)$ appearing in Eric Saias' 1989 paper, we would be able to recover the asymptotic
$$M_{n^2+1}(x) \sim e^{\frac{\gamma-1}{\sqrt{e}}} x^{2/\sqrt{e}}, \ \ \ \ \ \ \ \ \ (2)$$ which is very similar to equation $(1)$ above.
Moreover, I believe that given any irreducible integer polynomial $F$ of degree $d$, we have that the median largest prime factor of $F(n)$ in the interval $[1,x]$ satisfies the asymptotic $$M_F(x)\sim e^{\frac{\gamma-1}{\sqrt{e}}} x^{d/\sqrt{e}}.\ \ \ \ \ \ \ \ \ (3)$$
Under the assumptions in Martin's paper, the above outline should be able to prove that equation $(3)$ holds when the degree is less than or equal to $2$. However, additional issues arise when $d\geq 3$. Specifically, there are problems regarding the range of $u$ which I did not discuss so thoroughly above, and the previous bounds we had on $\psi_F(x,y)$ are not in a large enough range of $u$ for the proof to work.
I hope that answers your question, and that equation $(2)$ is what you are looking for.
Best Answer
Take the negation and this is a very well-known question: what is the probability that all prime factors of $n$ are $\le \sqrt{n}$? The answer is known quite generally: for any real $u\ge 1$, the probability that the prime factors of $n$ are $\le n^{1/u}$ is given by the Dickman–de Bruijn rho function, defined by a delay-differential equation. For $u=2$ we have $\rho(u) = 1-\log 2$, as in Ross Millikan's answer, but there is a very easy calculation that gives this particular case:
$$\#\{n \le x: P_1(n) > \sqrt{n}\} = \sum_{p} \#\{n \le x, n < p^2: p \mid n\} = \sum_{p\le \sqrt{x}} (p-1) + \sum_{p > \sqrt{x}} \lfloor x/p \rfloor \\ = x \log 2 + O(x/\log x),$$
where the main term comes from Mertens' theorem on $\sum_p {1/p}$ and the error terms can be deduced from the Prime Number Theorem (or Chebyshev's upper bound on $\pi(x)$).
Here, by convention, $p$ is assumed to only take prime values. The reason this is so simple is that no $n$ here can have more than one prime factor $> \sqrt{n}$.
The answer to your second question is known as the Golomb-Dickman constant. Wikipedia gives it as about $0.62433$, but I doubt anything is known about its rationality, say.