Embedded Primes Versus Prime Partitions

I noticed that the number associated with my diurnal age today (28323), while not prime, has digits that are all prime with the exception of 8 and it also has two other primes contained within it (283 and 23). I asked Gemini the following question:

28323 is a composite number with the property that it is a concatenation of prime numbers in various ways e.g. 283 || 23 and 2 || 83 || 23 where I’ve used the symbol || for concatenation. Write a program in SageMath that will identify all composite numbers in a given range that are concatenations of prime numbers in two or more different ways. The output should be a list of comma-separated numbers. The default range can be from 4 to 40000 and the upper and lower limits of the range should be easily adjustable. There should also be a switch so that the program can search for prime numbers with the same property, although the default should be set to composite. The number of suitable concatenations should be adjustable as well, although 2 is to be the default. Can a count of the suitable numbers be included in the output, underneath the list of numbers.

The program as requested is quite flexible. Below are the opening lines of code:

# --- Adjustable Parameters ---

LOWER_LIMIT = 4

UPPER_LIMIT = 40000

SEARCH_PRIMES = True  # False = search for composite numbers (default), True = search for primes

MIN_WAYS = 11         # Minimum number of valid prime concatenations required

# -----------------------------

Using these settings and thus searching for all primes in the range from 4 to 40000 that can be concatenated in at least 11 different ways, I found only a single number: 37337 (permalink). However, OEIS A179919 that lists primes with eleven embedded primes listed 111317 as the first number. Clearly I was confused and I sought clarification from Gemini. Here is its explanation:

The discrepancy comes down to two fundamentally different mathematical definitions: full-string prime partitions (concatenations) versus distinct proper prime substrings (embedded primes).

Your SageMath program counts the number of ways an entire number can be sliced into a complete concatenation of prime pieces from left to right, whereas OEIS A179919 counts how many distinct prime numbers appear anywhere inside the number as contiguous substrings (excluding the prime itself).

1. What Your Program Counts: Prime Concatenations (37337)

Your program requires every single digit of the number to be used in each partition. A 5-digit number has 2^{5-1} - 1 = 15 possible ways to be sliced into two or more contiguous pieces.

For the prime number 37337, 11 of those 15 full-string partitions consist entirely of prime numbers:

1. 3 || 7 || 3 || 3 || 7

2. 3 || 7 || 3 || 37

3. 3 || 7 || 337

4. 3 || 73 || 3 || 7

5. 3 || 73 || 37

6. 37 || 3 || 3 || 7

7. 37 || 3 || 37

8. 37 || 337

9. 373 || 3 || 7

10. 373 || 37

11. 3733 || 7

(The only 4 slices of 37337 that fail are the ones containing the composite substrings 33 or 733: 3 || 7 || 33 || 7, 3 || 733 || 7, 37 || 33 || 7, and 3 || 7337.)

2. What OEIS A179919 Counts: Distinct Embedded Primes (111317)

In the OEIS family of sequences (such as A039996 and A179909–A179924), an "embedded prime" is defined as a distinct prime proper substring occurring anywhere within the base-10 representation of the prime.

Under the OEIS definition, three completely different rules apply:

• The rest of the digits do not need to form primes: You just extract a contiguous block of digits from the number and ignore the digits to the left and right.

• Duplicates are only counted once: You collect the substrings into a mathematical set of unique prime values.

• Composite digits like 1 are helpful: Because you don't have to partition the entire number into primes, having the digit 1 (which is not prime and ruins full concatenations) is actually an advantage in A179919 because 1 starts many multi-digit primes (11, 13, 17, 113, 131, 317, etc.).

If we evaluate your number 37337 using the OEIS "embedded primes" rule, it only has 6 embedded primes:

$$\{3, 7, 37, 73, 337, 373, 3733\} \longrightarrow \text{7 primes?}$$

Actually, checking all contiguous proper substrings of 37337:

• 1-digit: 3, 7 (repeats ignored)

• 2-digit: 37, 73 (33 is composite)

• 3-digit: 373, 337 (733 is prime! Wait: 733 is indeed prime!)

• 4-digit: 3733 (prime), 7337 (7337 = 11 \times 667, composite)

Even with 733 being prime, the set of distinct proper prime substrings of 37337 is \{3, 7, 37, 73, 337, 373, 733, 3733\}, which is only 8 distinct embedded primes (falling short of 11). Furthermore, note that because 733 is prime, 37337 actually has 12 valid prime concatenations in your program (3 || 733 || 7 is also valid!), which is why it passed your MIN_WAYS = 11 threshold (>= 11).

