Let $f(n)$ be the largest prime factor of $n$. The image of function $g(n)=\sqrt{f(n^2+1)}$ is like this:

enter image description here

Question: If we want to draw a horizontal line which bisects the points from $n=1$ to $n=x,$ this line is probably in what position when $x\to \infty$?

The first thing we can find on the image is that there are many approximate straight lines.

Then what's the slope of these straight lines?

I find that the slope of the most inclined straight line is $1,$ hence the equation is $y=x.$ The second line is $y=\dfrac{x}{\sqrt2},$ the third is $y=\dfrac{x}{\sqrt5},$ then $y=\dfrac{x}{\sqrt{10}},$ then $y=\dfrac{x}{\sqrt{13}}.$

$\dfrac{1}{\sqrt{m}}$ can be a slope if and only if $a^2+1\equiv 0\pmod m$ has integer solution.

In fact, the point $(n,\sqrt{f(n^2+1)})$ on $y=x$ means $g(n)\approx n$ hence $n^2+1$ is prime. $y=\dfrac{x}{\sqrt2}$ means $g(n)\approx \dfrac{n}{\sqrt2}$ hence $2\mid n^2+1$ and $\dfrac{n^2+1}{2}$ is prime $\dots$

Whether there are infinity many primes of the form $n^2+1$ is still an open problem. So we can not prove these conclusions, but we can estimate it.

  • $\begingroup$ I think you are asking for $c=c(x)$ such that the number of $n\le x$ with $g(n)\lt c$ is $n/2$. Have you tried tabulating $c(x)$ for $1\lt x\le10000$ to see what it looks like? $\endgroup$ – Gerry Myerson Jun 25 '13 at 12:51

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.

| cite | improve this answer | |

Here's some non-optimized code

prim = Table[First[Last[FactorInteger[n^2 + 1]]], {n, 1, 100000}];   
ListPlot[Table[With[{temp = Sort[Take[prim, 2 k]]}, (temp[[k]] + temp[[k + 1]])/2], 
  {k, 2, 20000}]]

That leads to the following picture. I'd say that's too irregular to predict long-term behavior.
enter image description here

EDIT -- I was multiplying by 2, twice, which skewed the values. Here's better code.

prim = Table[First[Last[FactorInteger[n^2 + 1]]], {n, 1, 100000}];  
sortedprimes = {};   
vals = {};   
  addprime = Sort[{prim[[k - 1]], prim[[k]]}];
  sortedprimes = Sort[Join[sortedprimes, addprime]];
  newval = (sortedprimes[[k/2]] + sortedprimes[[k/2 + 1]])/2;
  vals = Append[vals, newval],
  {k, 2, 100000, 2}],
ListPlot[Transpose[{Range[50000] 2, vals}]]

Gives the following picture

enter image description here

We can try fitting the data in various ways. Fitting to $A x + B x/log(x)$ didn't immediately go bad when more terms were added.

ListPlot[{#[[1]], #[[2]] - (25.1 #[[1]] - (185.1 #[[1]])/
   Log[#[[1]]])} & /@ Transpose[{Range[50000] 2, vals}]]

Leading to the picture

enter image description here

| cite | improve this answer | |
  • 1
    $\begingroup$ I am not sure if your data is accurate. The median largest prime factor of $n^2+1$ on the interval $[1,10000]$ is $55287$, whereas your graph suggests that it is close to $150 000$. $\endgroup$ – Eric Naslund Jun 27 '13 at 0:37
  • $\begingroup$ I corrected the code. $\endgroup$ – Ed Pegg Jun 27 '13 at 4:18
  • $\begingroup$ Looks good now. Try best fitting with the function I mention in my answer, $$e^{(\gamma-1)/\sqrt{e}}\cdot x^{2/\sqrt{e}}.\ \ \ \ \ \ \ \ (2)$$ Numerically, this is $$\approx 0.773808\cdot x^{1.21306}.$$ The error between this and the true value should be strictly less than the main term multiplied by $\frac{1}{\log x}$. At $x=10000$, the true value is $55287$, and the estimate above, equation $(2)$, gives $55065$, which is an error of $222$. $\endgroup$ – Eric Naslund Jun 27 '13 at 19:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.