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$
16
  • 4
    $\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, 2015 at 23:23
  • 3
    $\begingroup$ It's only the black ones that are of interest. $\endgroup$ Feb 21, 2015 at 23:25
  • 1
    $\begingroup$ Where did you find the problem?????? $\endgroup$
    – Will Jagy
    Feb 21, 2015 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$ Feb 21, 2015 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$ Feb 22, 2015 at 0:22

1 Answer 1

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$
1
  • $\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$ Apr 17, 2015 at 5:37

You must log in to answer this question.

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