从“有多少个约数的个位是1”想到的～

mathe

对于4,6,8这三种情况，因子分解形式必然是$2^{r-1} p_1^{t_1}...p_h^{t_h}$形式，并且记$s=k/r$。
其中$2^{r-1}$的因子可以产生个位数为$1,2,4,8,6,2,4,8,6,2,...$的前$r$项，我们记其中2，4，8，6的比例分别为$c_2,c_4,c_8,c_6$
容易看出$c_2>=c_4>=c_8>=c_6$
同样$p_1^{t_1}...p_h^{t_h}$的因子可以产生个位数只能是$1,3,7,9$我们分别记它们的比例为$d_1,d_3,d_7,d_9，d_1+d_3+d_7+d_9=1$
于是对于乘积个位数是2, 4，6，8的比例为$e_2, e_4,e_6,e_8$，于是
$e_2=c_2d_1+c_4d_3+c_8d_9+c_6d_7$
$e_4=c_2d_7+c_4d_1+c_8d_3+c_6d_9$
$e_6=c_2d_3+c_4d_9+c_8d_7+c_6d_1$
$e_8=c_2d_9+c_4d_7+c_8d_1+c_6d_3$
对于固定的$c_2,c_4,c_8,c_6$,它们的关系只有四种
$c_2=c_4=c_8=c_6$,这时$e_2,e_4,e_6,e_8$的取值和$d_i$无关，总是等于$c_2=1/4-1/{4r}, r -= 1(mod 4)$,显然这种模式r要选择k的模4余1的最大因子
$c_2=c_4=c_8>c_6$,这时$e_2=c_2-{d_7}/r, e_4=c_2-{d_9}/r,e_6=c_2-{d_1}/r,e_8=c_2-{d_3}/r$,其中$c_2=1/4, r -= 0(mod 4)$，显然这种模式对于$e_2,e_4,e_8$我们应该让后面只产生1，可以让$e_2,e_4$和$e_8$取到最大值$1/4$
$c_2=c_4>c_8=c_6$,这时$e_2=c_2-{d_7+d_9}/r,e_4=c_2-{d_3+d_9}/r, e_6=c_2-{d_7+d_1}/r,e_8=c_2-{d_1+d_3}/r$,其中$c_2=1/4+1/{4r}, r -= 3(mod 4)$只有这一类概率可能超越1/4.而我们总可以取$d_1=1,d_3+d_9=0$使得$e_4$取到最大值$1/4+1/{4r}$
$c_2>c_4=c_8=c_6$,这时$e_2={d_1}/r+c_6,e_4={d_7}/r+c_6,e_6={d_3}/r+c_6,e_8={d_9}/r+c_6$,其中$c_6=1/4-1/{2r}, r -= 2(mod 4)$
于是各种还不确定的情况我们分别需要凑后面的因子使得$d_1$最小，或$d_7+d_1,d_1+d_3$最小（或者$d_3+d_9,d_7+d_9$最大），或$d_1,d_7,d_3,d_9$最大

mathe

现在我们查看如果不是5的倍数的奇数n的因子中1,3,7,9结尾的数的比例分别为$p_1,p_3,p_7,p_9$,同样奇数m的因子比例有$q_1,q_3,q_7,q_9$,奇数nm的因子比例有$r_1,r_3,r_7,r_9$,那么设$minp,maxp,minq,maxq,minr,maxr$分别为每类比例中的最小值和最大值，$min2p,max2p,min2q,max2q,min2r,max2r$分别为每类比例中两两和的最小和最大值，那么必然有下面的重要性质
  $min2p+max2p=min2q+max2q=min2r+max2r=1$
  $min2r>=\max{min2p,min2q}, max2r<=\min{max2p,max2q}$
  $minr>=\max{minp,minq}, maxr<=\min{maxp,maxq}$
