Cosmic partition

A cosmic partition is a partition of the positive integers produced by particular recursive operations, keyed to a monotonically increasing integer sequence starting at one. Since such sequences can be mapped to a subset of the real numbers, often these numbers are considered the keys of the cosmic partitions instead. Each key generates a different cosmic partition, which except in certain degenerate cases comprises an infinite number of infinite sets. Each element within a cosmic partition, arranged in increasing order and considered as an integer sequence, is called a cosmic sequence.

The provenance of the term "cosmic partition" (or "cosmic sequence") is uncertain. There is no obvious relation between these partitions or sequences and worlds or cosmoi, and the reason why they were given this name has been forgotten.

Generation

The generation of a cosmic partition begins with the choice of a key sequence. This key must be a monotonically increasing integer sequence which starts with one. Thus, for example, the sequence [math]\displaystyle{ a_n = 2^{n-1} }[/math], the sequence [math]\displaystyle{ a_n = p_n - 1 }[/math] (where [math]\displaystyle{ p_n }[/math] is the nth prime number), the Fibonacci sequence sans its first element, or even the one-element sequence whose sole element is 1 would all be allowable as key sequences. Usually, however, a key sequence is chosen which is infinite and which (unlike any of the sequences listed above) is of nonzero and nonunit density.

A finite key sequence leads to a degenerate cosmic partition comprising a finite number of cosmic sequences. In the extreme case, the one-element sequence whose sole element is 1 would produce a cosmic partition containing only one element, which element included all the natural numbers. Conversely, a key sequence with a finite complement leads to a degenerate cosmic partition comprising infinitely many cosmic sequences, each of which is finite. In the extreme case, a key sequence containing all the natural numbers would produce a cosmic partition each element of which contained only one number. As long as both the key sequence and its complement are infinite, the cosmic partition will include an infinite number of infinite cosmic sequences.

Often the key sequence is converted to a real number N, often known as the "key number". This is done by generating a new sequence a such that [math]\displaystyle{ a_n = 0 }[/math] if n appears in the key sequence, and [math]\displaystyle{ a_n = 1 }[/math] if not. This sequence is then taken to be a binary expansional sequence, and the number N is the real number it corresponds to: i.e., the real number produced by writing the sequence of ones and zeroes in the sequence in order after a radix point. Because the first digit after the point in the number's binary expansion is necessarily zero (because 1 always appears in the key sequence), N is necessarily between zero and one-half, inclusive. The odd natural numbers, 1, 3, 5, 7, 9,..., for example, would lead to the expansional sequence 0, 1, 0, 1, 0, 1, 0, 1,... and hence the binary expansion [math]\displaystyle{ .\overline{01} }[/math], which finally leads to the key number [math]\displaystyle{ \frac{1}{3} }[/math]. The key number is typically used instead writing out the a key sequence When the key sequence is periodic, leading to the key number being a simple rational number. It's common to refer to a cosmic partition (or sequence) with a key number of N (or a key sequence of S) as simply a cosmic partition (or sequence) of N (or S).

Of course, the correspondence between key sequences and key numbers runs afoul of the usual problem inherent in expansional sequences of ambiguity in the case of terminating expansions. The two-element sequence 1, 2 corresponds to the binary expansion [math]\displaystyle{ 0.00\overline{1} }[/math], while the infinite sequence 1, 3, 4, 5, 6, 7,... (that is, the sequence comprising all the natural numbers except 2) corresponds to the binary expansion [math]\displaystyle{ 0.01 }[/math]... but both these binary expansions represent the same number, [math]\displaystyle{ \frac{1}{4} }[/math]. Any key number that is a dyadic fraction leads to the same ambiguity. Since both possibilities for a terminating expansion would lead to degenerate cosmic sequences, however, in practice such key numbers are usually avoided, so the problem seldom comes up.

Once a key sequence (or key number) is chosen, there are a few different, ultimately equivalent ways the cosmic partition can be generated.

