5
$\begingroup$

The number $N\ :=\ 1270000^{16384}+1$ with $100,005$ digits is given.

Given, that $N$ is composite and does not have a prime factor below $2\times 10^{13}$, what is the expected number of digits of the smallest prime factor ?

On factordb, I checked, that N is composite and I searched a prime factor upto about $2\times 10^{13}$ without finding one.

I wonder, how likely it is, that the search is still unsucessful, if I continue to, lets say, $10^{18}$. If the number had no special form, the probablity that there is no prime factor below $10^{26}$, would be about $\frac{1}{2}$, but the situation should be different for $N$ because every prime factor $p$ must be of the form $2^{15}k+1$

If someone wonders, how I arrived to this number. I sieved out the factors of $k\times 1270000^{16384}+1$ and the program skipped $k=1$, I thought the reason would be that $N$ has a small prime factor, which is not the case.

The $1270000$ comes from rounding up the smallest number $n$, such that $n^{16384}$ has more than $100,000$ digits.

$\endgroup$

2 Answers 2

5
$\begingroup$

This is all a bit hand-wavy; someone else may be able to make it more rigorous, but perhaps it's enough for your practical purposes. I'll be fudging lower limits of integrals that start near $1$ because I'm not sure how to treat them correctly, so take everything with a grain of salt – but the orders of magnitude should be correct.

In Cramér's random model of the primes, the "probability" $\frac1{\log x}$ of a number $x$ being prime can be roughly thought of as the probability that a Poisson process with density $\frac1{y\log y}$ (corresponding to the density $\frac1{\log y}$ of primes below $x$ and the "probability" $\frac1y$ of a prime $y$ dividing $x$) contains no events below $\sqrt x$:

$$ \exp\left(-\int_{\sqrt{\mathrm e}}^\sqrt x\frac1t\frac{\mathrm dt}{\log t}\right)=\exp\left(-\log\log\sqrt x-\log2\right)=\frac1{\log x}\;, $$

where the lower limit is chosen to make the factor come out right. Now let $A_y$ be the event that $x$ has no prime factor less than $y$, and $E$ the event that $x$ has a prime factor (i.e. is composite). Then

$$ P(A_y)\approx\exp\left(-\int_{\sqrt{\mathrm e}}^y\frac1t\frac{\mathrm dt}{\log t}\right)=\frac1{2\log y} $$

and

$$ P(A_y\mid E)=\frac{P(A_y \cap E)}{P(E)}\approx\frac{\frac1{2\log y}-\frac1{\log x}}{1-\frac1{\log x}}\;. $$

Conditioning on the event $A_z$ that there is no prime factor below $z=2\cdot10^{13}$ yields

$$P(A_y\mid A_z\cap E)=\frac{P(A_y\cap A_z\cap E)}{P(A_z\cap E)}=\frac{P(A_y\cap E)}{P(A_z\cap E)}=\frac{\frac1{2\log y}-\frac1{\log x}}{\frac1{2\log z}-\frac1{\log x}}\approx\frac{\log z}{\log y}=\log_y z$$

for $y\ge z$, and $P(A_y\mid A_z\cap E)=1$ for $y\le z$. The expected number of decimal digits of the least prime factor is then roughly

\begin{align} \frac1{\log10}\int_{\frac12}^{\frac12\log x}\mathrm d\log yP(A_y\mid A_z\cap E) &\approx \frac1{\log10}\int_{\frac12}^{\frac12\log x}\mathrm d\log y\frac{\frac1{2\log y}-\frac1{\log x}}{\frac1{2\log z}-\frac1{\log x}}\\ &\approx\frac1{\log10}\frac{\frac12\log\left(\frac12\log x\right)-\frac12}{\frac1{2\log z}-\frac1{\log x}}\\ &\approx\frac1{\log10}\log z\log\left(\frac12\log x\right)\;. \end{align}

Thus, if the number where an "ordinary" number, the check up to $z$ would have increased the expected number of decimal digits from roughly $2.5$ to roughly $155$.

To take into account that the number under consideration can only be divisible by primes of the form $2^{15}k+1$, we can reduce the density of the Poisson process by some factor $\rho$. I'm not sure how this factor should be chosen; I'm not sure we can just say that it's $2^{-15}$, since the number might have a systematically higher "probability" of being divisible by primes of the form $2^{15}k+1$. So I'll just do the calculation with some factor $\rho$ and leave it to you to choose.

Wherever we had $\frac1{\log x}$, we now have to replace it by $\left(\frac1{\log x}\right)^\rho$. For the expected number of digits of the least prime factor, this yields

\begin{align} \frac1{\log10}\int_{\frac12}^{\frac12\log x}\mathrm d\log yP(A_y\mid A_z\cap E) &\approx \frac1{\log10}\int_{\frac12}^{\frac12\log x}\mathrm d\log y\frac{\left(\frac1{2\log y}\right)^\rho-\left(\frac1{\log x}\right)^\rho}{\left(\frac1{2\log z}\right)^\rho-\left(\frac1{\log x}\right)^\rho}\\ &\approx \frac1{\log10}\frac{-\frac1{2(\rho-1)}\left(\frac1{\log x}\right)^{\rho-1}-\frac12\left(\frac1{\log x}\right)^{\rho-1}}{\left(\frac1{2\log z}\right)^\rho-\left(\frac1{\log x}\right)^\rho}\\ &= \frac1{2\log10}\frac\rho{1-\rho}\frac{\left(\frac1{\log x}\right)^{\rho-1}}{\left(\frac1{2\log z}\right)^\rho-\left(\frac1{\log x}\right)^\rho}\;, \end{align}

which for $\rho=2^{-15}$ comes out to roughly $6074$ (Wolfram|Alpha calculation). For $\rho\ll1$, we can take the limit $\rho\to0$, using L'Hôpital's rule to obtain

$$ \frac{\log_{10} x}2\frac1{\log\log x -\log(2\log z)}\approx6074\;. $$

The corresponding value without checking up to $z$ would have been roughly $4050$.

To answer your other question, the "probability" that there is no prime factor below $y=10^{18}$ (given the check up to $z$ and that $x$ is composite) would be roughly

$$ \frac{\log z}{\log y}=\frac{\log\left(2\cdot10^{13}\right)}{\log10^{18}}\approx74\% $$

for an "ordinary" number, but with the reduced density it is roughly

$$ \frac{\log\log x-\log(2\log y)}{\log\log x-\log(2\log z)}\approx96\%\;. $$

Before the check up to $z$, your chances of finding a prime factor below $y=10^{18}$ were roughly

$$ \frac{\log(2\log y)}{\log\log x}\approx36\%\;. $$

$\endgroup$
1
  • 1
    $\begingroup$ A really good answer! $\endgroup$
    – Peter
    Sep 29, 2015 at 10:50
1
$\begingroup$

The smallest prime factor of $ N := 1270000^{16384} +1$ consits of $15$ decimal digits.

$4543895735 \cdot 2^{15}+1 = 148894375444481$ is a factor of $N$.

I found it today with a self written Pari/GP script and added it to factordb.com.

$\endgroup$
2
  • $\begingroup$ btw $\frac{1270000^{16384}+1}{148894375444481}$ is a $99,991$ digit composite number. $\endgroup$ Oct 13, 2018 at 9:20
  • $\begingroup$ Well done! (+1) $\endgroup$
    – Peter
    Oct 17, 2018 at 16:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .