两个数列的关系

lsr314

定义函数$φ_0(n)=n,φ_k(n)=φ(φ_(k-1)(n))$,即对$n$求$k$次欧拉函数。易知对每个正整数$n$，存在正整数$t$使得$φ_t(n)=1$，我们记$φ_0(n)，φ_1(n)，……,φ_t(n)$的最小公倍数为$L(n)$.
定义函数$f(n)$为不超过$n$且与$L(n)$互素的正整数的个数。
这个数列的前几项为:
$1, 1, 1, 2, 2, 2, 2, 4, 3, 4, 4, 4, 4, 4, 4, 8, 8, 6, 6, 8, 6, 8, 8,8, 10, 8, 9, 8, 8, 8, 8, 16, 8, 16, 8, 12, 12, 12, 12, 16, 16, 12, 12, 16, 12, 15, 15, 16, 14, 20, 16, 16, 16, 18, 20, 16, 18, 15, 15, 16, 16, 16, 18, 32, 16, 16, 16, 32, 16, 16, 16, 24, 24, 24, 20, 24, 17, 24, 24, 32, 27$
用这个数列的前几项在OEIS中搜索，得到一个数列：http://oeis.org/A110884，前几项为：
$1, 1, 1, 2, 2, 2, 2, 4, 3, 4, 4, 4, 4, 4, 4, 8, 8, 6, 6, 8, 6, 8, 8, 8, 10, 8, 9, 8, 8, 8, 8, 16, 8, 16, 8, 12, 12, 12, 12, 16, 16, 12, 12, 16, 12, 16, 16, 16, 14, 20, 16, 16, 16, 18, 20, 16, 18, 16, 16, 16, 16, 16, 18, 32, 16, 16, 16, 32, 16, 16, 16, 24, 24, 24, 20, 24, 16, 24, 24, 32, 27$
这个数列,记为$E(n)$,和$f(n)$相似度很高，但是第$46, 47, 58, 59, 77$项相差$1$:
$0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0$
所以问题是，这两个数列有什么关系，什么时候相等，什么时候不相等，不相等的时候差额是多少？

补充一下$E(n)$的定义：
定义数列$c(1)=1,c(k+1)=n*φ(c(k))$,由于$n|c(k+1)$,易知$(c(k+1))/(c(k))$是单调不增的，所以存在极限，这个极限记为$E(n)$.

mathe

设$n=p_1^{\alpha_1}p_2^{\alpha_2}...p_t^{\alpha_t}$
而除了上面素因子外，L(n)还包含素因子$p_{t+1},...,p_s$
于是显然$(p_1-1)(p_2-1)...(p_s-1)$的所有素因子也都是$p_1,p_2,...,p_s$之一。
我们可以假设$(p_1-1)(p_2-1)...(p_s-1)=p_1^{\beta_1}p_2^{\beta_2}...p_s^{\beta_s}$
A110884中定义了$c_1=1,c_{k+1}=\varphi(n c_k)$于是对于给定的n,显然对于充分大的k,$c_k$的所有素因子将正好是$p_1,p_2,...,p_s$，于是我们可以假设某个$c_k=p_1^{x_1}p_2^{x_2}...p_s^{x_s}$,其中$x_i>=1$
于是根据定义必然有
$c_{k+1}=p_1^{x_1+\alpha_1+\beta_1-1}...p_t^{x_t+\alpha_t+\beta_t-1}p_{t+1}^{x_{t+1}+\beta_{t+1}-1}...p_s^{x_s+\beta_s-1}$
于是$E_n={c_{k+1}}/{c_k}=np_1^{\beta_1-1}p_2^{\beta_2-1}...p_s^{\beta_s-1}={n(p_1-1)(p_2-1)...(p_s-1)}/{p_1p_2...p_s}$
这个表达式代表$n(1-1/{p_1})(1-1/{p_2})...(1-1/{p_s})=\sum_{h=0}^s (-1)^h \sum_{1<=i_1<i_2<...<i_h<=s}\frac{n}{\prod_{t=1}^h p_{i_t}}$
而楼主定义的结果根据容斥原理是$\sum_{h=0}^s (-1)^h \sum_{1<=i_1<i_2<...<i_h<=s}\floor{\frac{n}{\prod_{t=1}^h p_{i_t}}}$
很显然，如果$p_1p_2...p_s|n$,那么两者必然相等，而不相等的情况，就要看运气了，还是有相等的可能，只是可能性不大。
比如n=3时有$s=2,p_1=3,p_2=2$
所以$f(3)=\floor{3/1}-\floor{3/2}-\floor{3/3}+\floor{3/6}=1$正好等于$E(3)=3/1-3/2-3/3+3/6=1$
但是n=6时同样有$s=2,p_1=3,p_2=2$,
这时由于$f(6)$表达式里面每项需要取整的数本身就是整数，两者必然相等，也就是$f(6)=\floor{6/1}-\floor{6/2}-floor{6/3}+\floor{6/6}=E(6)$

