4
$\begingroup$

Consider $\lfloor 10^n \times 0.731926765612646213686753345587262244668218433356357832021 \rfloor$. For each $n$, reverse the digits. If the number isn't already prime, find the next prime.

For the first 24 values of $n$, the result is prime. This start is based on the record left-truncatable prime 357686312646216567629137.

After that, one must add the following values to get a prime number $(12, 0, 16, 2, 12, 20, 2, 2, 0, 14, 0, 2, 12, 6, 6, 10, 10, 10, 16, 12, 10, 4, 14, 2, 10, 12, 2, 0, 2)$

All values bounded above by 20. If this could go on (it doesn't), it would provide a solution for the finding primes Polymath project. How far can something like this be extended for a given upper bound? For $n$ going from 1 to 100, what constant minimizes the farthest distance to the corresponding 1 to 100 digit prime?

A similar question -- what constants work best without the reverse-digits step? For upper bound 0, $\lfloor 10^n \times .73939133 \rfloor$ could be used to produce primes for $n=1..8$. How far could this be extended with an upper bound of 10?

Is the following provable?
For any $0<k<1$ and any positive integer $d$ there exists an $n$ such that the following values are composite.
$$\lfloor 10^n \times k \rfloor, \lfloor 10^n \times k \rfloor+1, ..., \lfloor 10^n \times k \rfloor +d$$

Added results.
Prime to $n=31$, $\lfloor 10^n \times .19992191983120858559939829 \rfloor$ + $(1, 0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 0, 2, 0, 2, 2, 1, 1, 2)_n$

Prime to $n=43$, $\lfloor 10^n \times .2249916676947644237216638216097398882368887 \rfloor$ + $(0, 1, 3, 2, 2, 2, 1, 1, 0, 1, 0, 3, 2, 1, 3, 3, 1, 0, 2, 1, 0, 3, 3, 0, 1, 1, 0, 1, 1, 0, 2, 0, 0, 3, 1, 3, 1, 0, 1, 1, 3, 1, 0)_n$

Reverse prime to $n=50$, $\lfloor 10^n \times .79946519968197358169933425438229277782582723528486 \rfloor$ + $(0,0,0,2,0,0,2,0,0,0,0,2,2,2,2,2,0,0,0,0,0,0,0,2,2,0,0,2,0,2,2,2,0,2,2,0,2,0,0,2,0,2,2,2,0,2,2,2,0,0)_n$

Reverse prime to $n=64$, $\lfloor 10^n \times .1319788512835399616489432175746323115633163831863127383662373426 \rfloor$ + $(1,0,0,2,2,2,0,2,0,2,2,2,0,0,0,0,0,2,0,2,0,2,2,2,2,2,0,2,0,2,0,0,0,0,0,8,8,6,8,6,2,8,8,0,8,2,0,6,8,2,8,2,8,0,6,6,0,0,6,8,6,8,0,2)_n$

$\endgroup$
1
  • $\begingroup$ For the last question, it's true for all $d$ if $k$ is algorithmically random. If $\lfloor 10^n \cdot k + d \rfloor$ is prime, then we can compress the first $n$ digits of $k$ to a $(n-log(n)+c)$-digit description by referring to it by its index in the set of all primes. $\endgroup$ Sep 30, 2015 at 0:54

1 Answer 1

4
$\begingroup$

This is a more detailed version of my comment.

Given $k \in (0,1)$ and $d \in \mathbb{N}$, suppose for all $n \in \mathbb{N}$ there exists a $d_n \in \mathbb{N}$, $0 \le d_n \lt d$, such that $x_n = \lfloor 10^n \cdot k + d_n \rfloor$ is prime.

Lemma: For all $a \gt a_0$, there exists $n$ such that $\lceil \log_{10}(\pi(x_n)) \rceil = a$. In other words, we can always find a prefix of $k$ in base-$10$ of length $n$, add $d_n$ to it, and get a number $x_n$ such that the number of primes less than it has exactly $a$ digits. This can be proved with the prime number theorem.

Now consider $a$ with $a \gt a_0$ and $a = 10^b$ for some $b$, and let $n$ be determined by the lemma. Let $c = \pi(x_n)$. By the prime number theorem:

$\log_{10}(c) = \log_{10}(\frac{x_n}{\log(x_n)}) + O(1) = n - \log_{10}(n) + O(1)$

Also note that:

$\log_{10}(b) = \log_{10}(\log_{10}(n)) + O(1)$

From $b$ we can compute $a$ (the number of digits in $c$), so we can design a prefix-free encoding of $c$ requiring $n - \log_{10}(n) + O(\log_{10}(\log_{10}(n)))$ digits. This leaves room for the constant-sized machinery necessary to compute $x_n$ from $c$ and subtract $d_n$, resulting in the first $n$ digits of $k$, so given any $z$, for sufficiently large $b$ this prefix-free encoding will require fewer than $n-z$ digits. Therefore $k$ is not algorithmically random.

$\endgroup$
3
  • $\begingroup$ I think I like it. Can you apply this proof to my bound 2 example, and give some range of $n$ where a failure would occur? $\endgroup$
    – Ed Pegg
    Oct 1, 2015 at 16:45
  • $\begingroup$ This proof also works if you allow $d$ to grow slowly with $n$, for example $d = \log_{10}(n)$. $\endgroup$ Oct 1, 2015 at 17:48
  • $\begingroup$ If we fix a particular value of $z$ in the argument above, so that $k$ is assumed to have no prefix that can be compressed by more than $z$ digits (Chaitin's constant for example can be characterized this way, $z$ is just the size of a program that can solve the halting problem for programs shorter than $n$ using a length $n$ prefix of it), and assuming we know at least a few of the leading digits of $k$ in order to resolve the $O(1)$ term in the application of the PNT, then it looks like we can find a specific value of $n$ so that all numbers near $\lfloor 10^n \cdot k \rfloor$ are composite. $\endgroup$ Oct 3, 2015 at 17: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.