4
$\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$
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$
  • $\begingroup$ btw $\frac{1270000^{16384}+1}{148894375444481}$ is a $99,991$ digit composite number. $\endgroup$ – Martin Hopf Oct 13 '18 at 9:20
  • $\begingroup$ Well done! (+1) $\endgroup$ – Peter Oct 17 '18 at 16:56
4
$\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
    $\begingroup$ A really good answer! $\endgroup$ – Peter Sep 29 '15 at 10:50

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.