由于11#中各种方案的目的就是求某个$r_i$或两个和最大或最小，上面性质中说明了通常混合方案不会更好。
比如11#中要让$d_3$最大，我们已经找到某个不错的$d_3$,那么要找到更好的方案，我们只需要穷举所有maxp和maxq都大于当前已经找到的$d_3$的方案的混合方案即可
我们已知各种基本方案先按$maxp$从大到小分类排列是(去除$p_1=1$情况，这种方案和其它方案组合并不产生新方案）
$9^2: p_1=2/3,p_9=1/3$对应$maxp=2/3,minp=0$
$9^4: p_1=3/5,p_9=2/5$对应$maxp=3/5,minp=0$
$9^6: p_1=4/7,p_9=3/7$对应$maxp=4/7,minp=0$
...
$3^1: p_1=p_3=1/2; 7^1:p_1=p_7=1/2, 9^{2t-1}:p_1=p_9=1/2$对应$maxp=1/2,minp=0$
$3^2: p_1=p_3=p_9=1/3; 7^2: p_1=p_7=p_9=1/3$对应$maxp=1/3,minp=0$
$3^4,7^4: p_1=2/5,p_3=p_7=p_9=1/5$对应$maxp=2/5,minp=1/5$
...

mathe

于是从表格中已经复合变换的性质容易推断出，在$s=k/r$是偶数时，$d_9$的最大值是$1/2$,使用模式$9^1*1^{s/2-1}$就可以取到
而在s是奇数是，我们可以选择$9^{s-1}$模式，让$d_9$取到最大，这个比例已经不小于1/3了（需要注意s是奇数时模式$3^1$等不可用，所以已经不存在单项最大概率大于$1/3$的分布了，我们可以得出$9^{s-1}$必然优于所有复合模式
同样在$s$是偶数时，$d_3,d_7$的最大值$1/2$都可以在$3^1*1^{s/2-1}$和$7^1*1^{s/2-1}$时取到
而在$s$是大于1的奇数时，可能要去$s$的某个的奇数因子$u$,然后模式$3^{u-1}*1^{s/u-1}$和$7^{u-1}*1^{s/u-1}$可以取到最优值(需要注意除了$9^{2h}$模式以外，所有其它类型中3,7本来就已经取到最大概率，所以复合概率没法更优秀，而$9^{2h}$模式的复合只能让3和7的频率相互平均，不会将1或9的概率转移到3和7，所以不会引出更优秀的方案)
余下的几种情况比如让$d_1$最小和$d_1+d_7,d_1+d_3$最小就很复杂了，会出现组合方案,比如$s=6$时，$3^2*13^1$可以让$d_1=1/6$

mathe

所以当个位数要求是4，那么k如果存在除以4余数为3的因子，取最小的这样的因子作为r,那么使用$2^{r-1}1^{s-1}$可以得到最大概率$1/4+1/{4r}$,而如果k不存在除以4余数为3的因子而且k是4的倍数，那么使用$2^3 1^{k/4-1}$可以得到最大概率$1/4$
而如果k所有奇素因子都是$4k+1$形式而且是奇数，那么只能使用$2^{k-1}$形式得到最大概率$1/4-1/{4k}$
而如果k所有奇素因子都是$4k+1$形式而且是2的倍数(但是不是4的倍数),我们总可以试验第四种方案，使用其一个模4为2的因子，但是这种情况结果比较复杂，需要验证比较不同情况下哪种更好。

mathe

对于奇数s,
可以产生模式
$3^2: p_1=p_3=p_9=1/3; 7^2: p_1=p_7=p_9=1/3$对应$maxp=1/3,minp=0$
$3^4,7^4: p_1=2/5,p_3=p_7=p_9=1/5$对应$maxp=2/5,minp=1/5$
...
以及$9^2, 9^4,...$
我们先考虑
$3^2: p_1=p_3=p_9=1/3; 7^2: p_1=p_7=p_9=1/3$对应$maxp=1/3,minp=0$
$3^4,7^4: p_1=2/5,p_3=p_7=p_9=1/5$对应$maxp=2/5,minp=1/5$
...
之间相互复合能够产生的情况
记\(f_0(a)=\frac{a+1}{4a+3}, f_1(a)=\frac{a}{4a+3},f_2(a)=\frac{a+1}{4a+1},f_3(a)=\frac{a}{4a+1}\)
于是前面各种模式产生的$[p_1,p_3,p_7,p_9]$,在s模4余1时，为
\(w_1(s)=[f_2(s),f_3(s),f_3(s),f_3(s)]\)
在s模4余3时，概率为
\(u_1(s)=[f_0(s),f_0(s),f_1(s),f_0(s)]\)或\(u_2(s)=[f_0(s),f_1(s),f_0(s),f_0(s)]\)
我们并且记
\(w_2(s)=[f_3(s),f_3(s),f_3(s),f_2(s)]\)
经计算可以知道任何一种概率分布为$u_i(s)$或$w_i(s)$和另外一种$u_j(t)$或$w_j(t)$模式混合，
结果必然形如$u_k(x)$或$w_k(x)$,具体转化如下,其中用$\star$代表模式混合
\(\begin{cases}
w_1(s)\star w_1(t) = w_1(4st+s+t)\\
u_1(s)\star u_1(t) = w_2(4st+3s+3t+2)\\
u_2(s)\star u_2(t) = w_2(4st+3s+3t+2)\\
w_2(s)\star w_2(t)  = w_1(4st+s+t)\\
u_1(s)\star u_2(t) = w_1(4st+3s+3t+2)\\
w_1(s)\star w_2(t) = w_2(4st+s+t)\\
u_1(s)\star w_1(t) = u_1(4st+s+3t)\\
u_1(s)\star w_2(t) = u_2(4st+s+3t)\\
u_2(s)\star w_1(t) = u_2(4st+s+3t)\\
u_2(s)\star w_2(t) = u_1(4st+s+3t)
\end{cases}\)
也就是代表各种$3^{2a},7^{2b}$模式混合后得到的$[p_1,p_3,p_7,p_9]$的概率分布只有$u_1,u_2,w_1,w_2$这四种，而且其中分母完全由混合模式的因子数目唯一确定
而这四种方案$u_1$代表7的概率略小，$u_2$代表3的概率略小，$w_1$代表1的概率略大，$w_2$代表9的概率略大的模式
而如果继续混合\(9^{2c}\)模式，相当于会对原先模式中的$p_1$和$p_9$进行加权平均给新的$p_1,p_9$,同样会将$p_3,p_7$进行加权平均分配给新的$p_3,p_7$
加权平均后最大值会小于原先的最大值，最小值都会大于原先的最大值。由于模式3和7总是由对称方案存在，这表明要让3或7的概率最大或最小的方案都不会使用\(9^{2c}\)的模式

mathe

现在我们可以继续查看个位数要求是4的情况，现在唯一余下还没有分析的是k的所有奇数因子都是模4余1的情况而且k是2的倍数但是不是4的倍数，于是这时$r -=2 (mod 4)$, s是奇数，为了$d_7$最大，在s模4余3时选择$u_2$模式，$d_7=1/4+1/{4s}$,而在s模4余1时,$w_1$和$w_2$方案没有任何区别，都有$d_7=1/4-1/{4s}$。
也就是$s -=3(mod 4)$,个位是4的概率可以达到$1/4-1/{4r}+1/{4sr}$,而$s -= 1(mod 4)$时，个位是4的概率可以达到$1/4-1/{4r} -1/{4sr}$
经计算可以知道不会比方案1好。
我们总是记q为k中最小的模4为3的素因子，于是对于要求个位数是4的情况的策略如下

个位数是4的最大概率	模式	概率
存在q,而且k=qs	$2^{q-1}11^{s-1}$	$1/4+1/{4q}$
不存在q,4|k, k=4s	$2^3*11^{s-1}$	$1/4$
不存在q,k奇数	$2^{k-1}$	$1/4-1/{4k}$
不存在q, k=2s, s奇数	$2^{s-1}11$	$1/4-1/{4s}$

mathe

而个位数为8的选择，参考27#表格有$d_1+d_3>=1/4$而且$d_9<=1/2$，所以如果$4|r$应该优先选择第二种模式使得8的概率可以达到$1/4$.
如果$r$不是4的倍数，
使用第一种模式概率可以达到$1/4-1/{4r}$,其中r是最大模4余1的因子
使用第三种模式要求k存在模4余3的因子，概率可以达到$1/4+1/{4r}-{d_1+d_3}/r$,由于余下部分不能是4的倍数，如果余下部分也存在模4余3的因子u,$d_1+d_3$可以达到最小值$1/2-1/{2u}$,得到总概率为
   $1/4-1/{4r}+1/{2ur}=1/4-{u-2}/{4ur}$,显然这里$ur -= 1(mod 4)$而且是k最大模4余1的因子,u是其中最小模4余3的因子，不好于第一种模式
  而如果余下部分不存在模4余3的因子但是是2的倍数，根据27#表格，$d_1+d_3$可以取到最小值$1/2+0=1/2$,得到总概率$1/4-1/{4r}$
  而如果余下部分不存在模4余3的因子而且是奇数，那么$d_1+d_3$只能取到$1/2+1/{2q}$,其中$q=k/r$,所以总概率为$1/4-1/{4r}-1/{2k}$
    这表明如果k最小一个模4余3的因子是u时，设h是其最大奇数因子，我们要比较第一种方案$1/4-u/{4h}$和这里的$1/4-1/{4k}-1/{2h}=1/4-3/{4h}$,通常这个方案优于第一种模式。
使用第四种模式要求k是偶数，概率可以达到$1/4-1/{2r}+{d_9}/r$,这时余下部分是奇数，根据27#,$d_9$最小值只能$1/4+1/4-1/{2q}=1/2-1/{2q}$
   所以总概率为$1/4-1/{2k}$,和第一种概率相同

所以如果k是4的倍数，选择模式二$2^{k-1}$得到概率$1/4$
如果k不是4的倍数，其最大奇数因子模4余1，那么采用第一种模式$2^{r-1} 11^{k/r-1}$可以得到概率$1/4-1/{4r}$,其中$r$是k的奇数部分
如果k不是4的倍数，其最大奇数因子模4余3，那么如果k是偶数,k=2r，采用第三种模式，选择$d_1+d_3=1/2$, 即模式$2^{r-1}19^1$,得到概率$1/4-1/{4r}=1/4-1/{2k}$
                                                                       如果k是奇数，采用第三种模式，取$d_1+d_3=1$,即模式$2^{k-1}$得到概率$1/4-3/{4k}$        

mathe

如果有一个模式约数末位数为1,7,9,3的概率分别为$p_1,p_7,p_9,p_3$,另外一个模式为$q_1,q_7,q_9,q_3$,两个模式混合后的概率为$r_1,r_7,r_9,r_3$,那么我们必然有
\(\begin{cases}
r_1=p_1q_1+p_7q_3+p_9q_9+p_3q_7\\
r_7=p_1q_7+p_7q_1+p_9q_7+p_3q_9\\
r_9=p_1q_9+p_7q_7+p_9q_1+p_3q_3\\
r_3=p_1q_3+p_7q_9+p_9q_7+p_3q_1
\end{cases}\)
记$P=[p_1,p_7,p_9,p_3], Q=[q_1,q_7,q_9,q_3], R=[r_1,r_7,r_9,r_3]$,
我们把上面的关系式记为$R=P\star Q$
另外我们可以记$P(x)=p_1+p_7x+p_9x^2+p_3x^3$等
于是容易得出$R=P\star Q$的充要条件是$R(x) -= P(x) Q(x) (mod x^4-1)$
记$|P|=p_1+p_7+p_9+p_3$
于是我们有性质:
i) 交换律$P\star Q = Q\star P$
ii) 分配律$(P+Q)\star R = P\star Q + R\star Q$，其中+就是普通向量加法
iii)单位元$[1,0,0,0]\star P = P$
iv)移位变换\(\begin{cases}[0,1,0,0]\star [x,y,z,w] = [w, x, y, z] \\ [0,0,1,0]\star [x,y,z,w] = [z,w, x, y] \\ [0,0,0,1]\star [y,z,w,x] = [w, x, y, z] \end{cases}\)
v)吸收变换 $ [c,c,c,c] \star P = [c|P|, c|P|, c|P|, c|P|] = |P| [c,c,c,c]$

