Unprimeable Versus Weakly Prime Numbers

Let's clarify the distinction between these two types of numbers:

Unprimeable numbers are composite numbers that remain composite regardless of which single digit is changed to another. These numbers are essentially "immune" to becoming prime through a single-digit modification in base 10, with 200 being the smallest example. 

Key Facts about Unprimeable Numbers:

• Definition: A composite number is unprimeable if changing one digit to any other digit (0-9) never produces a prime number. 

• Smallest Examples: The sequence begins 200, 204, 206, 208, 320, 322, 324, 325, 326, 328, .... 

• Example Case (200): Modifying the first, second, or third digit of 200 always results in a composite number (e.g., changing 200 to 100, 300, 210, 201, etc.). 

• Differentiation: They are sometimes confused with "weakly primes", which are actual prime numbers that cannot be turned into a different prime by changing a single digit.

The reason that I sought the clarification is that the number associated with my diurnal age today, 28151, has a property that allows it membership of OEIS A186995:

  A186995: smallest weak prime in base \(n\).

The initial members of this sequence, up to base 16, are:

127, 2, 373, 83, 28151, 223, 6211, 2789, 294001, 3347, 20837899, 4751, 6588721, 484439, 862789

28151 corresponds to base 6 where it has the representation 334155. This large value surprised me and so I asked Gemini:

OEIS A186995 lists the smallest weak prime in base n and it begins with 127, 2, 373, 83, 28151, 223, 6211, 2789, 294001, 3347, 20837899, 4751, 6588721, 484439, 862789 etc. starting with n=2. When we get to n=6, the base 6 equivalent of 28151 is 334155 but I find it hard to believe that in the first 28150 base 6 numbers there are none that are weakly prime. Can you explain how this is so in the case of base 6.

This was the response: 

The reason the smallest weakly prime number in base 6 jumps so drastically to 28151 (which is 334155 in base 6) lies in the prime factorization of the base itself. Because 6 is the product of the two smallest prime numbers, 2 and 3, it creates a mathematical "divisibility shield" that makes it statistically extremely difficult for a base 6 number to qualify as weakly prime.

Here is the step-by-step mechanics of how this works:

The Mechanics of Digit Substitution

In base 6, a number N is constructed from its digits as:

N = d_k 6^k + d_k-1 6^k-1 + … + d₁ 6¹ + d₀ 6⁰

For a number to be weakly prime, it must first be prime. If N is prime (and greater than 3), it cannot be divisible by 2 or 3. This means it must be an odd number, and it cannot be a multiple of 3.

When you modify a digit d_i to a new value c (where c is between 0 and 5), the difference between the new number and the original prime N is exactly (c − d_i) 6ⁱ.

The Divisibility Shield

For any digit position i ≥ 1, the place value 6ⁱ is always a multiple of 6. Therefore, the difference (c − d_i) 6ⁱ is always an even number and always a multiple of 3.

When you add or subtract a multiple of 2 and 3 to a prime number N, the resulting number maintains the exact same divisibility properties as N modulo 2 and modulo 3. Consequently, any substitution made to the 6¹, 6², 6³ … positions will never produce a number divisible by 2 or 3.

The Statistical Improbability

To satisfy the weakly prime condition, every possible digit substitution must result in a composite number.

In the general integer population, about 66.7% of all numbers are composite simply by being even or a multiple of 3. However, because of the divisibility shield, none of the modified numbers from the higher digit positions can take this "easy" path to being composite. They are forced into the remaining 33.3% of the number line—numbers coprime to 6—where the density of primes is three times higher.

For 334155 in base 6, there are 5 higher digit positions (i ≥ 1), and changing them to the other 5 valid digits yields 25 different modified numbers. All 25 of these must simultaneously be composite, but their prime factors must be drawn exclusively from larger primes (5, 7, 11, 13, etc.). Finding a cluster where 25 specific numbers coprime to 6 all happen to hit composite numbers requires venturing much further up the number line, which is why the sequence jumps so violently to 28151.

You can observe this exact same behavior in OEIS A186995 whenever the base has multiple distinct prime factors. For base 10 (factors 2 and 5), the smallest weakly prime is 294001. For base 12 (factors 2 and 3), it rockets to 20837899. Conversely, in a prime base like base 5 (where the answer is just 83), changing a higher digit easily flips the number from odd to even, quickly satisfying the composite requirement.

