若干有趣的问题

最近时常碰到一些有趣的问题，在这里记录一下我对这些问题的初步想法和在网上搜到的资料

OEISA004125

问题背景

2024.3.24:今天vp的时候碰到相关的题目分析复杂度时想到的。

问题简介

一个正整数对小于等于自己当前值的正整数取模，结果的的期望是多少。
该问题也就是求n分之一的下式：$$f(n)=\sum_{i=1}^n (n\bmod i)$$

简单分析

一次取模后，值不足原来的一半，所以有一个$\frac{n^2}2$的上界；这个结论也可以通过余数不会大于除数而求和得到。

问题结论

事实上，有一个等式把该问题进行转换：
$$\sum_{i=1}^n (n\bmod i)=n^2-\sum_{i=1}^n\sigma(i)$$
其中$\sigma$是除数和函数。

这个式子证明大概可以按照如下思路，对于每个$(n\bmod i)$，$i$作为除数出现在$i,2i,3i…$中，出现的次数恰好等于$\left\lfloor\frac ni\right\rfloor$，这个次数乘以$i$后刚好等于$n$减去余数。

而除数和函数是积性函数，可以多项式复杂度内求解。

该数列本身的更多信息可参见oeis。

参考资料

Jeffrey Shallit,Answer,2024.3.24

拓展问题

一个正整数对小于等于自己当前值的正整数取模，需要多少次操作才能变成0

最坏情况

每次$n_i$都对$\left\lceil \frac{n_i+1}2\right\rceil$取模，当$n$处于$1$到$10^8$的范围内时，需要的次数大约在$1.4log_2(n)$左右。

期望情况

根据该数列的信息，我猜测期望仍然是$O(log_2(n))$的。

OEISA003042

问题背景

2024-03-13：今天jwong学长和我探讨了关于n阶格雷码编码方案数的问题。

问题简介

如果将$2^n$个长为n的二进制串组成一个序列,使得将
序列按圆形排列时一对相邻的二进制串只有一位不同，则称这些序列为n阶格雷码或简称格雷码(Gray code)。

问不同的n阶格雷码有多少种。

简单分析

首先，可以肯定的是，n阶格雷码编码一定是存在的。

在数模电课程给出了一种给出n阶格雷码的简单生成方案，即在n-1阶格雷码复制成两份，前一份在最高位加上0，后一份顺序翻转并在最高位加上一。

考虑对于任意两位，他们的01排布都是不同的，所以任意排列原方案的每一位，就能得到n!种方案，这可以作为该问题的一个下界。

问题结论

之后，我尝试通过写程序枚举方案观察性质。我发现有不属于上面提到的n!种方案里任何一种的其它方案，说明这个问题的答案很大。而在思索一番后，也没有找到合适的解决方案。

最后通过网络搜索，我发现该问题是一个经典问题OEISA003042。该问题前六项位：1, 2, 12, 2688, 1813091520, 71676427445141767741440。其中n=6是目前解出的最大n值，解出时间是2010年，并于2012年被验证。