另外，对于某个非5倍数的奇数n,其因子中末位数为1,7,9,3的比例构成的向量称为其概率向量，记为P(n)。而我们另外将$A(n)=P(n)-[1/4,1/4,1/4,1/4]$称为n的波动向量。
我们容易看出$P(n)\star P(m) = P(u)$的充分必要条件是$A(n)\star A(m)=A(u)$.
特别的$P(1)=[1,0,0,0]$是所有$P(.)$关于$\star$计算的单位元，而$W_1=[3/4,-1/4,-1/4,-1/4]$是所有$A(.)$关于$\star$计算的单位元。
另外我们记波动向量集合$B(k)={ k*A(u)| 其中u是一个没有因子5的奇数而且u的因子数目正好是k}$，那么$W_1 \inB(k)$,而且如果$m|n$,那么必然有$B(m)$是$B(n)$的子集
根据定义，我们有，对于任意整数$m>1,n>1$,那么应该有$B(m*n)={a\star b| a\in B(m), b\in B(n)}$

mathe

现在基本模式表格
记$I=[1,0,0,0],J=[1,1,1,1],N=[0,1,0,0], N^2=[0,0,1,0],N^3=[0,0,0,1],T=I+N^2$
记$W_x=[3/{4x},-1/{4x},-1/{4x},-1/{4x}], V_x=[1/{2x},-1/{2x},-1/{2x},1/{2x}],H_x=[1/{2x},0,-1/{2x},0], K_x=[1/{4x},-1/{4x},1/{4x},-1/{4x}]$

