超初等序列 - 版本历史

2025年8月20日 (三) 08:26 Z

2025-08-20T08:26:00Z

←上一版本		2025年8月20日 (三) 16:26的版本
第110行：		第110行：
	* <math>LP(H_1+H_2)=(LP(H_1),LP(H_2))</math>，其中<math>(S_1,S_2)</math>为两个序列的拼接。		* <math>LP(H_1+H_2)=(LP(H_1),LP(H_2))</math>，其中<math>(S_1,S_2)</math>为两个序列的拼接。
	* <math>LP(\psi^H_x(H))=(x,(LP(H)+x))</math>。		* <math>LP(\psi^H_x(H))=(x,(LP(H)+x))</math>。
			{{默认排序:序数记号}}
	[[分类:记号]]		[[分类:记号]]

2025年7月13日 (日) 07:23 Z

2025-07-13T07:23:35Z

←上一版本		2025年7月13日 (日) 15:23的版本
第81行：		第81行：

	可以将其和 [[长初等序列#举例\|LPrSS 中相同表达式的展开]]进行对比。		可以将其和 [[长初等序列#举例\|LPrSS 中相同表达式的展开]]进行对比。

	~~== 枚举 ==~~

	== 与 PSS Hydra 的对应 ==		== 与 PSS Hydra 的对应 ==

GaoKao：/* 与 PSS Hydra 的对应 */

2025-07-10T14:09:04Z

与 PSS Hydra 的对应

←上一版本		2025年7月10日 (四) 22:09的版本
第85行：		第85行：

	== 与 PSS Hydra 的对应 ==		== 与 PSS Hydra 的对应 ==
			HPrSS可以和[[PSS Hydra]]存在直接的转换关系，下面介绍互译算法。

			说明：算法中出现的所有“序列”均指正整数序列，不需要为HPrSS的合法式。

			=== HPrSS到PSS Hydra ===
			给定一个HPrSS表达式<math>S=(a_1,a_2,\cdots,a_n)</math>，设其对应的PSS Hydra表达式为<math>PH(S)</math>。则：

			* 如果<math>S</math>为空序列，则<math>PH(S)=0</math>。
			* 否则，记<math>x_1=1</math>，<math>x_{n+1}=\min\{k>x_n\mid a_k\le a_{x_n}\}</math>，即<math>a_{x_{n+1}}</math>是<math>a_{x_n}</math>右边第一个小于等于<math>a_{x_n}</math>的项。这样<math>S</math>就可以写成<math>(a_{x_1},S_1,a_{x_2},S_2,\cdots,a_{x_k},S_k)</math>，由<math>a_{x_{n+1}}</math>的定义可知<math>S_i</math>中的每一项均大于<math>a_{x_n}</math>。
			* 我们有<math>PH(S)=\psi^H_{a_{x_1}}(PH(S_1-a_{x_1}))+\psi^H_{a_{x_2}}(PH(S_2-a_{x_2}))+\cdots+\psi^H_{a_{x_k}}(PH(S_k-a_{x_k}))</math>，其中<math>S-a</math>为将<math>S</math>的每一项都减去<math>a</math>得到的序列。

			例如，考虑LPrSS表达式<math>(1,4,7,6,3,5,7)</math>

			进行第二步，得到<math>k=1,x_1=1</math>，故<math>({\color{red}1},4,7,6,3,5,7)=\psi^H_1((3,6,5,2,4,6))</math>

			对<math>(3,6,5,2,4,6)</math>进行第二步，得到<math>k=2,x_1=1,x_2=4</math>，故<math>({\color{red}3},6,5,{\color{red}2},4,6)=\psi^H_3((3,2))+\psi^H_2((2,4))</math>

			分别计算<math>(3,2)</math>和<math>(2,4)</math>对应的PSS Hydra，得到<math>(3,2)=\psi^H_3(0)+\psi^H_2(0)</math>，<math>(2,4)=\psi^H_2(\psi^H_2(0))</math>

			综上，我们得到了<math>(1,4,7,6,3,6,8)=\psi^H_1(\psi^H_3(\psi^H_3(0)+\psi^H_2(0))+\psi^H_2(\psi^H_2(\psi^H_2(0)))</math>

			=== PSS Hydra到HPrSS ===
			给定一个PSS Hydra表达式<math>H</math>，设其对应的HPrSS表达式为<math>LP(H)</math>。则：

			* 如果<math>H=0</math>，则<math>LP(H)</math>为空序列。
			* <math>LP(H_1+H_2)=(LP(H_1),LP(H_2))</math>，其中<math>(S_1,S_2)</math>为两个序列的拼接。
			* <math>LP(\psi^H_x(H))=(x,(LP(H)+x))</math>。

	[[分类:记号]]		[[分类:记号]]

GaoKao：修改/* 举例 */ 中的一个错误

2025-07-10T13:21:03Z

修改举例：中的一个错误

←上一版本		2025年7月10日 (四) 21:21的版本
第70行：		第70行：
	首先，找出末项6的所有祖先项，用红色表示：<math>({\color{red}1},{\color{red}4},6,{\color{red}6})</math>。		首先，找出末项6的所有祖先项，用红色表示：<math>({\color{red}1},{\color{red}4},6,{\color{red}6})</math>。

	其次，计算出阶差序列，为<math>(1,2,2,2)</math>。		其次，计算出阶差序列，为<math>(1,3,2,2)</math>。

	然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。		然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。

2025年7月7日 (一) 16:11 Z

2025-07-07T16:11:23Z

←上一版本		2025年7月8日 (二) 00:11的版本
第85行：		第85行：

	== 与 PSS Hydra 的对应 ==		== 与 PSS Hydra 的对应 ==
			[[分类:记号]]

2025年7月7日 (一) 14:04 GaoKao

2025-07-07T14:04:29Z

←上一版本		2025年7月7日 (一) 22:04的版本
第6行：		第6行：
	一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如		一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如

	<math>(~~s_1~~,~~s_2~~,\cdots,~~s_n~~)\quad(n,~~s_1~~,~~s_2~~,\cdots,~~s_n~~\in\N,~~s_1~~=1)</math>		<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

	的序列。		的序列。
第16行：		第16行：

	* '''零表达式'''指<math>n=0</math>的表达式，即空序列；		* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
	* ~~后继表达式指~~<math>n>0,~~s_n~~=1</math>的表达式，即末项为1的非空序列；		* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
	* ~~极限表达式指~~<math>n>0,~~s_n~~>1</math>的表达式，末项不为1的非空序列。		* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

	对于 HPrSS 的一个极限表达式<math>(~~s_1~~,~~s_2~~,\cdots,~~s_n~~)</math>，定义以下术语：		对于 HPrSS 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

	==== 父项 ====		==== 父项 ====
第33行：		第33行：
	对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>m_0=m</math>，<math>m_{i+1}=p_{m_i}</math>，<math>P_m=\{m_i\mid i\ge 0\}</math>我们将<math>a_m</math>的'''祖先'''定义为所有<math>a_p(p\in P_m)</math>。		对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>m_0=m</math>，<math>m_{i+1}=p_{m_i}</math>，<math>P_m=\{m_i\mid i\ge 0\}</math>我们将<math>a_m</math>的'''祖先'''定义为所有<math>a_p(p\in P_m)</math>。

	~~通俗地说，某一项的祖先是它本身、它的父项、父项的父项、父项的父项的父项……中的某一项~~		通俗地说，某一项的祖先是它本身、它的父项、父项的父项、父项的父项的父项……中的某一项。

			例如，<math>({\color{red}1},{\color{red}4},6,7,{\color{red}6},{\color{red}7})</math>中，末项7的祖先是所有红色的项。

	==== 阶差 ====		==== 阶差 ====
	对于<math>m\in\{1,2,\cdots,n\}</math>，若<math>a_m</math>的父项是<math>a_{p_m}</math>，则定义<math>a_m</math>的'''阶差'''为<math>d_m=a_m-a_{p_m}</math>;若没有父项，则定义<math>a_m</math>的阶差为<math>d_m=a_m</math>。		对于<math>m\in\{1,2,\cdots,n\}</math>，若<math>a_m</math>的父项是<math>a_{p_m}</math>，则定义<math>a_m</math>的'''阶差'''为<math>d_m=a_m-a_{p_m}</math>;若没有父项，则定义<math>a_m</math>的阶差为<math>d_m=a_m</math>。

	~~阶差一定是正整数。~~		由父项的定义可知，阶差一定是正整数。

	==== 阶差序列 ====		==== 阶差序列 ====
	设<math>a_m</math>的阶差为<math>d_m</math>，我们把<math>(d_1,d_2,\cdots,d_n)</math>称为<math>(a_1,a_2,\cdots,~~a_m~~)</math>的'''阶差序列'''。		设<math>a_m</math>的阶差为<math>d_m</math>，我们把<math>(d_1,d_2,\cdots,d_n)</math>称为<math>(a_1,a_2,\cdots,a_n)</math>的'''阶差序列'''。

	==== 坏根 ====		==== 坏根 ====
	~~对于极限表达式~~<math>(a_1,a_2,\cdots,~~a_m~~)</math>~~，记末项的阶差为~~<math>d_n</math>。我们记序列的'''坏根'''为<math>a_r</math>，其中<math>r</math>定义如下：		给定极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，其末项的阶差为<math>d_n</math>。我们记序列的'''坏根'''为<math>a_r</math>，其中<math>r</math>定义如下：

	* 若<math>d_n=1</math>，则<math>r=p_n</math>，即序列的坏根定义末项的父项；		* 若<math>d_n=1</math>，则<math>r=p_n</math>，即序列的坏根定义末项的父项；

	* 若<math>d_n\ge 1</math>，则<math>r=\max\{k\in P_n\|d_k<d_n\}</math>。通俗地说，序列的坏根为末项的祖先中，最靠右的，且阶差小于末项阶差的项。		* 若<math>d_n\ge 1</math>，则<math>r=\max\{k\in P_n\|d_k<d_n\}</math>。通俗地说，序列的坏根为末项的祖先中，最靠右的，且阶差小于末项阶差的项。

			==== 序列的阶差 ====
			序列的'''阶差'''定义为<math>\delta=a_n-a_r-1</math>，这一点和 [[长初等序列\|LPrSS]] 一致。

			==== 坏部&好部 ====
			坏部、好部的定义和 PrSS 一致：坏部<math>B=(a_r,a_{r+1},\cdots,a_{n-1})</math>，好部<math>G=(a_1,a_2,\cdots,a_{r-1})</math>。

			== 展开 ==
			对于一个合法的 HPrSS 表达式<math>S=(a_1,a_2,\cdots,a_n)</math>，其展开规则如下：

			* 若<math>S</math>为零表达式，则<math>S</math>代表序数0；
			* 若<math>S</math>为后继表达式，则其前驱是'''<math>S'=(a_1,a_2,\cdots,a_{n-1})</math>'''；
			* 若<math>S</math>为极限表达式，根据前文定义确定坏根、阶差、好部、坏部；记<math>B_t=(a_r+t\delta,a_{r+1}+t\delta,\cdots,a_{n-1}+t\delta)</math>，它可以看成坏部的每一项加上阶差的t倍，则其基本列的第<math>m</math>项为<math>S[m]=(G,B,B_1,B_2,\cdots,B_m)</math>。或者说，<math>S</math>的展开式为<math>(G,B,B_1,B_2,\cdots)</math>。

			=== 举例 ===
			考虑 HPrSS 表达式<math>(1,4,6,6)</math>。

			首先，找出末项6的所有祖先项，用红色表示：<math>({\color{red}1},{\color{red}4},6,{\color{red}6})</math>。

			其次，计算出阶差序列，为<math>(1,2,2,2)</math>。

			然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。

			根据末项和坏根，我们得到了好部<math>G=()</math>，坏部<math>B=(1,4,6)</math>，阶差<math>\delta=6-1-1=4</math>。

			根据坏部和阶差，我们可以求出<math>B_1=(5,8,10)</math>，<math>B_2=(9,12,14)</math>，等等。

			最后，我们得到了展开式<math>(1,4,6,6)=(1,4,6,5,8,10,9,12,14,\cdots)</math>。

			可以将其和 [[长初等序列#举例\|LPrSS 中相同表达式的展开]]进行对比。

			== 枚举 ==

			== 与 PSS Hydra 的对应 ==

GaoKao：创建页面，内容为“'''超初等序列(Hyper Primitive Sequence System, HPrSS)'''，是一种Worm型序数记号，它是PrSS的一种扩展。 == 定义 == === 合法表达式 === 一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如 $(s_1,s_2,\cdots,s_n)\quad(n,s_1,s_2,\cdots,s_n\in\N,s_1=1)$ 的序列。例如： $(1,4,6,4)$ 和 $(1,1,4,5,1,4)$ 都是合法的 HPrSS 表达式…”

2025-07-07T13:03:21Z

创建页面，内容为“'''超初等序列(Hyper Primitive Sequence System, HPrSS)'''，是一种Worm型序数记号，它是PrSS的一种扩展。 == 定义 == === 合法表达式 === 一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如 <math>(s_1,s_2,\cdots,s_n)\quad(n,s_1,s_2,\cdots,s_n\in\N,s_1=1)</math> 的序列。例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 HPrSS 表达式…”

新页面

'''超初等序列(Hyper Primitive Sequence System, HPrSS)'''，是一种[[Beklemishev's Worm|Worm]]型序数记号，它是[[初等序列系统|PrSS]]的一种扩展。

== 定义 ==

=== 合法表达式 ===
一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如

<math>(s_1,s_2,\cdots,s_n)\quad(n,s_1,s_2,\cdots,s_n\in\N,s_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 HPrSS 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
HPrSS的合法式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* 后继表达式指<math>n>0,s_n=1</math>的表达式，即末项为1的非空序列；
* 极限表达式指<math>n>0,s_n>1</math>的表达式，末项不为1的非空序列。

对于 HPrSS 的一个极限表达式<math>(s_1,s_2,\cdots,s_n)</math>，定义以下术语：

==== 父项 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>p_m=\max\{1\le p_m<m\mid a_{p_m}<a_m\}</math>，若这样的<math>p_m</math>存在，则称<math>a_{p_m}</math>为<math>a_m</math>的'''父项'''。

如果这样的<math>p_m</math>不存在，我们也可以把<math>a_m</math>的父项定义为一个虚构的“第0项”，其值为<math>a_0=0</math>。

通俗的说，<math>a_m</math>的父项是在<math>a_m</math>左边、最靠右的、且小于<math>a_m</math>的项。

例如，在<math>(1,3,5,4,1,3)</math>中，4的父项是第一个3，而第二个1没有父项。

==== 祖先 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>m_0=m</math>，<math>m_{i+1}=p_{m_i}</math>，<math>P_m=\{m_i\mid i\ge 0\}</math>我们将<math>a_m</math>的'''祖先'''定义为所有<math>a_p(p\in P_m)</math>。

通俗地说，某一项的祖先是它本身、它的父项、父项的父项、父项的父项的父项……中的某一项

==== 阶差 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，若<math>a_m</math>的父项是<math>a_{p_m}</math>，则定义<math>a_m</math>的'''阶差'''为<math>d_m=a_m-a_{p_m}</math>;若没有父项，则定义<math>a_m</math>的阶差为<math>d_m=a_m</math>。

阶差一定是正整数。

==== 阶差序列 ====
设<math>a_m</math>的阶差为<math>d_m</math>，我们把<math>(d_1,d_2,\cdots,d_n)</math>称为<math>(a_1,a_2,\cdots,a_m)</math>的'''阶差序列'''。

==== 坏根 ====
对于极限表达式<math>(a_1,a_2,\cdots,a_m)</math>，记末项的阶差为<math>d_n</math>。我们记序列的'''坏根'''为<math>a_r</math>，其中<math>r</math>定义如下：

* 若<math>d_n=1</math>，则<math>r=p_n</math>，即序列的坏根定义末项的父项；

* 若<math>d_n\ge 1</math>，则<math>r=\max\{k\in P_n|d_k<d_n\}</math>。通俗地说，序列的坏根为末项的祖先中，最靠右的，且阶差小于末项阶差的项。