4
$\begingroup$

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)
$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ The set $S(3k+1)$ is not quite arithmetically random because it excludes multiples of 3. (In fact all its elements are congruent mod 9, but this additional constraint does not change the expected count of primes.) Therefore the density of primes in $S(3k+1)$ should be about 3/2 times that of a random set of integers of the same size. $\endgroup$ Jul 1, 2022 at 1:52
  • $\begingroup$ Right! I thought that being constrained in a particular arithmetic class does not change the density of primes. But, indeed, since we are excluding multiples of $3$, we have to take into account we discarded a good amount of bad numbers. $\endgroup$ Jul 1, 2022 at 13:31
  • $\begingroup$ Thanks @AndreaMarino! Although I am not sure if in your reasoning you have taken into account that leading zeros are allowed. I guess this could have some impact on your estimation;, however, I am not sure about how to evaluate it... $\endgroup$ Jul 5, 2022 at 14:43
  • $\begingroup$ I am not sure I follow you. Which estimation, and where leading zeros should be allowed? Thanks! $\endgroup$ Jul 6, 2022 at 15:12
  • $\begingroup$ Consider, for instance, $S(10)$. A permutation with no leading zeros will have $11$ digits, whereas a permutation with a leading zero will have $10$ digits. For big numbers, this could lead to enormous differences (as big as the number of zeros which are digits of integers less than $n$) in the number of digits among permutations of the same set $S(n)$ $\endgroup$ Jul 6, 2022 at 22:01
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thanks for your answer; however, I am not sure in what sense it does address any of the questions asked... $\endgroup$ Jul 5, 2022 at 16:26
  • $\begingroup$ Maybe a very basic idea in order to guess if your asymptotic conjecture holds can be to check if |P(n)|, for small given values of n that you have already considered in your tests, is consistent with the percentage of primes in the given range, by considering all the integers having the same number of digits as 1_2_..._n. Now, let 10^(k-1) < 1_2_..._n < 10^k. Here you have to consider that there are less distinct elements belonging to the set of the digital permutations of 1_2_..._n than k!, since numbers as 1112345678910 can be sorted out as 1_11_2_3_4_5_6_7_8_9_10 or 11_1_2_3_4_5_6_7_8_9_10 $\endgroup$ Jul 6, 2022 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.