约数数目	模式	概率向量	波动向量
n+1	$11^n$	$I$	$W_1$
4k+1	$3^{4k};7^{4k}$	$J/4+W_r$	$W_r$
2k+1	$19^{2k}$	$T/2+H_r$	$K_1+H_r$
4k+3	$3^{4k+2}$	$J/4-N\star W_r$	$-N\star W_r$
4k+3	$7^{4k+2}$	$J/4-N^3\star W_r$	$-N^3\star W_r$
4k+2	$3^{4k+1}$	$J/4+V_r$	$V_r$
4k+2	$7^{4k+1}$	$J/4+N\star V_r$	$N\star V_r$
2k+2	$19^{2k+1}$	$T/2$	$K_1$
4k+4	$3^{4k+3} ;7^{4k+3}$	$J/4$	$0$

需要注意的是第二列的参数都正好是第一列中的约数数目$r$。
其中I和任意其它模式复合保持其它模式,$1/4 J$和其它模式复合必然是$1/4 J$两者都不能派生新模式

mathe

我们计算可以有$J\star J=4J, J\star W_x =0, J\star V_x =0, J\star H_x=0, J\star K_x=0$
$W_x = I/x -J/{4x}$,
所以$W_x\star W_y=I/{xy}-J/{4xy}=W_{xy}, W_x\star V_y = {V_y}/x=V_{xy}, W_x\star H_y={H_y}/x=H_{xy},W_x\star K_y={K_y}/x = K_{xy}$
$V_x\star V_y=1/{4xy} (I-N-N^2+N^3)^2=1/{xy}(N^3-N)=-2N\star H_{xy}$
$V_x\star H_y=1/{2xy}(I-N-N^2+N^3)=V_{xy}, V_x\star K_y = 0$
$H_x\star H_y=H_{xy}, H_x\star K_y=0, K_x\star K_y=K_{xy}$
$T\star T=2T, T\star W_x = 2K_x, T\star V_x = T\star H_x=0, T\star K_x = 2K_x$
所有有基本乘法公式
$J\star J=4J, J\star W_x =0, J\star V_x =0, J\star H_x=0, J\star K_x=0, W_x\star W_y=W_{xy}, W_x\star V_y=V_{xy}$
$W_x\star H_y=H_{xy},W_x\star K_y = K_{xy}, V_x\star V_y= -2N\star H_{xy}, V_x\star H_y=V_{xy}, V_x\star K_y=0$
$H_x\star H_y=H_{xy}, H_x\star K_y=0, K_x\star K_y=K_{xy}, T\star T=2T, T\star W_x = 2K_x, T\star V_x = T\star H_x=0, T\star K_x=2K_x$
另外还有$V_x=-N^2\star V_x, H_x=-N^2\star H_x, K_x=-N\star K_x$
然后我们把上面表格中的方案两两组合，很多组合得出的概率表达式会被前面的模式覆盖掉（也就是我们可以找到更简单的模式产生相同的结果），就不需要列出了，
新增加的有:

约数数目	最简模式	波动向量
(4s+1)(2t+1)	$7^{4s}19^{2t}$	$K_{4s+1}+H_r$
(4s+1)(2t+2)	$7^{4s}19^{2t+1}$	$K_{4s+1}$
4(2s+1)(2t+1)	$3^{4s+1)7^{4t+1}$	$2H_r$
4(2s+1)(2t+1)	$3^{4s+1)13^{4t+1}$	$-2N\star H_r$
4(2s+1)(2t+1)	$7^{4s+1)17^{4t+1}$	$2N\star H_r$
(4s+3)(4t+2)	$3^{4s+2)13^{4t+1}$	$-N\star V_r$
(4s+3)(4t+2)	$7^{4s+2)17^{4t+1}$	$-V_r$
(4s+3)(4t+3)	$7^{4s+3)17^{4t+3}$	$N^2W_r$
(4s+3)(2t+1)	$3^{4s+2}19^{2t}$	$K_{4s+3}-N\star H_r$
(4s+3)(2t+1)	$7^{4s+2}19^{2t}$	$K_{4s+3}+N\star H_r$
(4s+3)(2t+2)	$7^{4s+2}19^{2k+1}$	$K_{4s+3}$
8(2s+1)(2t+1)(2r+1)	$3^{4s+1)13^{4t+1}23^{4r+1}$	$-2N\star V_r$
16(2s+1)(2t+1)(2r+1)(2u+1)	$3^{4s+1)13^{4t+1}23^{4r+1}43^{4u+1}$	$-4H_r$
32(2s+1)(2t+1)(2r+1)(2u+1)(2v+1)	$3^{4s+1)13^{4t+1}23^{4r+1}43^{4u+1}53^{4v+1}$	$-4V_r$