lsr314

mathe 发表于 2018-8-22 11:19
设$n=p_1^{\alpha_1}p_2^{\alpha_2}...p_t^{\alpha_t}$
而除了上面素因子外，L(n)还包含素因子$p_{t+1},.. ...

前100个数里有95个相等，前1000个数里有833个相等，1000以内有168个素数，其中有138个相等，比例是82%，与合数几乎一样。
前1000个素数里有764个相等，这个比例非常高了。注意此时取整符号里的数几乎都不是整数，所以这些素因子是否存在一定的模式，导致两者非常接近？

mathe

统计更大的范围会完全不同，对于越小的n,|E(n)-f(n)|越小，所以是零的概率越大，但是对于充分大的n,随着差值波动范围的变大，等于0的概率应该会越来越小

mathe

估算了一下，对于充分大的n,如果L(n)有s个不同的素因子，那么，E(n)等于f(n)的概率应该接近＄sqrt(6/{2^s\pi})$

mathe

n=10000以内2649个,n=100000以内38721个，n=1000000, 共 506857个，而10000000，涨到6134846个。
两个数列最大差值
n=46, E=16, f=15, diff=1
n=290, E=64, f=66, diff=2
n=2513, E=512, f=515, diff=3
n=2668, E=512, f=508, diff=4
n=17437, E=3072, f=3067, diff=5
n=20401, E=4096, f=4102, diff=6
n=50761, E=9216, f=9223, diff=7
n=70963, E=12288, f=12296, diff=8
n=103646, E=18432, f=18442, diff=10
n=103729, E=18432, f=18443, diff=11
n=316122, E=55296, f=55308, diff=12
n=316263, E=55296, f=55309, diff=13
n=659893, E=110592, f=110578, diff=14
n=1186903, E=196608, f=196624, diff=16
n=1348297, E=221184, f=221166, diff=18
n=2338132, E=393216, f=393235, diff=19
n=2339906, E=393216, f=393236, diff=20
n=3583609, E=589824, f=589802, diff=22
n=7448278, E=1179648, f=1179623, diff=25
n=9658309, E=1572864, f=1572895, diff=31
前100000个数的差值分布:
diff[-8]=1 diff[-7]=3 diff[-6]=17 diff[-5]=60 diff[-4]=201 diff[-3]=878 diff[-2]=3882 diff[-1]=14004 diff[0]=61278 diff[1]=14466 diff[2]=3900 diff[3]=983 diff[4]=256 diff[5]=57 diff[6]=11 diff[7]=2 diff[8]=0
可以看出前后两数比例大概是4倍关系
前10000000个数的差值分布
diff[-31]=1 diff[-30]=0 diff[-29]=0 diff[-28]=0 diff[-27]=0 diff[-26]=0 diff[-25]=1 diff[-24]=0 diff[-23]=1 diff[-22]=1 diff[-21]=2 diff[-20]=4 diff[-19]=7 diff[-18]=4 diff[-17]=19 diff[-16]=38 diff[-15]=57 diff[-14]=85 diff[-13]=178 diff[-12]=399 diff[-11]=757 diff[-10]=1564 diff[-9]=3060 diff[-8]=6638 diff[-7]=14216 diff[-6]=31316 diff[-5]=67564 diff[-4]=152805 diff[-3]=342789 diff[-2]=783267 diff[-1]=1675370 diff[0]=3865152 diff[1]=1663590 diff[2]=785463 diff[3]=343480 diff[4]=148613 diff[5]=63254 diff[6]=27519 diff[7]=11744 diff[8]=5377 diff[9]=2548 diff[10]=1346 diff[11]=720 diff[12]=423 diff[13]=234 diff[14]=146 diff[15]=97 diff[16]=41 diff[17]=40 diff[18]=21 diff[19]=17 diff[20]=9 diff[21]=10 diff[22]=7 diff[23]=1 diff[24]=1 diff[25]=2 diff[26]=0 diff[27]=0 diff[28]=0 diff[29]=0 diff[30]=0 diff[31]=0
前后比例减低到大概只有两倍了