Skyline method

The skyline method is one popular method of generating a cosmic partition, interesting because it generates the cosmic sequences in two places at once. Begin by writing the positive integers, in order (or as many of them as you want; the more you start with, the more elements of the cosmic sequences you will generate). Now, write the positive integers again above the previous row, but skipping the numbers that appear in the key sequence. For instance, for a key number of [math]\displaystyle{ \frac{7}{31} }[/math] ([math]\displaystyle{ 0.\overline{01110} }[/math]), corresponding to a key sequence of 1, 5, 6, 10, 11, 15, 16, 20, 21, 25,..., we get the following:

[math]\displaystyle{ \begin{matrix} & 1 & 2 & 3 & & & 4 & 5 & 6 & & & 7 & 8 & 9 & & & 10 & 11 & 12 & \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \end{matrix} }[/math]

Now, write the natural numbers again over the previous row, but again skipping any column the top number in which appears in the key sequence. This leads to the following:

[math]\displaystyle{ \begin{matrix} & & 1 & 2 & & & 3 & & & & & 4 & 5 & 6 & & & & & 7 & \\ & 1 & 2 & 3 & & & 4 & 5 & 6 & & & 7 & 8 & 9 & & & 10 & 11 & 12 & \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \end{matrix} }[/math]

After sufficiently many iterations of this procedure, we would eventually arrive at this:

[math]\displaystyle{ \begin{matrix} & & & & & & & & & & & & & & & & & & {\color{Red}1} & \\ & & & & & & & & & & & {\color{Red}1} & & & & & & & {\color{Red}2} & \\ & & & & & & {\color{Red}1} & & & & & {\color{Red}2} & & & & & & & {\color{Red}3} & \\ & & & {\color{Red}1} & & & {\color{Red}2} & & & & & {\color{Red}3} & & & & & & & {\color{Red}4} & \\ & & {\color{Red}1} & {\color{Red}2} & & & {\color{Red}3} & & & & & {\color{Red}4} & 5 & 6 & & & & & {\color{Red}7} & \\ & {\color{Red}1} & {\color{Red}2} & {\color{Red}3} & & & {\color{Red}4} & 5 & 6 & & & {\color{Red}7} & 8 & 9 & & & 10 & 11 & {\color{Red}12} & \\ {\color{Red}1} & {\color{Red}2} & {\color{Red}3} & {\color{Red}4} & 5 & 6 & {\color{Red}7} & 8 & 9 & 10 & 11 & {\color{Red}12} & 13 & 14 & 15 & 16 & 17 & 18 & {\color{Red}19} & 20 \\ \end{matrix} }[/math]

Consider the columns topped by the number 1 (colored red in the above diagram). If we take the bottom numbers in these columns—which are equivalent to these columns' positions—we get the sequence 1, 2, 3, 4, 7, 12, 19, 32, 53, 88... But notice also that reading down the numbers in any given column topped by 1 we get the same sequence (or a truncated form thereof). We get a different, disjoint sequence if we do the same with the columns starting with 5—which, again, is not in the original sequence—or with 6—which is not in any of the prior sequences—and so on. In each case, the sequence we obtain through the positions of the columns topped with a given number is the same as the sequence of numbers within that column. These are the cosmic sequences that make up the cosmic partition of the given key.

Extension method

Another popular method of generating cosmic partitions, the extension method may not be as visually pleasing as the skyline method but takes up less space. To start, simply write down the number 1. Now, in each iteration, we add to each row the next number not already appearing and not in the key sequence, taking the rows in increasing order of the last number in them. Then we add as new rows any numbers in the key sequence we've already exceeded.

For instance, let us consider the same key sequence as before, 1, 5, 6, 10, 11, 15, 16, 20, 21, 25,... We start with 1:

[math]\displaystyle{ \begin{matrix} 1 \end{matrix} }[/math]