Numbers as Dates

When I turned 28000 days old, there was no way to turn this number into a date until I reached 28100 days old. At this point, it's possible via this stratagem:

28 - 1 - 00 --> 28th January 1900

There is ambiguity here because 00 could be interpreted as representing 2000 but I'll stick with 1900 for reasons that I'll make apparent. Yesterday I turned 28149 days old which converts as follows:

28 - 1 - 49 --> 28th January 1949

Hmmm. On that date, I was not yet born although I was a seven month old foetus. However, today I'm 28150 days old and this converts as follows:

28 - 1 - 50 --> 28th January 1950

Now by that date I had been born and was about ten months old. The interesting thing is that when I turn 30449 days old, this can be made to correspond to my birthday in the following way:

3 - 04 - 49 --> 3rd April 1949

There's ambiguity here because 30449 can also be made into another date:

30 - 4 - 49 --> 30th April 1949

All this requires that we admit to leading zeros when we want them, omit them when we don't and make choices that to suit ourselves when confronted with competing alternatives. In other words, flexibility is required. This process is not continuous. It works until I exceed 28999 since:

28 - 9 - 99 --> 28th September 1999

However, 29000 doesn't work and this number to date conversion only becomes possible again when I reach 29100 since:

29 - 1 - 00 --> 29th January 1900

With the leading two digits being 29, care must be taken with leap years and February. What happens with 29200?

29 - 2 - 00 --> 29th February 1900

Is the 29th of February 1900 a valid date? It is if 1900 were a leap year but it's not since it's not divisible by 400. If we interpret the date as 29th February 2000 however, then the date is valid since 2000 was a leap year. Sticking with the twentieth century convention, valid dates only arise with 29204, 29208, 29212, ... , 29288, 29292, 29296.

After reaching 29300, there's no problem with the leading two digits being 29 and things will be fine until I reach 30000. The number to date conversion will kick in again at 30100 and I'll reach 30449 without any gaps. All this is hardly serious mathematics but fun nonetheless. 

In all of this, I've adopted a day - month - year format switching between DD-M-YY and D-MM-YY as it suits me. This works well whereas other formats lead to lots of inadmissable dates and aren't as much fun.

Four Special Xenodromes

The number associated with my diurnal age today (\( \textbf{28149} \)) has the property that it is a member of OEIS A365257. This sequence consists of numbers such that the five digits of the number and their four successive absolute first differences are all distinct. The digit 0 is excluded of course or else the condition cannot be met.$$ \underbrace{|2-8|}_{6} \, \underbrace{|8-1|}_{7} \, \underbrace{|1-4|}_{3} \, \underbrace{|4-9|}_{5}$$I've written about this sequence before in a post titled Very Special Five Digit Numbers. In the range up to 40000, the only 96 such numbers (with 0 excluded) are:

14928, 15829, 17958, 18259, 18694, 18695, 19372, 19375, 19627, 25917, 27391, 27398, 28149, 28749, 28947, 34928, 35917, 37289, 37916, 38926, 39157, 39578, 43829, 45829, 47289, 47916, 49318, 49681, 49687, 51869, 53719, 57391, 57398, 58926, 59318, 59681, 59687, 61973, 61974, 62983, 62985, 67958, 68149, 68749, 68947, 69157, 69578, 71952, 71953, 72691, 72698, 74619, 74982, 74986, 75193, 75196, 76859, 78259, 78694, 78695, 81394, 81395, 81539, 82941, 82943, 85179, 85629, 85971, 85976, 86749, 87269, 87593, 87596, 89372, 89375, 89627, 91647, 91735, 92658, 92834, 92851, 92854, 93518, 94182, 94186, 94768, 94782, 94786, 95281, 95287, 95867, 96278, 96815, 97158, 98273, 98274

