Prime numbers made of permutations of digits of consecutive positive integers

Question

I posted this question in MSE some weeks ago and got no answer to any of the questions, so I post it here to see if someone could help.

Following the spirit of this question, I developed a program to check how many permutations of the digits of consecutive positive integers from $1$ to $n$ were prime numbers (allowing leading zeros). For instance, if we call $S(3)$ the set of different permutations of the digits of consecutive positive integers from $1$ to $3$, $S(3)=\{123,132,213,231,312,321\}$.

For similar reasons to the ones exposed in this partial answer I gave to the question cited, $S(n)$ contains no prime number for $n\neq 3k+1$, as the sum of digits of any permutation in some set $S(3k)$ is divisible by $3$ (and by divisibility criteria it follows that such permutation is divisible by $3$ too), and this in turn implies divisibility by $3$ of any permutation in some set $S(3k-1)$.

Therefore, I have focused only on the sets $S(3k+1)$. Let us call $P(n)$ the subset made of permutations of $S(n)$ that are prime numbers. I found that $$|P(4)|=4$$ $$|P(7)|=534$$ $$|P(10)|=2808500$$

I have not been able to calculate the cardinality of more sets $P(3k+1)$, as my computer runs out of memory for bigger sets (it has to check $(3k+1)!$ numbers!). However, I have come up to the following

Conjecture

Let $D(3k+1)$ count the number of digits of consecutive positive integers from $1$ to $3k+1$. Then,

$$\lim_{k\to \infty}\frac{(D(3k+1)-1)!}{|P(3k+1)|}=1$$

It is a "bold" conjecture, as I only have three data to support it: $$\frac{(D(4)-1)!}{|P(4)|}=1.5$$ $$\frac{(D(7)-1)!}{|P(7)|}=1.34$$ $$\frac{(D(10)-1)!}{|P(10)|}=1.292$$

It would be great (i) to have more data that helps to strengthen (or discard) the conjecture, (ii) to have an insight on the reasonability (or not) of it, and (iii) of course, if there is some literature on the subject, more than glad to hear of it!

Thanks in advance!

EDIT

I share the Python code I have used to calculate $|P(3k+1)|$ for $k<4$, in case someone with more computational power than mine could calculate it for bigger values of $k$:

import itertools
import functools

from sympy import isprime

i=10

list = []