In the next step, we write the next number (2) to the right of the 1:

[math]\displaystyle{ \begin{matrix} 1 & 2 \end{matrix} }[/math]

The next two steps are similar:

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 \end{matrix} }[/math]

Now, however, things get different. 5 is in the key sequence, as is 6, so the next number we can add on the right is 7.

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 & 7 \end{matrix} }[/math]

Since we've already exceeded 5 and 6, we add those as new rows:

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 & 7 \\ 5 & & & & \\ 6 & & & & \end{matrix} }[/math]

Now, the next three unused numbers not in the key sequence are 8, 9, and 12. We add those to the rows in order of the last number in the row, which means first 8 goes on the second row (ending in 5), then 9 on the third row (ending in 6), then 12 on the first (ending in 7):

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 & 7 & 12 \\ 5 & 8 & & & & \\ 6 & 9 & & & & \end{matrix} }[/math]

Since we've exceeded 10 and 11, we add those as new rows:

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 & 7 & 12 \\ 5 & 8 & & & & \\ 6 & 9 & & & & \\ 10 & & & & & \\ 11 & & & & & \end{matrix} }[/math]

The next iteration brings this:

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 & 7 & 12 & 19 \\ 5 & 8 & 13 & & & & \\ 6 & 9 & 14 & & & & \\ 10 & 17 & & & & & \\ 11 & 18 & & & & & \\ 15 & & & & & & \\ 16 & & & & & & \end{matrix} }[/math]

then this:

[math]\displaystyle{ \begin{matrix} 1 & 2 & 3 & 4 & 7 & 12 & 19 & 32 \\ 5 & 8 & 13 & 22 & & & & \\ 6 & 9 & 14 & 23 & & & & \\ 10 & 17 & 28 & & & & & \\ 11 & 18 & 29 & & & & & \\ 15 & 24 & & & & & & \\ 16 & 27 & & & & & & \\ 20 & & & & & & & \\ 21 & & & & & & & \\ 25 & & & & & & & \\ 26 & & & & & & & \\ 30 & & & & & & & \\ 31 & & & & & & & \end{matrix} }[/math]

And so on, with each row representing a different sequence within the cosmic partition.

Nomenclature and representation

Since the cosmic sequences of a particular key are disjoint, we can specify one particular sequence of a given key by merely specifying any number within it, which is called the "seed" of the sequence. Most often, the seed chosen is the smallest number, called the "minimal seed". The sequence 1, 2, 3, 4, 7, 12, 19, 32, 53, 88... is therefore the unique cosmic sequence with a key of [math]\displaystyle{ \frac{7}{16} }[/math] and a seed of 1. Except in the degenerate case of a finite key sequence, there are an infinite number of cosmic sequences in each cosmic partition, all with different minimal seeds. The set of minimal seeds of the cosmic sequences for a given key is, in fact, exactly the set of numbers in the key sequence. Sometimes the word "seed" is used to refer to the minimal seed of the sequence in which a given number appears; in the cosmic partition with a key of [math]\displaystyle{ \frac{7}{16} }[/math], for instance, the seed of 7 is 1 (since 7 appears in the cosmic sequence with a minimal seed of 1), and the seed of 28 is 10 (since 28 appears in the cosmic sequence with a minimal seed of 10).

Specific sequences within a cosmic partition can also be specified by their "order". The order of a cosmic sequence is the position of its first element (which is also its minimal seed) within the key sequence. The first-order cosmic sequence within a given cosmic partition is the sequence beginning with one. The second-order cosmic sequence begins with the second number in the key sequence, and so on.