This got me wondering as to how many numbers there were such that the digits of the numbers contain the non-prime digits (1, 4, 6, 8 and 9) and the absolute differences between successive pairs of digits are the prime digits 2, 3, 5 and 7. It turns out that there are only four such numbers (grouped into two palindromic pairs):$$ \begin{align} 18694 \rightarrow \underbrace{|1-8|}_{7} \, \underbrace{|8-6|}_{2} \, \underbrace{|6-9|}_{3} \, \underbrace{|9-4|}_{5}\\ \\49681 \rightarrow \underbrace{|4-9|}_{5} \, \underbrace{|9-6|}_{3} \, \underbrace{|6-8|}_{2} \, \underbrace{|8-1|}_{7}\\ \\94186 \rightarrow \underbrace{|9-4|}_{5} \, \underbrace{|4-1|}_{3} \, \underbrace{|1-8|}_{7} \, \underbrace{|8-6|}_{2} \\ \\68149 \rightarrow \underbrace{|6-8|}_{2} \, \underbrace{|8-1|}_{7} \, \underbrace{|1-4|}_{3} \, \underbrace{|4-9|}_{5} \end{align}$$

Langford Sequences

I came across a reference to Langford Sequences in the puzzle shown in Figure 1:

Figure 1: link

The clue provided is to look at the repeating numbers and after a link thought I got it (9, 5, 12). As mentioned in the author's comments to the problem's solution, such a sequence is known as a Langford Sequence for \(n=12\). I asked Gemini to investigate further:

The Mathematical Enigma of Langford Sequences

Recreational mathematics often springs from the most unexpected, everyday observations. Such is the case with Langford sequences, a fascinating problem in combinatorial mathematics named after the Scottish mathematician C. Dudley Langford. The concept originated in 1957 while Langford was watching his young son play with colored wooden building blocks.

Langford noticed his son had stacked the blocks in a highly specific, deliberate pattern: between the two red blocks, there was exactly one block; between the two blue blocks, there were two blocks; and between the two yellow blocks, there were exactly three blocks. By assigning numbers to the colors (Red=1, Blue=2, Yellow=3), the child's stack translated into a unique integer sequence.

3

1

2

1

3

2

Intrigued by this elegant arrangement, Langford formalized the concept and submitted it as a problem to the Mathematical Gazette in 1958. He posed the question: could this pattern be replicated with larger sets of blocks and more colors? The challenge quickly caught the attention of the broader mathematics community and was eventually popularized by Martin Gardner in his famous Scientific American columns.

Mathematical Properties and Constraints

A standard Langford sequence of order n requires arranging the numbers 1 through n (appearing twice each) so that the two occurrences of any number k are separated by exactly k other numbers. However, mathematicians soon discovered that a perfect Langford sequence is mathematically impossible for most numbers.

In 1959, R. O. Davies proved what is now known as the Modulo 4 rule. He demonstrated that a Langford sequence of order n exists if and only if n is a multiple of 4, or one less than a multiple of 4. Expressed mathematically, a solution only exists when n ≡ 0 (mod 4) or n ≡ 3 (mod 4). This dictates that sequences can be built for n = 3, 4, 7, 8, 11, and 12, but they are intrinsically impossible for n = 5, 6, 9, or 10.

Furthermore, as n increases, the number of valid unique sequences (ignoring simple reversals) scales astronomically. Cataloged in the On-Line Encyclopedia of Integer Sequences as OEIS A014552, the solutions jump from a single arrangement for n = 3 and n = 4, to 150 solutions for n = 8, all the way to 108,144 unique solutions for n = 12. Because no simple algebraic formula exists to calculate these counts, determining them requires exhaustive algorithmic searches, often framed as exact cover problems in computer science.

Sequence Variations

Mathematicians rarely leave a rigid constraint unchallenged. The strict spacing rules of Langford sequences led to the development of several notable variations designed to bend those parameters.

1. Skolem Sequences (and the "Nickerson Variant" Confusion)

To clarify a common point of historical confusion, the "Nickerson variant" is not a separate iteration; it is simply an alternate name for the Skolem sequence. In a Skolem sequence, the spacing rule is shifted. Instead of requiring exactly k numbers between the occurrences of k, it requires the distance between the two occurrences of k to be exactly k positions. This means there are k - 1 numbers between them.

In 1957, Norwegian mathematician Thoralf Skolem published this shifted parameter while researching Steiner triple systems. Nearly a decade later, in 1966, R. S. Nickerson independently rediscovered this exact modification while directly studying Langford's problem. Consequently, recreational puzzle enthusiasts often refer to it as the Nickerson variant, while academic literature utilizes the term Skolem sequence. Unlike Langford pairings, Skolem sequences are solvable when n ≡ 0 (mod 4) or n ≡ 1 (mod 4).

4

2

3

2

4

