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.