Ulam 序列 定义
1 2 3 U(a,b,1) = a U(a,b,2) = b U(a,b,k > 2) = 大于U(a,b,k-1) 且能唯一表示为 U(a,b,i) + U(a,b,j), i != j
例如
1 2 3 4 5 6 7 U(1,2,1) = 1 U(1,2,2) = 2 U(1,2,3) = 1+2 = 3 U(1,2,4) = 1+3 = 4 U(1,2,5) = 2+4 = 6 (5有两种表示方法) U(1,2,6) = 2+6 = 8 (6有两种表示方法) U(1,2,7) = 3+8 = 11 (9,10都有多种表示方法)
题目 求
1 2 3 4 5 6 7 8 9 U(2,5,10**11) +U(2,7,10**11) +U(2,9,10**11) +U(2,11,10**11) +U(2,13,10**11) +U(2,15,10**11) +U(2,17,10**11) +U(2,19,10**11) +U(2,21,10**11)
想法 列举了几个，发现无能为力
能想到的就是 set+枚举
那至少是 K方的空间时间复杂度, 连k都没法搞，更别说k方了
果断google XD
搜索到 Schmerl and Spiegel (1994) proved that Ulam sequences (2,v) for odd v>=5 have exactly two even terms. Ulam sequences with only finitely many even terms eventually must have periodic successive differences (Finch 1991, 1992abc). Cassaigne and Finch (1995) proved that the Ulam sequences (4,v) for 5<=v=1 (mod 4) have exactly three even terms.
The Ulam sequence can be generalized by the s-additive sequence.
还有cos性质，不过这题可能用不到
当然如果直接用性质，也不需要写啥文章了，就像pe66，我还是从零整理了整个 pell方程和连分数关系的证明过程。
性质
有无限多个。显然做pe到176了，这还是很明显，最大两个的和一定唯一表示，所以至少有一个大于且唯一表示的，所以得证
除了第3个，其它的都不是上两个的和, $U_{n-2}+U_{n}$ 是唯一的计算方案，所以，$U_{n-2}+U_{n} \ge U_{n+1}$, 得证
n大于2时，相邻3个能构成3角形, $U_{n-1}+U_{n} > U_{n-2}+U_{n} \ge U_{n+1}$,得证
(1,2) 的Ulam sequence 是 Complete sequence，也就是任何正整数可以序列中每个数字最多用一次的和表示。直接用集合最小法，假设有集合的数，都是该序列不可表示的，那么取最小的不可表示的数,记为$x_0$，显然它没有出现在序列中，且它大于4, 取最大一个小于它的序列中的数 $0 \leq x_1=x_0-U_n < U_n$, 则也不可表示, 和最小性质矛盾
任意n, $[n,2n)$之间至少有一个 数属于序列, 无限多个和$U_{n+1} \leq 2*U_n$ 得证
(1,2)的序列，i>4, $i,i+1,i+2,i+3,i+4$,至多两个属于序列，首先可以看作在整数中取连续的5个数，那么根据贪心，直接取到$i$是序列中的数，否则我们做平移到i是序列中的数，只会更多。如果$i+1$也是，显然$i+2 = (i)+(2)=(i+1)+(1),i+3=(i)+(3)=(i+1)+(2),i+4=(i)+(4)=(i+1)+(3)$都有多种表示法。如果$i+2$也是，$i+3=(i+2)+(1) = (i)+(3), i+4=(i+2)+(2)=(i)+(4)$。如果$i+3$也是，$i+4=(i+3)+(1)=(i)+(4)$,得证
(u, v)-Ulam 序列 is regular 如果序列的差分，是最终周期性的(也就是除去一定的非周期序列前缀后，剩余部分是周期序列)
paper 法文令人抠头XD, 这个老哥是 诗人作家，业余数学家!?还是重名?
英文还稍微能看，法文只剩公式靠猜为主，用了一下google的pdf翻译功能XD
s-additive sequences s-additive 如果除了开始2个以外的数，正好能表示成s种前面的数之和，因此 Ulam numbers and the (u, v)-Ulam numbers are 1-additive sequences
正整数，单增
给定前2s项，作为基础
对于n>2s, $U_n$ 是大于 $U_{n-1}$的最小整数，满足 $U_{n} = U_i+U_j (u_i\neq u_j,i \neq j)$, 的最小的且正好有s个解
性质 显然, 是必要给出2s项，否则直接中断（因为要s种表示方式）
并且前s+1项 决定了 整个2s项，因为这样才能有2s+1项(有s种表示方式) $U_{2s+1} = U_{1}+U_{2s} = U_{2}+U_{2s-1} =U_{3}+U_{2s-2} = \cdots =U_{s}+U_{s+1}$
因此$U_{s+2}$可取值是$U_{s+1}+U_{1}$ 或 $U_{s+1}+U_{2}$，且满足一串等式类似上面，但是并不保证 下标和为s的函数, 对于可行和来说，只有s+1种，其实就是连等式中不会出现的数只会在前s+1个中
补充定义$U_0=0$
所以说我们有两串连等式
$U_{2s+1} = U_0+U_{2s+1} = U_{1}+U_{2s} = U_{2}+U_{2s-1} =U_{3}+U_{2s-2} = \cdots =U_{s-1}+U_{s+2}$
$U_{2s+2} = U_{1 or 2} + U_{2s+1} = U_{2 or 3}+U_{2s} = U_{2 or 3}+U_{2s-1} =U_{3 or 4}+U_{2s-2} = \cdots =U_{(s) or (s+1)}+U_{s+2}$
上下相减
$U_0 - U_{1 or 2} = U_1 - U_{2 or 3} = U_2 - U_{3 or 4} = \cdots = U_{s-1} - U_{(s) or (s+1)} = 常量$
对于给定具体的一个初始序列这个值是确定的，所以是常量
很明显 这里有s个等差，注意在 $x 或 x+1$ 的取值是在一个确定位置的左侧全部取x，右侧全部取x+1 的，所以最多发生一次 不连续的差，而这个等差序列最大跨度为2个下标差
所以可能的序列有
$A$(前s项以及$U_0$完全等差): $u,2u,3u,\cdots,(s-1)u,su,v,v + u,\cdots,v+(s-2)u,v+(s-1)u$
这个相当于上面常量的表达式在or的选择全部取左侧
$B_1$(前s-1以及$U_0$完全等差): $u,2u,3u,\cdots,(s-1)u,v,su,v + u,\cdots,v+(s-2)u,v+(s-1)u$
看上去和上面交换了正中两项的位置,这个相当于上面常量的表达式除了最后的一项的or取右侧，其余or的选择全部取左侧。
很好的是序列的性质，因为有和($U_{2n+1}$)的控制右侧的序列并不会因为交换了中间两项而改变
$B_2$(前s-1以及$U_0$完全等差): $u,2u,\cdots,v,(s-1)u,v+u,su,\cdots,v+(s-2)u,v+(s-1)u$
这个相当于上面的常量表达式，除了最后两项区or右侧，其它取or左侧，也就是 $U_{s+1}-U_{s-1} = U_{s}-U_{s-2} = U_{s-2}-U_{s-3} = 等差常量$ ,也就是 前s-2项 再配上$U_{s}$ 和 $U_{s+2}$ 都是等差的。
这里比较有意思的是，虽然$U_{s+1}-U_{s-1} = U_{s}-U_{s-2}$中的s+1超过了s，但是本身差是关于 s,s+1 之间对称的，所以$U_{s+1}-U_{s-1} = - (U_{(2s+1)-(s+1)} - U_{(2s+1)-(s-1)} ) = U_{s+2} - U_{s}$。因此序列中依然$u,2u,\cdots,su$都存在，只是位置变了，而后面的部分依然不会变，后面的部分又因为s,s+1之间对称等差性，v，v+u到 (s-1)u 也没变，只是换了位置，然后序列就神奇得像是 交叉了一下而已
$B_{s-1}$: $u,v,2u,v+u,3u,v+2u,\cdots,su,v+(s-1)u$
就是两个序列完全穿插到了一起，也就是上面常量表达式除了第一项取or左侧，其余全部取or右侧
$C$: $v,u,v+u,2u,v+2u,3u,\cdots,v+(s-1)u,su$
就是两个序列完全穿插到了一起,然后再错过一个，也就是上面常量表达式所有项取or右侧
(目前位置不懂为什么要分成ABC三种，因为从组成来看，就是两个序列的穿插结果)
因此，可以用(s,u,v)唯一表示($u\neq v$) s-additives的序列，s决定了和的要求次数，初始序列长度，其中u决定了存在的 $u,2u,3u,\cdots,su$序列,u和v,确定了$v,v+u,v+2u,\cdots,v+(s-1)u$这个序列，这两个序列从小到大排列即可
如果u和v不互质，$gcd(u,v) * (s,u/gcd(u,v),v/gcd(u,v)) = (s,u,v)$
对于s=1，只有A/C类型的序列
u=1 只有 A类型的序列
对于 v = (s+1)u 的 我们称之为自然 s-additive, 因为上面提到的互质，考虑u=1，显然(s,1,s+1) = (s,2,1), 因为数列都是 1~2s
对于 $u\ge 3$ 且 $s>1$ 有性质 取自$v+nu$序列，仅在$ku<v<(k+1)u$时 $U_{3s+k+1} = 2v+(2s-1)u$
例如 (s=3,u=3,v=10):[3,6,9,10,13,16],19,22,25,28,31,34,35(!),37,40…
$3u=9<v=10<(3+1)u=12$ 所以$k=3, i = 3s+k+1=14,U_i=u_{14} = 2v+(2s-1)u = 35$
证明，首先因为序列是通过$u,2u,\cdots,su$和$v,v+u,v+2u,\cdots,v+(s-1)u$以某种穿插形式初始化的，u,v互质不等，v的系数为0或1,所以在序列生成过程中已有的是$(1s)u,v+(0(s-1)+)u$，可能的下一个数是au,u或v+au或2v+au,
首先au不可能，因为不带v的仅有s个递增的数，不可能有s种方案
接下来v+au,刚刚好，选一个ku，再选一个v+(a-k)u,即是连续的又是刚好s个，问题只是可能不是可选的最小
对于2v+au,也就是需要选 v+ku,和v+(a-k)u,这个只会发生一次，因为v+?u,?的取值范围是从0开始的连续整数，所以2v+(a+1)u的方案必定有s+1种。同时当这个2v+au产生时，并不会产生额外的新值
因为2v+au带来的可能是 3v+bu或4v+bu,而3=0+3=1+2,4=0+4=1+3=2+2都不具备构成。
同样 对于2v+au来说，显然不对bu/v+bu产生影响，根据a的值也不对2v+bu的构成产生影响
综上在算下a的具体值和对应下标的值，得证(s>1,u>=3,v) 主要由 $(1~s)u,v+ku,以及一个特殊2v+(2s-1)u (如果有的话)$构成
因此对于s>1的序列，还要研究的就是u=1和u=2的情况
2.0 考虑 u=2
文章是s-additives,所以用的是(s,u,v),本文其实只关注(1,2,>=5奇数)
忽略 v 是偶数，因为性质上 (s,2,2n) = 2(s,1,n)
2.3 (1,2,v>=5奇)
简写作$2,v(2)2v+1,2v+2,2v+3(2),3v,3v+4(4),5v+2,5v+4,5v+10,5v+12,5v+18,5v+20,5v+26,\cdots$
再根据v mod 4来确定最后的模式串是$7v+2,7v+6$或$7v+4,7v+12$
括号数字表示，以该数字递增
和上面证明类似(考虑2的系数和v的系数)，达到2v+1前，只会有2,v+2k构成，且k是从0取到$(v+1)/2$所有整数,换句话说，和的表示总是会选择2，因为如果不选2则至少(v)+(v+2) = 2v+2
接下来2v+2是一个特例,2v不可表示，所以一定是2v+2 = (v+a)+(v+(2-a)),只有a=0
注意到v的系数为1时，加的部分是偶数，所以在$(2v+2,3v]$的范围，(2v+(偶数>2))有超过一种表示例如$(2v+4=v+(v+4)=2+(2v+2))$,对于$(2v+2k = v+(v+2k) = (v+2)+(v+2k-2))$其中$k>=3$, 对于(2v+(奇数>2)),有且仅有表示$2v+(2k+1) = 2+(2v+(2k-1))$,因为如果不选2的话v的系数只能选为1的，而v的系数为1的加的部分是偶数不可能加成2k+1
接下来3v+4,先说为啥没有$3v+1,3v+2,3v+3$,直接上表达式$3v+1=v+(2v+1)=(v+2)+(v+(v-1))$(v的取值范围让 2 != v-1), $3v+2=2+3v=v+(2v+2))$,$3v+3=v+(2v+3)=(v+2)+(2v+1))$
然后是为什么$3v+4$可选,$3=0+3=1+2$所以如果选2的话，3v+2不存在，只能$(v+a)+(2v+(4-a))$,a只能取2,唯一表示
k>=1
$3v+(2k+1) = v+(2v+(2k+1)) = (v+2) + (2v+(2k-1))$, 注意到$v~3v$的等差2的序列全有
所以序列中取最大的4个$(3v)+(3v-6) = (3v-2)+(3v-4)$,k取$[1,(3v-7)/2]$时$3v+(2k+1)$都是有多个表示方法的，需要注意的是这里的增加部分和上面表示略有不同，这里即使增加的部分即使超过了v，也是没有做改写,所以也涵盖了$[4v,5v]$的部分
$3v+(4k+2)$和$3v+4k$注意到这两个都是奇数，而奇数=奇数+偶数，而偶数少得可怜，只有2和2v+2,相反v直到到3v的奇数是没有遗漏的被选择了，所以$3v+4k$是唯一表示$(2v+2)+(v+(4k-2))$而$3v+(4k+2)$则有含上面两个偶数的表示都存在。范围k，$4k-2=2v$即$k=(v+1)/2$都可以也就是$5v+2$
接下来越来越复杂，先看看我们序列有什么
$2$,$v2v+1$的等差2的奇数序列,$2v+2$,$2v+33v$等差2的奇数序列,$3v~5v+2$的等差4的奇数序列
然后我暂时不想再往5v和7v去证明了
定理1 如果 v是大于3的奇数， (2,v)-Ulam序列,仅有两个偶数项
$U_1=2$ and $U_{(v+7)/2} = 2v + 2$
本文仅需要 前½(3v + 11) terms，上面两个是唯一的偶数项（上面列举时已经证明）, 其实上面已经在列举的时候观察到了这两项，但是没有证明仅这两项是偶数
引理2 考虑前(3v+11)/2项
$2,v,(2),2v+1,2v+2,2v+3,(2),3v,(4),5v+2,5v+4,5v+10$
我们上面还剩下 5v+4 和 5v+10没证
$5v+3=(3v)+(2v+3)=(3v+4)+(2v-1)$多解
$5v+4=2+(5v+2)$单解,$3v+2$不存在不能用$(2v+2)+(3v+2)$
$5v+5=(3v)+(2v+5)=(3v+4)+(2v+1)$多解
$5v+6=2+(5v+4)=(2v+2)+(3v+4)$多解
$5v+7=(3v)+(2v+7)=(3v+4)+(2v+3)$多解
$5v+8$ 没有表示方案
$5v+9=(3v)+(2v+9)=(3v+4)+(2v+5)$多解
$5v+10=(2v+2)+(3v+8)$单解
因此说明了 在<=8v+8中 不存在别的偶解，因为如果存在则取存在的最小的且大于2v+2的，则它不能表示成两个偶数之和，否则它表示成a(小于4v+4)+b(大于4v+4),存在更小解b矛盾，
要么表示成奇数之和，注意到在$(8v+8) = (5v+10)+(3v-2)$,也就是$(5v+10)+(v3v-2)$能表示$6v+108v+8$的所有偶数,同样选取$5v+2$和$5v+4$可知从$6v+4~8v+8$都有不只一种表示方法
也就是如果选取的数唯一表示的 取值中有大于$(5v+10)$的，那剩余的部分一定小于$(3v-2)$,设存在的最小大于5v+10的偶数为$5v+2 < v = i(> 5v+10) + j(<3v - 2) <= 8v+8$
那我们关心的还剩下$(5v+10,6v+4)$之间是否还村在唯一表示的偶数
$5v+(2k+1) = (3v+4j) + (2v+(2k+1-4j))$
$4j \in [0,2v-2]$ 的所有4的倍数
$(2k+1-4j) \in [-v,v]$ 的所有奇数
$(2k+1) \in [-v+2,3v-4]$ 的所有奇数都至少有一个以上的表示方式 (这里重复会怎么样？还是只要非端点，内部重复少一次，还是能大于1,毕竟如此的表示方案次数的规律是 从1开始先增后减最后是1 )
所以$5v+(2k+1) \in [4v+2,8v-4]$都是有至少两种表示方法的了
因此证明了8v+8内，有且只有两个偶数项
引理3 x是最小的大于2v+2的偶数，那么取任意奇数r,满足$1\leq r < x-2v$,那么必有i满足$0\leq i \leq v$ and $r+2i\in S$,也就是有比它小的任意奇数加某个2i后 在序列中
反证，如果上述不成立，那么r取满足$r<x-2v$和${r+2i:0\leq i \leq v} 交 S = 空$的最小正奇数(r>=3)，也就是一个r让上述的值都不属于S
也就有$r+2v,r+2v-2$都不属于S
注意到$r+2v = (r-2)+(2v+2) = (r+2v-2)+2$所以$(r-2)$也不属于S，否则$r+2v$唯一表示
因此有${(r-2)+2i:0\leq i \leq v} 交 S = 空$，说明了(r-2)才是最小（这里应该是r不能取大于等于3的, r 取1单独讨论也是满足）
r=1时，显然i取v，$1+2v\in S$ ，所以证毕。
任意 奇数r 满足 $1 \leq r < x - 2v$. 存在i，满足 $0 \leq i \leq v$ and $r + 2i \in S$.
如果$x>8v+8$, $a<b$( 且 a和b是S中的奇数,因为偶数就那两个,不可能了)满足 x=a+b,令r=x-3v,根据引理3,我们存在$0\leq i \leq v$并且$(x-3v)+2i \in S$,
再由引理2的序列，知$\{3v-2i:0\leq i \leq v\} \subseteq S $，就是v到3v之间所有偶数都可以取到，
因此的到a和b的具体值(如果x能表示)$(a,b) = (3v-2i, x-3v+2i)$
对于$0\leq j\leq v, j\neq i$,有$x-3v+2j \notin S$ 因为如果属于，则也能找到对应的$a,b$，那么x的表示方法就不唯一了，因此0~v之间有且仅有唯一的$i$可选来得到a和b的值,
$[x-3v, x-3v+2v = x-v]$之间所有奇数有且只有一个属于S
然后考虑$[x-5v-2,x-5v-2 + 2v = x-3v-2]$ 之间所有奇数的状况
$x-3v+2j =((x-5v-2)+(2j))+(2v+2) = (x-3v+2j-2)+2$
说明如果$x-5v-2+2j \in S$
那么$x-3v+2j$和$x-3v+2j-2$至多只有一个存在,(否则$x−3v+2j$有多种表示方法
同时如果$x-3v+2j-2$不存在，那么$x-3v+2j$唯一表示，所以至少一个存在，
综上，$x-5v-2+2j \in S, 0\leq j \leq v$当前仅当$x-3v+2j$和$x-3v+2j-2$其中一个存在于S
对于$[x-3v, x-v]$之间唯一可能存在的$x-3v+2i$
考虑$i$的取值
如果$0 \leq i < v$, 当且仅当 $x-3v+2i - (2v+2) \in S$ 或 $x-3v+2(i+1) - (2v+2) \in S$,直接由上面的当且仅当得到
如果$i = v$, 和上面不同，这里不取不到$2(i+1)$,首先因为上面证明了 $x-3v+2v = x - v$和$x-3v$不会同时属于S,也因为$x-3v$这个值也不在$[x-5v-2, x-3v-2]$范围中，
其实对于 $0 < j \leq v$, $x-3v+2j = 2+(x-3v+2j-2)=(2v+2)+(x-3v+2j-(2v+2)) \in S$，又$[x-3v,x-v]$仅能有一个奇数出现,第一个等式必不成立
$0 < j \leq v$有$x-3v+2j\in S$ 当且仅当$x-3v+2j-(2v+2)\in S$
所以对于$0<j<v$,$x−3v+2j \in S$得到 $x-3v+2j - (2v+2) \in S, x-3v+2j+2 - (2v+2) \in S, $, 而又由上得到 $x-3v+2j - (2v+2)+(2v+2) \in S, x-3v+2j+2 - (2v+2)+(2v+2) \in S$,和$x-3v+2j+2 \notin S$ 矛盾
所以$i$的可能取值只有$0$和$v$
$i=0$,$(a,b)=(3v,x-3v)$,$x-3v-(2v+2) \in S$ 或$x-3v-(2v+2)+2 \in S $
$x-3v-(2v+2) \in S$, 因为x唯一表示, 所以关于x的补也不属于S:$3v+(2v+2) \notin S$ 和枚举$5v+2 \in S$的矛盾,(依靠x的范围保证了这是两种不同的表示)
所以有 $x-3v \in S$ 当且仅当 $x-5v \in S$ => $x-5v+(2v+2) \in S$ 矛盾,因为$[x-3v,x-v]$仅有一个属于S
$i=v$,$(a,b)=(v,x-v)$,$x-v-(2v+2) \in S$ 或$x-v-(2v+2)+2 \in S $
因为x唯一表示, 所以关于x的补也不属于S:$v+(2v+2) \notin S$ 或 $v+(2v+2)-2 \notin S$ 和枚举的矛盾,(依靠x的范围保证了这是两种不同的表示)
综上 不存在大于8v+8的偶数
周期 是最终周期性的，（就是从某项开始，差分是周期的）
最小的$N(v)$记为 差分的周期,
对于大的n差分循环为$D(v) = S_{N(v)-n}-S_n$ 叫做Fundamental difference
密度$d(v) = N(v)/D(v)$
On the Regularity of Certain 1 -Additive Sequences 这篇论文还给了一个这三个取值的table, 当然对我们来说做题，其实足够了，但是我还是希望证明1.周期存在，2.如何判断进入周期了
定义 如果一个1-additive序列的差分是最终周期性的，称它为regular的
定理2 如果一个1-additive 序列只有有限个偶数项，那么它是regular的
题目虽然是任意个，我们这里只证明仅有2和2v+2为偶数项的,有限项同理，核心是抽屉原理
令f(x) = 1 当x在序列中，f(x) = 0 当x不在序列中
有 $f(x) = f(x-2) xor f(x-2v-2)$
$g(x) = 向量 (f(x) f(x+2) … f(x+4v-2))$
$g(x+4v) = 向量 (f(x+4v) f(x+4v+2) … f(x+4v-2))$
所以g(x) 由与x无关的函数唯一决定 g(x+4v)
g(x) 的状态数为 2v 有限，因此g(x+4v)也是有限的
所以 g(x+4kv) 必定循环
循环证必
注意这里取4v有点大，实际上可以缩小到一定范围都行，比如有paper是按照更小的来取的，这里主要是能制造一个靠固定公式递推的向量即可，足够大，可以完全不考虑其具体大小得到“循环”这个性质
找循环节 直接按照上面的方法能找到一个，然后根据约数缩减即可
仔细一想，因为是从小到大尝试是否是循环节，那么这个值就一定是起始值和循环节，因此不需要约数
继续 我以为证明了有循环节就可以编码了，
然后写完以后，跑得很慢，看了一下论文的table上面的数据，在(2,17),(2,19),(2,21)时，循环节很大，滑窗搜索写得就有太慢了？也许是我写的问题？感觉我写的 (2v+1)k^2起 ，k是循环节，而在21时，循环节已经2e6了，感觉我内存炸掉比结果先来到
差分循环节长度$N$
循环节的差 $D = a_{N+n} - a_n$
比如对于(2,5) 有(N,D) = (32,126)
令$b_n $表示 $2n+1$ 的方案数
对于足够大的n, 因为有且只有两个偶数其实我们就得到 $b_n = b_{n-1} xor b_{n-v-1}$,实际上就是由2或2v+2组成
这里paper提到了ring，// 奈何我暂无相关知识(查了一下 两种运算(加法和乘法)闭合集) XD, 虽然可以抑或，但缺点是抑或没有组合性质，那就加法模2
$b_n = b_{n-1} xor b_{n-v-1} (mod 2)$,$b_n$取值范围在$0,1$中
其实我们把它们变成矩阵和矩阵乘法
初始矩阵，令
$\beta_{(v+1)/2} = (b_{-(v+1)/2} b_{-(v-1)/2} \cdots b_{(v-3)/2} b_{(v-1)/2})^T = (0 0 \cdots 0 1)^T$
也就是注意到$b_{(v-1)/2}$表示的是v可以表达，前面的都是小于v的奇数不论正负，都不能表达，从而产生奇数的序列。
转换矩阵是
$\mathbf{A}_{(v+1)\times (v+1)} = \begin{bmatrix}
除了最后一行是递推，上面的都是平移
这里我们注意到，转换矩阵是模非零，说明矩阵存在，所以循环一定能循环到初始矩阵
我们令$p = (v+1)/2$假设$q, q > p$首次让$\beta_q = \beta_p$
那么
$ N = \sum_{k=p-1}^{q-2} b_k$, 其实就是$\beta$的下标和向量内最大的b的下标差1,然后 统计这之间所有等于1的$b_k$
$D=2(q-p)$,直接就是值的差
特征多项式 $f(x) = det(xI + A) = x^{v+1}+x^v+1， f(-A) = 0$, v的奇数决定了矩阵的长宽是偶数, 用途是加速矩阵高幂次运算
我们之前有递推 $\beta_{n+1} = A \beta_n$,有这两个工具即使枚举就可以很快得到答案了
推到这，我才突然回想，既然在证明循环时，已经有了递推表达式，那就不需要模拟，也不需要上面这样去算
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <bits/stdc++.h> using namespace std;typedef long long ll;#define rep(i,a,n) for (ll i=a;i<n;i++) #define pb push_back ll v ; vector<int > arr; vector<ll> vals; int getidx (int idx) if (idx < v)return 0 ; return arr[(idx-v)/2 ]; } ll work (ll val,ll query) { arr.clear (); vals.clear (); v = val; arr.pb (1 ); vals.pb (v); ll idx = v+2 ; for (int zCnt = 0 ;;idx+=2 ){ auto zo = getidx (idx-2 ) ^ getidx (idx-2 *v-2 ); arr.pb (zo); if (!zo){ zCnt++; }else { if (zCnt == v){ printf ("%lld:%zu %lld\n" ,v, vals.size (),idx-v); query -= 2 + 1 ; ll ans = vals[query % vals.size ()] + (query/vals.size ()) * (idx-v); printf ("[%lld]\n" ,ans); return ans; }else { zCnt = 0 ; vals.pb (idx); } } } return 0 ; }; int main () ll ans = 0 ; rep (i,2 ,11 ){ ans += work (2 *i+1 , 100'000'000'000 ); } printf ("Ans: %lld\n" ,ans); return 0 ; }
回顾 我们虽然只想求 Ulem序列的某种特殊情况sum(2,odd >= 5,10**11)
但是因为资料匮乏，只能自己搜paper啃，学习了s-additives的定义，证明了部分性质。
这个带变量的大量“枚举”第一次这样思考，分类的时候很怕有特殊情况没有考虑到，感觉是不是要去学coq了
另外本题在证明过程中的同一个数字的不同表示法
证明用了不少次反证+最小矛盾的方法
几个引理还是挺漂亮的，利用唯一性和奇偶性和2v+2建立 充要关系
有些paper有点自顶向下证明
在证明有限偶数是这个题的核心，一旦证明了有限偶数，剩余的部分就比较容易了
感觉paper上除了有笔误，证明也不太对？没太懂几个隐含推出是为啥
上面有不少部分和题目本身无关，如s-additives在s>1的情况的性质
这里的向量忽略掉偶数的建立方式和只包含首个v的建立方式，有点意思，简化了初始和边界问题（不过也依赖本身偶数只是穿插到奇数序列中，不影响奇数序列本身的递推公式的性质上，
TODO 整理表述、符号一致性和笔误修复
Ulam Sequence 延伸相关 例如数列密度猜想
cos性质
等等，都在这道题目以外，目前没有深究
ref oeis U(a,2)
mathworld:Ulam Sequence
WolframAlpha
msu: Ulam Sequence
Fundamental difference of Ulam 1-additive sequence starting U(2,2n+1).
1972, Sur les suites s-additives
1990, On the regularity of certain 1-additive sequences
1992, Patterns in 1-Additive Sequences
1994, The regularity of some 1-additive sequences
2016, A Hidden Signal in the Ulam sequence
2018, ULAM SEQUENCES AND ULAM SETS
2018, STRUCTURES IN ADDITIVE SEQUENCES