3

1

1

In the Skolem sequence for n=4 visualized above, notice how the 1s are adjacent (0 spaces between them), the 2s have 1 space, the 3s have 2 spaces, and the 4s have exactly 3 spaces between them.

2. Hooked Langford Sequences

Because standard Langford sequences cannot exist for values like n = 2, n = 5, or n = 6, mathematicians created a structural workaround. A "hooked" sequence introduces a single empty, unassigned space—the hook—to stretch the mathematical footprint. To qualify as a true Hooked Langford sequence, this empty space (usually denoted by a zero, underscore, or blank space) must be placed in the penultimate, or second-to-last, position.

1

2

1

_

2

By shifting the available positions with this single hook, the previously impossible combinations resolve seamlessly, allowing the strict spatial requirements of the original Langford block problem to be met.

Inconsummate Numbers Revisited

In August of 2018, I included, in a post title Inconsummate Numbers, a program to determine all the inconsummate numbers up to 40000. It wasn't elegant but it got the job done (or so I thought). I asked Gemini to write a new program that was more efficient. Firstly, I asked it to write a program that would accept an integer as input and determine if that integer was inconsummate or not. If it was not then the program would display what number, when divided by its sum of digits, returned the input integer. I tested it with the number associated with my diurnal age today: 28147. Here was the result.

28147 is NOT inconsummate.

Found 2 number(s) x that yield 28147 when divided by their digit sum:

• 422205 (Digit sum: 15, Check: 422205 / 15 = 28147) 

• 928851 (Digit sum: 33, Check: 928851 / 33 = 28147)

Gemini described the way it determined this (although only for 522205):

The Number

The number you are looking for is 422205.

When you sum the digits of 422205, you get 15 (since 4 + 2 + 2 + 2 + 0 + 5 = 15). When you divide the original number by this sum, it yields your target:

\[ 422205 / 15 = 28147 \]

The Mathematical Mechanics

To understand how to program this, we have to look at the relationship between the target number, the starting number, and the digit sum.

Let \(n\) be the target number (in this case, 28147), let \(x\) be the number we are trying to find, and let \(s\) be the sum of the digits of \(x\), represented as a function \(S(x)\).

The problem dictates that:

\[ \frac{x}{s} = n \]

This can be rearranged to:

\[ x = n \cdot s \]

This means that any valid number \(x\) must be a direct multiple of \(n\). Furthermore, because \(s = S(x)\), we can substitute \(x\) to find the core condition that must be met:

\[ S(n \cdot s) = s \]

To find \(x\), we don't need to guess incredibly large numbers; we only need to test possible values for the digit sum \(s\), multiply it by \(n\), and see if the sum of the digits of that product equals \(s\).

Establishing an Upper Bound

To write a program that eventually stops running, we must define a maximum possible value for \(s\).

The maximum possible digit sum for a number is 9 times its number of digits (e.g., the sum of 999 is \(9 \times 3 = 27\)). Therefore, \(s\) can never be larger than 9 times the digit length of \(n \cdot s\). We can use a simple loop to calculate this hard mathematical ceiling before we even start searching.

***************************************

I then got Gemini to write a program to determine all the inconsummate numbers in the range from 1 to 40000. Here was the result (minus the actual list which is too large to include but here is a permalink):

Range Analyzed: 1 to 40000 (Total of 40000 numbers)

Count of Inconsummate numbers: 6836

Percentage of range: 17.09%

Now in my original list back in August of 2018, I had 10867 numbers listed as inconsummate in the same range. I've now amended that post and replaced the list with a link to a Google Document containing the correct list. You live and learn I guess.

Finally let's remind outselves of the definition:

An inconsummate number is a positive integer that cannot be formed by dividing any integer by the sum of its digits (in base 10), acting as the opposite of a "consummate number". 

Most numbers are "consummate". In the range up to 40000, they constitute 82.91%  but inconsummate numbers constitute only 17.09%.

Testing For Simple Permutations

Having explained what a simple permutation is in my previous post, I thought that testing the number associated with my diurnal age would be a good idea. Here is the output for today's number \( \textbf{28146} \) (permalink):

Simple Permutation Analyzer initialized...

--- Analyzing Number: 28146 ---