Now compare that to 111317, the first term of OEIS A179919:

• Under your concatenation program: 111317 has only 1 valid prime concatenation (11 || 13 || 17), because any slice that isolates a single 1 (1 || 11317, 111 || 3 || 17, etc.) fails since 1 is not prime.

• Under OEIS A179919 (distinct proper prime substrings): Scanning all contiguous substrings of 111317 yields 11 distinct primes:

  1. 1-digit: 3, 7 (2 primes)

  2. 2-digit: 11, 13, 17, 31 (4 primes)

  3. 3-digit: 113, 131, 317 (3 primes)

  4. 4-digit: 1113 (3 \times 371, composite), 1131 (3 \times 377, composite), 1317 (3 \times 439, composite) (0 primes)

  5. 5-digit: 11131 (prime), 11317 (prime) (2 primes)

Summing those unique prime substrings gives 2 + 4 + 3 + 0 + 2 = 11 embedded primes:

$$\{3, 7, 11, 13, 17, 31, 113, 131, 317, 11131, 11317\}$$

Side-by-Side Comparison of the Two Rules

Property	Your Program (Prime Concatenations)	OEIS A179919 (Embedded Primes)
Core Mechanism	Partitions the entire string into adjacent prime blocks (A || B || C).	Extracts any contiguous prime substring from anywhere inside the string.
Unused Digits	Forbidden — every digit must belong to a prime block in the partition.	Allowed — surrounding digits outside the substring are ignored.
Repeated Primes	Counted every time they form a distinct full-string partition.	Ignored — only distinct prime values are counted.
Score for 37337	12 valid full-string prime concatenations.	8 distinct embedded primes (\{3, 7, 37, 73, 337, 373, 733, 3733\}).
Score for 111317	1 valid full-string prime concatenation (11 || 13 || 17).	11 distinct embedded primes (\{3, 7, 11, 13, 17, 31, 113, 131, 317, 11131, 11317\}).

I've gotten Gemini to write a program that accepts any positive integer as input, prime or non-prime, and outputs the concatenated primes as well as the embedded primes. Here is the output for 28323 (permalink):

Analysis for 28323 (Composite)

=============================================

1. PRIME CONCATENATIONS (Total: 4)

   1. 2 || 83 || 2 || 3

   2. 2 || 83 || 23

   3. 283 || 2 || 3

   4. 283 || 23

2. DISTINCT EMBEDDED PRIMES (Total: 5)

   2, 3, 23, 83, 283

I've added this program to my daily number analysis.

Record Runs Involving Home Primes

I just happened to notice that there is a run of six consective numbers from 27597 to 27602 inclusive that are only one step removed from their home primes. The only longer run up to one million that occurs is a run of eight numbers from 45162 to 45169.

Here is a permalink for finding these runs. Currently I'm 27586 days old and so the coming record run is not far off. Here are the factorisations for the numbers and the home primes associated with them.

• \(27597 = 3 \times 9199 \rightarrow 39199\)
  
  
• \(27598 = 2  \times13799 \rightarrow 213799 \)
  
  
• \(27599 = 11 \times 13 \times 193 \rightarrow 1113193 \)
  
  
• \(27600 = 2^4 \times 3 \times 5^2 \times  23 \rightarrow 222235523 \)
  
  
• \(27601 = 7 \times 3943 \rightarrow 73943 \)
  
  
• \(27602 = 2 \times 37 \times 373 \rightarrow 237373 \)

The run of eight numbers is listed below together with factorisations and home primes:

• \(45162 = 2 \times 3^2 \times 13 \times 193 \rightarrow 23313193 \)
  
  
• \(45163 = 19 \times 2377 \rightarrow 192377 \)
  
  
• \(45164 = 2^2 \times 7 \times 1613 \rightarrow 2271613 \)
  
  
• \(45165 = 3 \times 5 \times 3011\rightarrow 353011 \)
  
  
• \(45166 = 2 \times 11 \times 2053 \rightarrow 2112053 \)
  
  
• \(45167 = 31^2 \times 47 \rightarrow 313147\)
  
  
• \(45168 = 2^4 \times 3 \times 941 \rightarrow 22223941 \)
  
  
• \(45169 = 17 \times 2657 \rightarrow 172657 \)
  

All concatenations are applied to the prime factors in order from lowest to highest. Of course, runs formed by numbers that are concatenations of prime factors from highest to lowest are impossible because every second number is even with a smallest factor of 2. Every second concatenated number will thus be even as well.