def get_digit(i):
    if i < 10:
        list.append(i)
    else:
        get_digit(i // 10)
        list.append (i % 10)

for j in range(1, i+1):
    get_digit(j)
    
def prime_permutations(i):
    l = itertools.permutations(list)
    n_primos=0
    for x in l:
        number = int(functools.reduce(lambda sub, ele: sub * 10 + ele, x))
        if isprime(number)==True:
            n_primos = n_primos+1
            print(number)
    print("El número de primos en permutaciones de", i, "elementos es", n_primos)       

prime_permutations(i)

Answer 1

My impression is that the prime numbers in $S(3k+1)$ are exactly in the proportion they should be. Note that numbers in $S(3k+1)$ are smaller than $10^{D(3k+1)-1}$ because they have $D(3k+1)$ digits.

By the prime number theorem, primes up to $10^{D(3k+1)-1}$ are in proportion $1/(D(3k+1)-1)\log(10) $. In the subset $S(3k+1)$, which seems "arithmetically random", I would expect the same proportion, that is $$|P(3k+1)| \sim \frac{|S(3k+1)|}{(D(3k+1)-1)\log(10)} \ \ \ \ :NO:$$ But hey (thanks Noam D. Elkies), we have to remember such numbers are never multiples of $3$. This is the only "easy" constraint we have. Taking into account this fact, there is a factor $3/2$ to take into account $$ |P(3k+1)| \sim \frac{3|S(3k+1)|}{2(D(3k+1)-1)\log(10)}$$ The factor is explained in an edit at the end.

(EDITED) We are left with estimating $S(3k+1)$. We have $D(3k+1)$ digits, and it's not hard to see that are almost equally distributed among the ten possible digits. There is indeed a bias, but I will neglect it (see below). The permutations of $D(3k+1)$ things divided in 10 equal groups is $$\frac{ D(3k+1)!}{ \left ( \frac{ D(3k+1)}{10} \right ) !^{10} } $$ Using the complete stirling approximation, after a few calculations we get $$ \frac{10^{D(3k+1)+5}}{ (2 \pi D)^{9/2} )}$$ Since about $1/10$ of the numbers will start with $0$, we get in the end $$ S(3k+1) \sim \frac{10^{D(3k+1)+4}}{ (2 \pi D)^{9/2} }$$ Let's get back to estimate $P(3k+1)$. We have $$|P(3k+1)| \sim \frac{3}{2} \cdot \frac{10^{D(3k+1)+4}}{ (2 \pi D(3k+1) )^{9/2} ( D(3k+1) -1) \log(10)}$$ I think this is the "naive guess", but actually it is not consistent with yours.

Now let's estimate $D(n)$. Since a number $\ell \le n$ has about $\log_{10}(\ell)$ digits, we have $$D(n) \sim \sum_{\ell = 0}^{n}\log_{10}(\ell) = \frac{ \log ( n!)}{ \log(10) } $$ Using the Stirling approximation $$ D(n) \sim \frac{ \log(n!) }{ \log(10) } \sim \frac{n \log(n) }{ \log(10)} = n \log_{10}(n)$$ If we plug the Stirling approximation for $D(n)$ into the estimate above we get $$|P(m)| \sim \frac{10^{m \log_{10}(m) +4}}{ (2 \pi)^{9/2} (m \log_{10}(m) )^{11/2} \log(10)}$$ $$|P(m)| \sim \frac{ 3 \cdot 10000}{ 2 \cdot ( 2 \pi)^{9/2} \cdot \log(10) }\frac{m^{m-\frac{11}{2} }}{ \log_{10}(m)^{11/2}}$$ $$|P(m)| \sim 1.667 \cdot \frac{m^{m-\frac{11}{2} }}{ \log_{10}(m)^{11/2}}$$

I would be curious to see how this performs!

EDIT The factor $3/2$ can be explained in this way. Call $A(j)_{\le x}$ the subset of numbers congruent to $j$ modulo $3$ smaller than $x$, for $j=0,1,2$. If we have $m$ primes in $A(0)_{\le 3x} \sqcup A(1)_{\le 3x} \sqcup A(2)_{\le 3x} $, then the primes up to $3x$ are $m/3x$, while the primes up to $3x$ in $A(1)_{\le 3n} \sqcup A(2)_{\le 3n}$ are $$\frac{m}{2x} = \frac{3}{2} \cdot \frac{m}{3x}$$ Thus the density in $A(1)_{\le 3x} \sqcup A(2)_{\le x}$ is (as the intuition suggests) higher, and there is precisely a factor of $3/2$. Also, by the extended prime number theorem, $A(1)_{\le 3x}$ and $A(2)_{\le 3x}$ have approximately the same number of primes. This means $A(1)_{\le 3x}$ contains about $m/2$ primes, resulting in a density of $$\frac{m/2}{x} = \frac{m}{2x} = \frac{3}{2} \frac{m}{3x}$$ Explaining the factor.

BIAS. If $(3k+1)$ is for example $2002$, one thousand the numbers will start with $1$, so there will be a relative abundance of $1$. Here $D(2002) \sim 8000$ so each digit should appear $800$ times, but instead the digit $1$ appears $1000$ of times + $D(999)/10 \simeq 400$, while the other digits appear a little less than $800$ times.

Answer 2

We knows that no prime of the form $1\_2\_...\_n$ has been found yet... at least for $n$ up to $10^6$ (see https://mathworld.wolfram.com/SmarandachePrime.html).

Now, a partial answer to your question is given by OEIS, see sequences $A176942$ and $A071620$, while the list of the first $31$ primes of the requested form was given by me in 2011 (see https://vixra.org/pdf/1101.0092v2.pdf, pages 6 to 8), and they are listed in the OEIS sequence $A181129$.

Lastly, it is interesting to note that an efficient sieve criterion, able to efficiently skim the composite terms of the OEIS sequence $A001292$, is described in my article Ripà M. (2012), "Patterns related to the Smarandache circular sequence primality problem", Notes on Number Theory and Discrete Mathematics, vol. 18(1), pp. 29-48.