Cartesian Product versus Self-Convolution

I asked Gemini the following:

How does the self convolution of a set A differ from the Cartesian product of the set with itself (A x A)?

This was the response: 

To understand the difference between the Cartesian product of a set and its self-convolution, we have to look at what mathematical object each operation produces. In short: the Cartesian product generates a new set of raw pairs, while the convolution generates a sequence that counts the frequencies of their sums.

Here is a full breakdown of how these two concepts differ and how they ultimately connect.

1. The Cartesian Product: Structural Pairing

The Cartesian product of a set $A$ with itself, denoted as $A \times A$, is an operation strictly within set theory.

It takes the elements of $A$ and creates a new set containing every possible ordered pair $(x, y)$, where both $x$ and $y$ are elements of $A$.

$$A \times A = \{(x, y) \mid x \in A \text{ and } y \in A\}$$

• Nature: It is purely structural. It does not add, multiply, or combine the values of the elements; it merely groups them side-by-side in a 2D grid.
• Size: If set $A$ contains $k$ elements, the Cartesian product $A \times A$ will always contain exactly $k^2$ elements.

2. The Self-Convolution: Frequency of Sums

Strictly speaking, you cannot convolve a "set" directly; convolution is an operation applied to functions or sequences. When mathematicians refer to the convolution of a set $A$, they are actually referring to the discrete convolution of the set's indicator sequence (also called the characteristic function).

Let $1_A(x)$ be a sequence where the value is $1$ if $x$ is in set $A$, and $0$ if it is not. The self-convolution of this sequence produces a new sequence, $c_n$:

$$c_n = \sum_{i+j=n} 1_A(i) \cdot 1_A(j)$$

• Nature: It is an arithmetic and combinatorial operation. The resulting sequence $c_n$ tells you exactly how many times the integer $n$ can be expressed as the sum of two elements from set $A$.
• Size: The result is not a finite set of pairs, but an infinite sequence of integers (though it will be mostly zeros if $A$ is a finite set).

3. The Core Difference

The Cartesian product asks: "What are all the possible ways to pick two elements from this set?"

The Convolution asks: "If I add those two elements together, how many pairs produce a sum of $n$?"

If you imagine the Cartesian product as a square grid of pairs, the convolution is the result of drawing diagonal lines through that grid (where $x + y = n$) and counting how many pairs fall on each diagonal.

4. A Concrete Example

Let’s define a set of integers: $A = \{1, 2, 4\}$

The Cartesian Product ($A \times A$) creates a set of $3^2 = 9$ ordered pairs:

$A \times A = \{(1,1), (1,2), (1,4), (2,1), (2,2), (2,4), (4,1), (4,2), (4,4)\}$

The Self-Convolution maps the sums of these pairs to their frequencies. Let's add the elements of each pair together:

• Sums to 2: $(1,1) \rightarrow$ 1 pair
• Sums to 3: $(1,2), (2,1) \rightarrow$ 2 pairs
• Sums to 4: $(2,2) \rightarrow$ 1 pair
• Sums to 5: $(1,4), (4,1) \rightarrow$ 2 pairs
• Sums to 6: $(2,4), (4,2) \rightarrow$ 2 pairs
• Sums to 7: None $\rightarrow$ 0 pairs
• Sums to 8: $(4,4) \rightarrow$ 1 pair

The resulting convolution sequence $c_n$ (starting from index $n=0$) would look like this:

$0, 0, 1, 2, 1, 2, 2, 0, 1, 0, 0, 0...$

5. The Generating Function Connection

Because you are working with tools like SageMath, the most elegant way to see the relationship between these two concepts is through generating functions.

If you turn set $A$ into a polynomial where the elements of the set are the exponents, you get:

$$f(x) = x^1 + x^2 + x^4$$

When you square this polynomial (which is the algebraic equivalent of the Cartesian product), you get:

$$f(x)^2 = (x^1 + x^2 + x^4) \cdot (x^1 + x^2 + x^4)$$

$$f(x)^2 = x^2 + 2x^3 + x^4 + 2x^5 + 2x^6 + x^8$$

Look at the coefficients of the expanded polynomial: $1, 2, 1, 2, 2, 1$. These are the exact non-zero values of our convolution sequence. The Cartesian product dictates the terms being multiplied, but the mathematical simplification of gathering like-terms is the act of convolution.

Convolutions Revisited

On the 12th October 2025, I created a post titled A Practical Example of a Convolution which began as follows:

Over the past decade, for some reason, I've chosen to ignore convolutions. Whenever they were mentioned in an OEIS sequence, I simply skipped over the reference. However, I'm now attempting to redress that neglect and to that end I was lucky to find two excellent YouTube videos about convolutions made by 3Blue1Brown (this guy has 7.76 million subscribers and for good reason).

I finished the post by saying:

This post is simply the first in what I hope will be a series of posts relating to convolutions. As I've already discovered, convolutions linked to Fourier transforms and Laplace transformations so it's a big topic to investigate but at least I've finally made a start.

Unfortunately there was no future series of posts relating to convolutions but I was reminded of them once again thanks to the number associated with my diurnal age today: \( \textbf{28152}\). It is a member of OEIS A014342:

 A014342: Convolution of primes with themselves.

 The initial members are:

4, 12, 29, 58, 111, 188, 305, 462, 679, 968, 1337, 1806, 2391, 3104, 3953, 4978, 6175, 7568, 9185, 11030, 13143, 15516, 18177, 21150, 24471, \( \textbf{28152}\), 32197, 36678, 41543, 46828, 52621, 58874, 65659, 73000, 80949, 89462, 98631, 108396, 118869, 130102, 142071

This time around I got Gemini to explain how the convolution was calculated:

In the context of integer sequences like those found in the OEIS, a convolution (specifically, a discrete Cauchy convolution) is a mathematical way of combining two sequences to create a third. When a sequence is convolved with itself, you are multiplying its terms together in a symmetrical, sliding window and summing the results.

Here is the full breakdown of how this works for OEIS A014342.

The Formula

First, let's establish our base sequence, which is the sequence of prime numbers, denoted as p_n:

• p₁ = 2
• p₂ = 3
• p₃ = 5
• p₄ = 7
• p₅ = 11
• ...and so on.

The n-th term of the convolved sequence, let's call it c_n, is calculated by taking the sum of the products of two primes whose indices add up to n + 1.

The formal equation looks like this:

c_n = Σ (p_i × p_n-i+1)

(summed from i = 1 to n)

In simpler terms: to find the n-th number in your sequence, you line up the first n primes going forward, line up the exact same n primes going backward, multiply the overlapping pairs, and add those products together.

Step-by-Step Calculation

Here is how the first few members of the sequence are calculated using this method.

1st Term (n = 1):

We only use the first prime (p₁ = 2).

c₁ = (p₁ × p₁)

c₁ = (2 × 2)

c₁ = 4

2nd Term (n = 2):

We use the first two primes (2 and 3). We pair the first with the second, and the second with the first.

c₂ = (p₁ × p₂) + (p₂ × p₁)

c₂ = (2 × 3) + (3 × 2)

c₂ = 6 + 6

c₂ = 12

3rd Term (n = 3):

We use the first three primes (2, 3, and 5). Notice how the indices always add up to 4 (n + 1).

c₃ = (p₁ × p₃) + (p₂ × p₂) + (p₃ × p₁)

c₃ = (2 × 5) + (3 × 3) + (5 × 2)

c₃ = 10 + 9 + 10

c₃ = 29

4th Term (n = 4):

We use the first four primes (2, 3, 5, and 7).

c₄ = (p₁ × p₄) + (p₂ × p₃) + (p₃ × p₂) + (p₄ × p₁)

c₄ = (2 × 7) + (3 × 5) + (5 × 3) + (7 × 2)

c₄ = 14 + 15 + 15 + 14

c₄ = 58

5th Term (n = 5):

We use the first five primes (2, 3, 5, 7, and 11).

c₅ = (p₁ × p₅) + (p₂ × p₄) + (p₃ × p₃) + (p₄ × p₂) + (p₅ × p₁)

c₅ = (2 × 11) + (3 × 7) + (5 × 5) + (7 × 3) + (11 × 2)

c₅ = 22 + 21 + 25 + 21 + 22

c₅ = 111

The Pattern

As you calculate further into the sequence, this symmetrical "folding" action continues. You are always starting at the outer edges of your chosen set of primes and working your way inward to the middle, multiplying the pairs and summing them up. This specific operation is incredibly common in polynomials, probability theory, and signal processing, but when applied purely to integer sequences like the primes, it yields the exact sequence you provided.

Remember that SageMath makes it very easy to determine self-convolutions due to its formula convolutions(A, A) where A is any given set.

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 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%.