Intermediate Stage:

  Digits ranked descending: [8, 6, 4, 2, 1]

  Rank mapping (1=highest): {8: 1, 6: 2, 4: 3, 2: 4, 1: 5}

  Normalized permutation:   [4, 1, 5, 3, 2]

Result: False

Reason: Failed: Sub-block [3, 2] from digits [4, 6] forms an interval.

Alternative: Try 28416 instead. It is a simple permutation using your digits.

Having found that the digits 28146 do not form a simple permutation, the program finds a permutation that is simple, namely 28416. I tried entering a number with repeated digits and the number was regarded as invalid. I asked Gemini why:

The Definition of a Strict Permutation

The primary reason duplicate digits are rejected is rooted in the mathematical definition of a permutation. In combinatorics, a standard permutation is strictly defined as a rearrangement of a set of distinct, distinguishable items. Every item in the set must be unique.

When you introduce duplicate items (like the number 88234), you are no longer working with a standard set. You are working with what mathematicians call a multiset. While you can arrange the elements of a multiset, the rules, formulas, and structural properties change entirely.

The Problem of Ambiguity

Permutation theory relies on knowing exactly how many unique arrangements can be made. If all elements are distinct, a sequence of length n will always have n! (n factorial) possible arrangements.

However, duplicates introduce ambiguity. Imagine the number 122. Let's label the identical twos to tell them apart: 1, 2_a, 2_b. If we swap the two 2s, we get a structurally identical number:

• Arrangement A: 1, 2_a, 2_b (Displays as 122)
• Arrangement B: 1, 2_b, 2_a (Displays as 122)

Because swapping identical digits does not create a new, distinct sequence, the total number of unique arrangements drops. The mathematical framework built to analyze the structure of permutations assumes that every single shift in position creates a fundamentally new sequence. Duplicates break this assumption.

How Duplicates Break the "Simple" Math

Beyond the theoretical definition, duplicate digits physically break the mathematical logic used to define a simple permutation.

Recall the formula we used in the algorithm to test for intervals: max(block) - min(block) == length - 1. This formula only works because it assumes that an interval of distinct integers will have a predictable span. For example, a block of three distinct, consecutive numbers like {4, 5, 6} will always have a span of 2 (because 6 - 4 = 2, and the length 3 minus 1 is 2).

If we allow duplicates, this logic collapses. Consider a block of two identical numbers: {5, 5}.

• The length of the block is 2.
• The maximum value is 5.
• The minimum value is 5.
• max - min is 0.

The formula expects a span of 1 for a block of length 2. Because the span is 0, the math fails to recognize what is happening. Furthermore, the entire concept of a "continuous range of numbers" becomes nonsensical when numbers repeat. Does {5, 5} constitute an interval? What about {4, 5, 5, 6}?

Because the definition of simple permutations was explicitly designed to map the structural scattering of distinct integers, attempting to apply it to repeating digits forces the math to evaluate scenarios it was never designed to handle.

Fair enough. I've incorporated this algorithm into my daily number analysis. The no repeated digits restriction means that only xenodromes are acceptable input.

Simple Permutations

One of the properties associated with my diurnal age today (28146) is that it's a member of OEIS A111111:

A111111: number of simple permutations of degree \(n\).

The initial members of this sequence beginning with \(n=1\) up to \(n=9\) are 1, 2, 0, 2, 6, 46, 338, 2926 and 28146.

I did not understand the explanation in the OEIS comments about what a simple permutation of degree \(n\) was so I turned to Gemini for help and its response forms the content of this blog post. I got NotebookLM to create a video overview of the post and then uploaded it to YouTube.

Understanding Simple Permutations

To understand OEIS A111111, it helps to think of the problem in terms of finding "hidden chunks" or "blocks" within a sequence of numbers.

The core rule is this: a permutation is simple if you cannot find any contiguous sub-sequence of length 2 or more (but less than the total length) that contains a continuous range of numbers, regardless of the order those numbers appear in.

Deconstructing the Example: 2647513

The comment in the sequence notes that the permutation 2647513 is not simple because of the interval of indices [2..5]. Let's map the positions (indices) to their actual values.

• Position 1: 2
• Position 2: 6
• Position 3: 4
• Position 4: 7
• Position 5: 5
• Position 6: 1
• Position 7: 3

