I have been toying for a while with the study of: in how many distinct primes and of which size can we divide permutations of digits of the first positive integers?
In this post I studied how many permutations of the digits of consecutive positive integers from $1$ to $n$ were prime numbers (allowing leading zeros). There I found some restrictions; for instance, if we call $S(n)$ the set of different permutations of the digits of consecutive positive integers from $1$ to $n$, by divisibility criteria $n$ must be of the form $3k+1$ to have permutations of the digits of consecutive positive integers from $1$ to $n$ that are prime numbers.
In this second post I take a step further, and ask about the possibility of always having some permutation of the digits of consecutive positive integers from $1$ to $n$ (from now on, $p_{i}(n)$) such that it can be divided into blocks of digits such that each block forms some prime number.
As a result of the comments, the broader (and more interesting) question stated at the beginning of this post came to my mind. in how many distinct primes and of which size can we divide permutations of digits of the first positive integers?
Regarding maximum size of some block of digits of some permutation being a prime number (from now on, $M_{s}B_{j}p_{i}(n)$), the first post cited establishes the restriction cited, so if we denote as $D(n)$ the number of digits of consecutive positive integers from $1$ to $n$, at most we have $M_{s}B_{j}p_{i}(n)\leq D(n)-1$ for any $p_{i}(n)$ such that $n\neq 3k+1$, and numerical evidence shows that $M_{s}B_{j}p_{i}(n)= D(n)$ for many $p_{i}(n)$ such that $n=3k+1$. I have not been able to derive other bounds on this angle of the problem, but this suggests that $M_{s}B_{j}p_{i}(n)$ shall be close to $D(n)$.
Regarding the maximum number of blocks of distinct primes, I found surprising that really tight bounds on the number of blocks can be (in principle) conjectured. For instance, using the Python program below, I have been able to check that if we restrict the size of the blocks to be $M_{s}B_{j}p_{i}(n)\leq \lfloor\log(n)\rfloor$ the program finds permutations and sets of blocks of digits such that each block forms some distinct prime number for $n\leq 13$ (the program takes so much time for bigger values of $n$). Currently, I have no clue on how sharp could this bound be, or if it is clearly false for bigger values of $n$.
I guess that some statistical study on the ocurrence of digits in the first prime numbers could be helpful, comparing it to the ocurrence of digits in the first consecutive positive integers, to get more insight on the possible restrictions to size and number of prime numbers in which permutations of the first consecutive positive integers can be divided.
Questions
Can you share some helpful references, or insight (teorical or heuristical) to this problem? Do you find it interesting enough to continue researching? Can you share some advice on how to improve the Python program, or an alternative, to check bounds for bigger values of $n$?
Thanks in advance!
Python program for checking bounds
@author: juanmoreno
"""
import itertools
import math
def is_prime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
return False
return True
def find_smallest_blocks(perm_str, log_n, max_block_size, current_blocks, all_blocks):
if len(perm_str) == 0:
if all_blocks is None or len(current_blocks) < len(all_blocks):
return current_blocks
return all_blocks
for size in range(1, min(max_block_size, len(perm_str)) + 1):
block = perm_str[:size]
if is_prime(int(block)):
new_blocks = current_blocks + [block]
result = find_smallest_blocks(perm_str[size:], log_n, max_block_size, new_blocks, all_blocks)
if result is not None:
all_blocks = result
return all_blocks
def find_permutation(n):
digits = list(range(1, n+1))
log_n = math.floor(math.log(n))
max_block_size = log_n
while True:
for perm in itertools.permutations(digits):
perm_str = ''.join(map(str, perm))
blocks = find_smallest_blocks(perm_str, log_n, max_block_size, [], None)
if blocks:
print(f"Valid permutation found: {perm_str} => Blocks: {blocks}")
return
# Generate next permutation
next_permutation = list(itertools.permutations(digits))
if next_permutation:
digits = list(next_permutation[0])
else:
break
print("No valid permutation found.")
if name == "main":
n = int(input("Enter a positive integer n: "))
find_permutation(n)
