21
$\begingroup$

$ 343,~ 34343, ~3434343, ~343434343,\ldots$

$\begin{array}\\ \color{Red}{343} &\color{Red}{: 7^3}\\ 34343 &: 61\times 563\\ \color{green}{3434343} &\color{green}{: 3\times 11^2\times 9461}\\ \color{red}{343434343} &\color{Red}{: 7\times 521\times 94169}\\ 34343434343 &: 47\times 79\times 9249511\\ \color{green}{3434343434343} &\color{green}{: 3^2\times 19\times 29\times 67\times10336531}\\ \color{red}{343434343434343} &\color{Red}{: 7\times 151\times 324914232199}\\ 34343434343434343 &: 5638147\times 6091262669 \end{array}$

Update: The numbers in black are,

$$F_n = \frac{34\times10^{6n-1}-43}{99}$$

and $F_n$ is composite for $n<1667$ (user Uncountable) and $n<3101$ (user A.P.).

$\endgroup$
  • 3
    $\begingroup$ It's easy to prove that one third of the numbers are divisible by 3, and another third are divisible by 7. $\endgroup$ – gnasher729 Feb 21 '15 at 23:23
  • 2
    $\begingroup$ It's only the black ones that are of interest. $\endgroup$ – Brian M. Scott Feb 21 '15 at 23:25
  • 1
    $\begingroup$ Where did you find the problem?????? $\endgroup$ – Will Jagy Feb 21 '15 at 23:41
  • 1
    $\begingroup$ The black numbers are of the form $(34\times10^n+43)/99$ where $n$ is of the form $6r-1$. That doesn't solve the problem, but it gives you a more convenient form for the numbers. $\endgroup$ – Gerry Myerson Feb 21 '15 at 23:45
  • 2
    $\begingroup$ It's worth noting that since this sequence is exponential, it satisfies a linear recurrence relation with constant coefficients, and so some of the tools that have been applied to those sequences might be applicable here. See math.stackexchange.com/questions/1090319/… for an example. $\endgroup$ – Steven Stadnicki Feb 22 '15 at 0:22
7
+50
$\begingroup$

We have $343434 = 2 \times 3 \times 7 \times 13 \times 17 \times 37$. $34343$ is not divisible by any of these numbers. Therefore the subsequence $34343$, $34343 + 343434 \times 10^5$, $34343 + 343434 \times 10^5 \times (10^0 + 10^6)$, $34343 + 343434 \times 10^5 \times (10^0 + 10^6 + 10^{12})$, $34343 + 343434 \times 10^5 \times (10^0 + 10^6 + 10^{12} + 10^{18})$ etc. consists of numbers which are not divisible by $2, 3, 5, 7, 13, 17, \quad \text{or}\quad 37$.

Heuristically, the chance of a random number $N$ being prime is $1 / \ln N$. Having $7$ small primes excluded as possible factors increases the chances by a factor $(2/1)(3/2)(5/4)(7/6)(13/12)(17/16)(37/36) ≈ 5.1757$.

The numbers are around $3.4343 \times 10^{5+6k}$ with $k = 0, 1, 2, 3,\ldots$ The natural logarithm is about $13.8155k + 10.4442$. So the chance that each of the numbers is a prime is about $5.1757 / (13.8155k + 10.4442)$. The expected number of primes among the numbers for $k = 0$ to $n$ is about $0.3746 \cdot\ln (n) + 0.4013$. For $n = 1,666$ the expected number of primes is about $3.1803$; that's the range that Uncountable checked. So finding no primes is slightly unlucky, but not that unlikely.

For a $50\%$ chance of finding a prime, the expected number of primes needs to increase by $\ln 2 ≈ 0.6931$, so $\ln n$ needs to be increased by $0.6931/0.3746 ≈ 1.8502$, $n$ needs to be multiplied by $6.36$. So there's a $50\%$ chance of finding a prime with up to $63,600$ digits; then a $50\%$ chance for a prime with up to $404,000$ digits and so on.

Of course all that is just heuristic. If it is correct, then a prime will almost certainly exist. Finding a probable prime might be very hard. If checking a range that gives a $50\%$ chance fails, the next range giving a $50\%$ chance is $6.36$ times larger. Miller-Rabin test grows more than quadratic with the number of digits, and there are more numbers to test, so the next range takes more than $6.36^3 = 257$ times longer.

$\endgroup$
  • $\begingroup$ Can you look at this similar question and give a comment why $7373737373737\dots$ has prime values for $n=3,\,7,\,95,\,422,\dots$. $\endgroup$ – Tito Piezas III Apr 17 '15 at 5:37

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.