Take the first $n$ integers, and concatenate them to form the $n_{th}$ Smarandache number. Then, I have the following
Conjecture
For $n>2$, the digits of each Smarandache number can be rearranged in blocks of digits, such that each block forms some prime number.
For instance, consider $n=1234$; it can be rearranged as $2341$, with blocks $23$ and $41$, which are both prime numbers. The blocks could also be $2$, $3$ and $41$. It can be expected an increasing number of ways to form blocks as $n$ grows.
I have written a Python program to check the validity of the conjecture, but it seems to be too slow from $n=15$ on (I share it below the questions).
Questions
Has been this already studied somewhere? Can you share some reference? Is the conjecture plausible for big values of $n$?
Can you share a faster way / program to check the validity of the conjecture? Or a possible strategy to prove it.
As a side note, and incidentally, the Python program finds mainly blocks that involve "quasi-Smarandache" numbers, where a quasi-Smarandache number can be defined as some integer that looks similar to some Smarandache number but changing the order of some digit, or substracting some. (F.i., 1234657, 12345678109,...). It surprises me that they seem to be more abundant than one could "a priori" expect.
Thanks in advance!
EDIT
As stated at the comments, a second interesting conjecture can be posed:
Conjecture 2
For $n>2$, the digits of each Smarandache number can be rearranged in blocks of at least $\lfloor\log(n)\rfloor$ digits, such that each block forms some prime number.
I have written another Python program to check the validity of the conjecture 2, but it seems to be too slow from $n=15$ on (I share it below the questions too).
Any insight on Conjecture 2,or an improvement on the program developed to check it for higher values of $n$, would also be welcomed.
Python code used for checking the Conjecture
Created on Thu Jul 27 14:55:31 2023
@author: juanmoreno
import itertools
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
def check_permutation(perm):
blocks = []
current_block = []
for num in perm:
current_block.append(num)
number = int("".join(str(digit) for digit in current_block))
if is_prime(number):
blocks.append(number)
current_block = []
return len(current_block) == 0, blocks
def permute_first_n_integers(n):
for perm in itertools.permutations(range(1, n+1)):
is_valid, blocks = check_permutation(perm)
if is_valid:
return blocks
return None
n = int(input("Enter the value of n: "))
for i in range(1,n+1):
result = permute_first_n_integers(i)
if result:
print("Example of blocks of prime numbers formed with the digits of integers less than or equal to ",i,":", result)
else:
print(f"No permutation found for n = ",i)
Python code used for checking the Conjecture 2
Created on Wed Aug 2 16:12:58 2023
@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 check_permutation_blocks(perm_digits, log_n):
num_blocks = len(perm_digits) // log_n
for num_combinations in range(num_blocks, 0, -1):
for combination in itertools.combinations(range(log_n * num_blocks), num_combinations):
blocks = [perm_digits[i:j] for i, j in zip((0,) + combination, combination + (None,))]
if all(len(block) >= log_n and is_prime(int(''.join(block))) for block in blocks):
return blocks
return None
def find_prime_blocks_permutation(n):
log_n = int(math.log(n))
permutations = itertools.permutations(str(i) for i in range(1, n+1))
for perm in permutations:
perm_digits = ''.join(perm)
blocks = check_permutation_blocks(perm_digits, log_n)
if blocks:
print("Valid permutation:", ''.join(perm))
print("Blocks forming prime numbers:", blocks)
return
print("No permutation found with blocks forming prime numbers.")
if name == "main":
n = int(input("Enter the value of n: "))
find_prime_blocks_permutation(n)