Cosmic partitions are often designated by the ancient Greek letter koppa, Ϙ; however, conventions vary as to how to designate cosmic partitions and sequences of particular keys or orders. Most commonly, the key is written in parentheses after the koppa; the cosmic partition of [math]\displaystyle{ \frac{3}{4} }[/math], for instance, is then [math]\displaystyle{ \def\Koppa{\unicode{x03D8}}\Koppa({\frac{7}{16}}) }[/math] or [math]\displaystyle{ \Koppa(1, 5, 6, 10, 11, 15, 16, ...) }[/math]. To specify a particular sequence within the partition, the order of the sequence is either written as a subscript (as [math]\displaystyle{ \Koppa({\frac{7}{16}})_1 }[/math]) or as a second number within the parentheses (as [math]\displaystyle{ \Koppa(\frac{7}{16}; 1) }[/math]). If it is desired to specify a particular element of the sequence, this can be done with a second pair of parentheses: so [math]\displaystyle{ \Koppa(\frac{7}{16}; 1)(5) }[/math] is the fifth element of the first-order cosmic sequence of [math]\displaystyle{ \frac{7}{16} }[/math]... which happens to be 7.

Related sequences

The procedure laid out above to generate the cosmic partition also generates another, related sequence: after we've written the rows of numbers as described, we can form a new sequence based on the heights of the columns. That is, the nth term of this sequence is the number of elements in the column with the number n at the bottom. For the key of [math]\displaystyle{ \frac{7}{16} }[/math], the corresponding sequence is then 1, 2, 3, 4, 1, 1, 5, 2, 2, 1, 1, 6, 3, 3, 1, 1, 2, 2, 7, 1, ... This sequence is also sometimes called the cosmic sequence, but that leads to confusion with the other, more common definition of cosmic sequences (which may be called monotonic cosmic sequences if necessary to differentiate them). A more common name for this sequence is a "cosmic skyline", or a "skyline sequence" (apparently after a fancied resemblance to the skyline of a city). The skyline sequence of a given key can also be produced from the cosmic sequences of that key directly: the nth element of the skyline sequence is the position of the number n within the cosmic sequence in which it appears. For instance, the number 13 is the third element of 5, 8, 13, 22, 37, 62, ..., the cosmic sequence of [math]\displaystyle{ \frac{7}{16} }[/math] which contains it, so the thirteenth element of the skyline sequence of [math]\displaystyle{ \frac{7}{16} }[/math] is 3.

Taking the nth element of each cosmic sequence for a given key gives another sequence, called a cross-cosmic sequence. Like the cosmic sequences, the cross-cosmic sequences are infinite in both length and number (except for degenerate cases). The cross-cosmic sequences can therefore be assigned to orders the same as the cosmic sequences; the first-order cross-cosmic sequence is simply the key sequence. Like the cosmic sequences of a given key, the cross-cosmic sequences form a partition of the natural numbers, sometimes called a cross-cosmic partition. Note that when the cosmic sequences are generated by the extension method, while the cosmic sequences can be read across the rows of the resultant arrangement of numbers, the cross-cosmic sequences can be similarly read down the columns. The cross-cosmic sequence is most often symbolized by a koppa with a horizontal line through it: Ϙ. Thus the relation between cosmic and cross-cosmic sequences can be expressed as [math]\displaystyle{ \Koppa(K; s)(n) = \cssId{sstyle}{\style{text-decoration:line-through}{\Koppa}}(K; n)(s) }[/math].

Properties

Although individual cosmic sequences are not fractal in any meaningful sense, a cosmic partition—the set of all cosmic sequences for a given key—does have fractal characteristics. There is a pattern of self-similarity exhibited by the set of sequences as a whole that can be demonstrated in a few different ways. For instance, if you remove the lowest numbers from each sequence, and then reduce all the remaining numbers in all sequences to "close in the gaps" (that is, moving from lowest number to highest, change each number into the lowest positive integer not already present in any of the sequences as they currently stand), what results is the same set of sequences you started with. Furthermore, if you remove the sequence with a seed of 1 and then "close the gaps" in the remaining sequences in the same manner, you end up with a cosmic partition, but one with a different key. (In the case of a periodic key sequence, the key of the resulting partition will have a smaller periodicity.)

