Y數列入門

\( \newcommand{\len}{ {\rm len}} \renewcommand{\value}{ {\rm value}} \newcommand{\ifu}{ {\rm if}} \newcommand{\gtone}{ {\rm gt1}} \newcommand{\parent}{ {\rm parent}} \newcommand{\diff}{ {\rm diff}} \newcommand{\ancestor}{ {\rm ancestor}} \newcommand{\bm}[1]{ {\boldsymbol　 #1}} \newcommand{\w}{\omega} \newcommand{\e}{\varepsilon} \newcommand{\nat}{\mathbb{N}} \newcommand{\p}{\psi} \)

(This article is being translated into Chinese.)

Y數列(Y-sequence) is a notation made by Yukito. In this page, we have introduction of Y sequence See the code if you want to know its definition. See the page to try expansion.

记号

每个Y序列是以形式为 \((a_0,a_1,a_2,\cdots,a_k)\) 的含有有限项数的正整数数列。例如，这些是符合规则的Y序列：(1), (1,1,1), (1,2,2), (1,2,3), (1,2,4), (1,2,3,4,1,2,3,3,3), (1,2,4), (1,2,4,5,4), (1,2,4,8,9,8), (1,2,4,8,16), (1,3), (1,4,4) 和 (1,1024).

至 \(\w\) 的展开规则

我们现在定义一个对Y序列的“展开”函数. 函数输入一个Y序列和一个正整数，例如(1,2,3)[2]=(1,2,2,2)。

现在按照不同的情况定义一个序列的展开式。

最简单的情况为序列的末尾是1。此类型的序列展开只需将后面的1移除。 (1,1,1,1)[2]=(1,1,1), (1,1,1,1,1,1)[100]=(1,1,1,1,1), (1)[300]=(). 方括号里的数字无关紧要。以此方法可以展开至少 \(\w\) 以内的序列。

寻找父节点

举例：展开 (1,2,3,4,1,2,3,3,3)[2]

对于序列中的每一个非1数都可以找到一个“父“节点。先标记这个数字，然后往左找。找到的第一个比他小的数称为他的“父”。

展开此类型的序列只需要找到最右边的数字的父节点。

例如，我们寻找如下序列中，红圈里的3的父节点：

所以2是它的父节点。

所有的1都是序列里的最小数，所以1没有父节点。

Drawing Hydra Diagram

Drawing a hydra diagram is useful for later expansion.

Let's find all the parent for all the numbers, and connect them with the lines as the followings. They are called hydra diagrams of Y sequences.

The element which has A as its parent is called the child of A. If you draw the child one step above the parent, it is easier to draw the larger one.

Since 1 has no parent, we'll connect it to the leftmost x for now.

Expansion up to \(\varepsilon_0\)

The sequence with parent-child difference of 1 can be expanded in the following way.

(1) Inclement bracket by 1.
(2) Delete the last number.
(3) Make anger mark with the parent of deleted child. (The parent who have had their children killed are angry.)

(4) The right part of the angry parent including it is called bad part. The left part of the parent is good part.

(5) Copy the bad part to the right as many times as the bracket.

Also, Also, if the rightmost number is 1, then after the bracket is increased by 1 in (1), the 1 simply disappears because there is no parent of 1.

The last element is always disappear. The last element is called cut child. The parent of the cut child is called bad root. This is very important element because it decide the border of good part and bad part.

The expansion method so far is almost the same as 原始數列系統. When the difference from the parent is more than 2, there is another rule, which will be explained in the next section.

Expansion up to (\(\varepsilon_0\)～\(\varepsilon_{\omega+1}\))

We explain the expansion method for the sequence which has difference between the parent and the child. For example, let's consider the expansion of (1,2,4)[2].

Expansion of (1,2,4)[2]

In the sequence, The cut child is 4, and its parent is 2, so, the difference between the parent and the child is \(4-2=2 \gt 1\). In this case, we need to make the second sequence which denotes all the differences between all the parents and their children, and to make lines between them. Though it is different to the "differential sequence" generally spoken in mathematics because it takes difference between the parents and their children, let's call the differential sequence for the parents and children differential Y sequence. It is easy to understand that the differential Y sequence (1,2) should be written under the corresponding branch of (1,2,4). Call (1,2,4) "the 1st level sequence" and call its differential Y sequence (1,2) "the 2nd level sequence".

To expand, we first expand the 2nd level of sequence using the same rules as before.

You can see (1,2) → (1,1,1). the bold 1 is the bad root.

The next step is to use it to reconstruct the 1st level sequence. Before we do that, we need to copy the bad part of the 1st level sequence as well as the 2nd level sequence.

First of all, the bad root of the 1st level sequence is the end of the branch corresponding to the bad root of the 2nd level sequence.

So, in this case of the example, 2 is the bad root of the 1st level sequence. bad root and the right side of it is the bad part. The bad root and the bad part to the right of it are the bad part. 2 is the end of the bad root, so the bad part is only 2.

Copying 1st level sequence requires a slightly more special method than the 2nd level. First, we need to analyze the "branch connection" of the bad part of the first Y sequence (1,2,4).

Notice the height of the location of the bad root parent (IN) and the location of the cut child (OUT). The IN is one level below the bad root, and the OUT is one level above the bad root. When copying, we use this information to make sure that the IN of the copied bad part connects to the OUT of the bad part one level to the left.

It goes like this. let the copied bad part have no numbers written on it, and let the numbers be a circle. After the shape is decided, reconstruct the 1st level sequence so that the 2nd Y sequence is the differential Y sequence of the 1st Y sequence.

You could have done all the reconstruction by addition: 1+1=2, 2+1=3, 3+1=4, and so on. And this 1st level sequence is the sequence that expanded the original Y sequence (1,2,4).

We finally got the expansion result, (1,2,4)[2]=(1,2,3,4).

Expansion of (1,2,4,1,2,4)[2]

Let's expand (1,2,4,1,2,4)[2].

There is one things that is different from earlier. We can't make the differential Y sequence because 1 in the right side of (1,2,4,1,2,4) has no parent. In this case, the parent should be marked as x.

The rest is the same, expand the differential Y sequence (1,2,x,1,2) by [2] to (1,2,x,1,1,1), and then expand the 1st level sequence based on that. The result is (1,2,4,1,2,3,4).

By the way, this will be the Y sequence corresponding to \(\e_02\).

Expansion of (1,2,4,4)[2]

Next is the expansion of (1,2,4,4)[2]. This can be expanded with the same rule.

First, the bad root in the 2nd level is the parent of the rightmost 2, so it becomes 1. bad part is to the right of bad root, so it becomes (1,2). Now we have (1,2,1,2,1,2).

Now consider how the 1st level will be copied.

The IN is one below the bad root, the cut child is 4, and the parent is 2, so the OUT is one above the bad root. The IN and OUT of this are connected to copy the branch.

Then, as before, we will use the numbers in the 2nd level as hints to reconstruct the Y-number sequence in the 1st level. Add up the corresponding branches: 2+1=3, 3+2=5, 3+1=4, 4+2=6, and so on, until the circles are filled with 3, 5, 4, and 6. So, (1,2,4,4)[2]=(1,2,4,3,5,4,6).

We can expand up to less than \(\epsilon_{\w+1}\) with this rule.

Expansion up to (\(\varepsilon_{\omega+1}\)～\(\p_0(\p_\w(0))\)

One thing to watch out for arises in (1,2,4,5,4). This is the Y sequence equivalent to \(\varepsilon_{\omega+1}\).

If we use the same idea as before, the differential Y sequence would be (1,2,1,2), so we would want the parent of the rightmost 2 to be the 1 to the left of it, as in
.
However, in the Y sequence after the 2nd level, the parenting involves the level above. However, in the second and subsequent levels of the Y sequence, the previous level is involved in determining the parent.

First, observe the ancestor of 4 on the far right of the 1st level. An ancestor is itself, its parent, its parent's parent, its parent's parent's parent, ....

An ancestor of 4 is 4, 2 of 4's parents, 1 of its parents, and x of its parents. The ancestors of 4 are 4, 2 of 4's parents, 1 of its parents, and x of its parents. 4, the third from the right and 5 are not ancestors.

Then, when finding the parents of the 2nd level elements, only the 2nd level element corresponding to the branches of the direct ancestors of the parent and child that are connected to the 1st level branch corresponding to that element will be considered as candidates. In other words, the third 2 from the right and the second 1 from the right in the 2nd level are ignored.

This makes the rightmost parent of the 2nd level the fourth 1 from the right.

The rest is the same as before.

The bad root of the 2nd level is the leftmost 1 and bad part is (1,2,1). The bad root of the 1st level is 2, and the bad part is (2,4,5). After they are copied by the value of the bracket, the 2nd level should be (1,2,1,1,2,1,1,2,1), the circles of the 1st level should be filled by using the 2nd level numbers, to be (1,2,4,5,3,5,6,4,6,7).

Now we can expand the Y sequence less than (1,2,4,8), that is, up to the second level.

Expansion up to (\(\p_0(\p_\w(0))\)～\(\p_0(\p_\w(1)+\p_\w(0))\))

Next we will talk about the sequence that gives rise to the 3rd level. Let's expand (1,2,4,8,8)[2].

We want to expand the 2nd level sequence (1,2,4,4), but there is a pair where the difference between the parent and child is 2. In this case, we need to make a differential Y sequence of this and a 3rd level sequence.

In this case, the 1st level sequence is just a copy, just like the sequence below \(\e_0\), while the 2nd and 1st level sequences are reconstructed from their next level sequences after copying the branch form, just like before.

In other words, the 3rd level sequence (1,2,2) is first expanded as (1,2,1,2,1,2), the 2nd level sequence is reconstructed as (1,2,4,3,5,6,4), and then the 1st level sequence (1,2,4,8,7,12,11,17) can be reconstructed using it.