If we look strictly at positions 2 through 5, the numbers present are 6, 4, 7, and 5. If we sort that subset of numbers, we get 4, 5, 6, 7. This forms a perfect, unbroken mathematical sequence (an interval). Because we found a contiguous block of positions that maps to a contiguous block of values, and this block is smaller than the entire sequence but larger than a single number, the permutation fails the test. It is not simple.

Why is n=3 exactly 0?

Looking at the sequence (1, 2, 0, 2, 6, 46...), the third term is 0. This means there are absolutely zero simple permutations of length 3. We can prove this by testing all six possible permutations of the numbers 1, 2, and 3:

• 123: Positions 1-2 contain {1, 2}. (Fails)
• 132: Positions 2-3 contain {3, 2}, which sorts to {2, 3}. (Fails)
• 213: Positions 1-2 contain {2, 1}, which sorts to {1, 2}. (Fails)
• 231: Positions 1-2 contain {2, 3}. (Fails)
• 312: Positions 2-3 contain {1, 2}. (Fails)
• 321: Positions 1-2 contain {3, 2}, which sorts to {2, 3}. (Fails)

Every single permutation of length 3 contains an embedded chunk of length 2 that forms a continuous range. Therefore, none of them are simple.

The n=4 Case: The Two Survivors

The sequence tells us there are exactly 2 simple permutations for n=4. Out of the 24 possible combinations, only two survive the test: 2413 and 3142.

Let's test 2413 to see why it passes:

Check all chunks of length 2:

• Positions 1-2: {2, 4} — Gap between 2 and 4.
• Positions 2-3: {4, 1} — Gap between 1 and 4.
• Positions 3-4: {1, 3} — Gap between 1 and 3.

Check all chunks of length 3:

• Positions 1-3: {2, 4, 1} — Sorts to {1, 2, 4}. Missing the 3.
• Positions 2-4: {4, 1, 3} — Sorts to {1, 3, 4}. Missing the 2.

Because no sub-sequence forms an unbroken chain of numbers, 2413 is a simple permutation. The same logic applies to 3142, making them the only two simple permutations of degree 4.

I then asked Gemini the following:

So in the case of n=9 we are looking at all permutations of the digits 123456789 and finding that there are 28146 simple permutations? Is that correct? Also, can you explain what is meant by a permutation of degree n. Is there a formula for calculating the number of simple permutations of degree n? 

The n=9 Case

For n=9, you are looking at all possible arrangements of the digits 1 through 9. There are 362880 total possible permutations for those nine digits (which is 9 factorial). If you were to test every single one of those 362880 arrangements for hidden consecutive blocks, you would find that exactly 28146 of them are simple permutations.

What is a "Permutation of Degree n"?

In combinatorial mathematics, the "degree" simply refers to the total number of elements in the set you are arranging.

• A permutation of degree 4 means you are finding the arrangements of a set containing exactly 4 distinct items (usually the integers 1, 2, 3, and 4).
• A permutation of degree n just means you are arranging the integers from 1 up to n.

It is just a formal way of stating the length of the string of numbers you are working with.

Is There a Formula?

There is no simple, single-line closed-form algebraic formula to instantly calculate the exact number of simple permutations for a specific degree. You cannot just plug n into a basic equation to get the answer.

Instead, mathematicians calculate exact values using generating functions and recurrence relations. The foundational logic is based on substitution decomposition: the idea that every standard permutation can be uniquely constructed by taking a simple permutation and "inflating" its individual points with other, smaller permutations. By knowing the total number of permutations (n!), mathematicians can work backward recursively to strip away the complex ones and isolate the count of simple ones.

However, there is a very elegant asymptotic formula for this sequence.

As the degree n becomes very large, the number of simple permutations, denoted as \( S_n\), can be approximated by:$$ S_n \approx \frac{n!}{e^2}$$Here, e is Euler's number. Because e² is approximately 7.389056, this formula reveals a fascinating property of permutations: as the length of the number string approaches infinity, the probability that a randomly generated permutation will be simple approaches 1 / e², or roughly 13.53%.

So, while calculating the exact integer for a specific degree requires heavy recursive computation, calculating the approximate scale of simple permutations for massive degrees is surprisingly straightforward.

I asked Gemini to give an example for the case of \(n=9\):

An Example for \(n=9\)

Here is one of the 28146 simple permutations of the digits 1 through 9:

4 1 7 3 9 6 2 8 5