Since a first-order cosmic sequence is itself an integer sequence starting with 1, it is perfectly permissible to use a first-order cosmic sequence as a key to generate another cosmic partition. Accordingly, it's tempting to ask whether there's any self-generating cosmic sequence which is its own key. Alas, it's clear that this is not the case as soon as one considers that, due to the method by which cosmic sequences are constructed, a first-order cosmic sequence can have no elements in common with its key sequence aside from 1 (and clearly no higher-order cosmic sequence can match the key sequence, since no higher-order cosmic sequence can include 1). This does not, however, rule out the possibility of pairs or cycles of first-order cosmic sequences that generate each other. In fact, the extreme degenerate cases trivially do so: the first-order cosmic sequence corresponding to a key sequence containing only the number one contains all positive integers, and vice versa. However, it also can occur with nondegenerate key sequences: the sequence [math]\displaystyle{ \{ n^2 \} }[/math] = (1, 4, 9, 16, 25, 36, 49, 64, 81, 100,...) (sequence A000290 in the On-Line Encyclopedia of Integer Sequences) and the sequence [math]\displaystyle{ \{ 1 + \left \lfloor{\frac{n^2}{4}} \right \rfloor \} }[/math] = (1, 2, 3, 5, 7, 10, 13, 17, 21, 26, ...) (OEIS A033638) form such a pair such that either sequence, used as a key sequence, generates the other as a first-order cosmic sequence. This is not the only such pair; another comprises the dodecagonal numbers [math]\displaystyle{ \{ n (5 n - 4) \} }[/math] (OEIS A051624) and its generated sequence (not currently found in the OEIS). Such a pair of mutually generated sequences are called cosmic alternators. In fact, if one starts with any key sequence and iteratively uses the generated first-order cosmic sequence as a key sequence to generate a new first-order cosmic sequence, the pattern of sequences generated will converge to such an alternating pair.

Examples

Most cosmic sequences cannot be characterized in any more concise way. For some particular keys, however, the cosmic sequences match other, more familiar sequences. For example, taking the odd integers as a key sequence (corresponding to a key number of [math]\displaystyle{ \frac{1}{3} }[/math]), the cosmic sequence of seed s is simply [math]\displaystyle{ {s \cdot 2^{n-1}} }[/math]—and, in general, for any key comprising all integers that are not multiples of some integer a (corresponding to a key number of [math]\displaystyle{ \frac{1}{2^a - 1} }[/math]), the cosmic sequence of seed s is simply [math]\displaystyle{ {s \cdot a^{n-1}} }[/math]. Another type of key number that gives rise to simple familiar sequences as cosmic sequences is the key sequence comprising all numbers that are one greater than a multiple of some integer a, [math]\displaystyle{ \{ a(n-1)+1 \}_{n=1}^{\infty} }[/math] (corresponding to the key number [math]\displaystyle{ \frac{2^{a-1}-1}{2^a-1} }[/math]; the first-order cosmic sequence of such a key is simply the nth power ceiling of [math]\displaystyle{ \frac{2^a-1}{2^{a-1}-1} }[/math], [math]\displaystyle{ {}^n \left \lceil \frac{2^a-1}{2^{a-1}-1} \right \rceil }[/math]. Many other common sequences can be generated by suitable keys; the finite key sequence (1, 2) gives rise to the (positive) odd numbers as a first-order cosmic sequence and the (positive) even numbers as a second order; the key sequence (1, 3) yields as a first order cosmic sequence one followed by the even numbers: (1, 2, 4, 6, 8, 10, ...). Many other examples could be given. It is not, however, the case that every monotonically increasing integer sequence can be generated as a cosmic sequence. There is, for example, no key sequence that will generate the sequence comprising one followed by the prime numbers (OEIS A008578), or the prime numbers minus one (OEIS A006093).