To verify that this permutation is simple, we can apply the same logic used previously. We must ensure that no subset of contiguous positions (from length 2 up to length 8) contains a continuous range of values.

Why This Example Works

The easiest way to prove it is simple is to test the difference between the highest and lowest values within various blocks. If the difference between the maximum and minimum values in a block equals the length of the block minus 1, it forms a continuous interval.

• Testing Length 2 Blocks: Let's look at the adjacent pairs: {4, 1}, {1, 7}, {7, 3}, {3, 9}, {9, 6}, {6, 2}, {2, 8}, and {8, 5}. None of these pairs are consecutive numbers. The smallest gap is 3 (between 1 and 4, 6 and 9, 5 and 8). Because no pair has a difference of exactly 1, there are no length 2 intervals.
• Testing Length 4 Blocks: If we take the first four positions (4, 1, 7, 3), the highest value is 7 and the lowest is 1. The span is 6, which is much larger than the block length of 4. If we take the last four positions (6, 2, 8, 5), the highest is 8 and the lowest is 2. The span is 6. Because the numbers are scattered, they do not pack tightly enough to form an interval.
• Testing Length 8 Blocks: If we take the first eight numbers (4, 1, 7, 3, 9, 6, 2, 8), the values range from 1 to 9. The only missing number is 5. Because 5 is missing from the middle of the set, the remaining numbers cannot form an unbroken sequence. The same applies to the last eight numbers (1, 7, 3, 9, 6, 2, 8, 5), which are missing the 4.

Because this "scattering" holds true for every possible block size between 2 and 8, the permutation strictly avoids all intervals and perfectly satisfies the definition of a simple permutation.

I asked Gemini the following: 

Of what use are simple permutations? Are there any practical applications or is the concept purely theoretical.

While simple permutations originated as a purely theoretical concept in combinatorial mathematics, they have proven to be surprisingly useful in several practical, real-world applications. Because mathematics is the language of structure, these "irreducible" sequences provide the foundational logic for any field that needs to analyze, dismantle, or scramble data.

Here is a breakdown of how simple permutations bridge the gap between pure theory and practical application.

The "Prime Numbers" of Permutations (Theoretical Foundation)

Before looking at applied fields, it is helpful to understand their role in pure mathematics. Just as every integer can be factored into a unique set of prime numbers, every single permutation can be uniquely broken down into a "tree" of simple permutations through a process called substitution decomposition. In this sense, simple permutations are the fundamental, indivisible building blocks of all mathematical sequences.

Bioinformatics and Evolutionary Genomics

One of the most robust practical applications of this concept is in computational biology, specifically regarding genome rearrangement.

When scientists compare the DNA sequences of different species, they look at how chunks of genes have moved around over millions of years of evolution. A sequence of genes in a fruit fly might be a permuted version of the same genes in a mosquito. If a block of genes moves together as a single, unbroken unit during evolution, it forms an "interval" (meaning the permutation of that genome is not simple).

Simple permutations represent the extreme cases of genetic mutation: complete and total structural rearrangement where no contiguous blocks of genes have been preserved intact. By programming algorithms to search for and isolate these simple permutation structures, geneticists can map exactly where and how evolutionary divergence occurred.

Computer Science and Algorithm Optimization

In computational analysis, particularly when writing custom data analysis scripts in Python or SageMath, efficiency is critical. Because every complex sequence can be mathematically decomposed into a structural tree of simple permutations, computer scientists use these trees to drastically speed up sorting and search algorithms.

Problems involving "permutation pattern matching" that would normally take an impossible amount of exponential computing time can often be reduced to manageable polynomial time. The algorithm simply breaks the massive dataset down into its simple permutation components first, and then solves the problem on those smaller, irreducible blocks.

Cryptography and Data Diffusion

A secure cryptographic cipher relies on two primary principles: confusion and diffusion. Diffusion requires that a small, localized change in the input data is spread completely across the entire output data.

Because the strict definition of a simple permutation means it perfectly avoids forming neat, predictable blocks of adjacent numbers, it represents a state of maximum "scattering." This mathematical framework helps cryptographers design the substitution-permutation networks (the architecture behind modern encryption standards like AES) that resist pattern analysis and keep digital communications secure.

While you may never see a simple permutation explicitly named in a piece of commercial software, the mathematical rules governing them are silently working behind the scenes to optimize data, track genetic history, and secure information.