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

282842712474

之前遇到的一道小学题目

一个数字刚好有12个约数，那么它最多有多少个约数的个位数字是3

这个题目并不复杂，答案是6。

由此可以引申出两个问题：

1、有什么直观的方法得到答案是6？

2、一般化，如果刚好有$k$个约数，那么最多有多少个约数的个位数字是$n\in \{0,1,...,9\}$

gxqcn

\(\because 12=(1+1)(1+1)(1+2)\)
\(\therefore m=p_1p_2p_3^2\) （\(p_i\) 为不同的素数）
又 \(3^1\equiv 3, 3^2\equiv 9, 3^3\equiv 7, 3^4\equiv 1 \pmod{10}\)
故可以考虑让 \(p_1\equiv p_2\equiv 3,  p_3\equiv 1 \pmod{10}\)
从而  \(p_1\equiv p_1p_3\equiv p_1p_3^2\equiv p_2\equiv p_2p_3\equiv p_2p_3^2 \equiv 3 \pmod{10}\)

mathe

可以写成$p_1p_2^5$,其中$p_1=3(mod 10),p_2=1(mod 10)$

gxqcn

感觉楼上的方法非常好，具有一般性，达到最优化。

1）对于要求的个位数 \(n\in\{1,2,3,5,7,9\}\) 时，

某数 \(m\) 刚好有  \(k\) 个约数，
若 \(k\) 为素数，那该数仅有一个素因子，很容易分析；
若 \(k\) 为合数，表达为 \(k=p*r\)，其中 \(p\) 为 \(k\) 的最小素因子，
令 \(m=p_1^{p-1}p_2^{r-1}, p_1\equiv n, p_2\equiv 1 \pmod{10}\),
基本可以达到最优（我只归纳了下，未严格证明，也许不正确）。

2）对于剩余的情形，\(n\in\{0,4,6,8\}\)，情况略复杂一些。

282842712474

gxqcn 发表于 2018-5-31 17:17
感觉楼上的方法非常好，具有一般性，达到最优化。

1）对于要求的个位数 \(n\in\{1,2,3,5,7,9\}\) 时，

正是“基本可以达到最优，但却没办法直观地证明”的困难。

哪怕一开始的特例，答案是6个，构造出6个的情况容易，遍历所有可能得到最多是6个也不难。问题是：

1、如何简单地严格证明是6个？
2、如果对于1，没有简明的结果，那么能不能退而求其次：答案是6个有没有直观（可以不严谨）的理解。

事实上，6=12/2，这让我联想到，是不是答案总是小于等于$k/2$？

mathe

这道题目一般情况答案还是比较复杂的，需要分类
个位数是1和5的情况最简单，显然可以选择所有素因子个数都是1和5，于是所有约数个位也都是1和5,其中对于末尾数为5的情况，显然只能选择5的幂。
个位是0的情况有点复杂，显然这个数必然有素因子2和5,可以假设其为$2^a 5^b p_1^{t_1}p_2^{t_2}...p_h^{t_h}, k=(a+1)(b+1)(t_1+1)...(t_h+1)>=4$而且k必须是合数
于是其个位数为0的约数数目为$ab(t_1+1)...(t_h+1)=a/{a+1}b/{b+1}k$,于是显然a和b越大越好，而且在$(a+1)(b+1)$固定的情况下，a和b越接近越好，显然我们必然选择$k=(a+1)(b+1)$,而且要求这种分解方法将k分解为两个最接近的因数。比如k=18,那么我们应该选择18=3*6,于是a=2,b=5,得到结果2*5=10种。而对于这种情况，数目是可以超过$k/2$的。
对于个位要求是3,7,9的情况，同样设这个数为$p_1^{t_1}p_2^{t_2}...p_t^{t_h}, k=(t_1+1)(t_2+1)...(t_h+1)$。首先显然素因子2和5必然不能出现，不然结果必然不是最优的。
其次，其中必然有某个$p_i$尾数是3,7或9（也就是不能所有素因子尾数都是1)，不凡设这个数是$p_1$,于是对于任意一个奇数x, 容易看出$x*1,x*p_1,x*p_1^2,x*p_1^3,x*p_1^4,...$末尾数的周期必然是4或2（9的周期是2,3和7的周期是4）
于是我们可以将所有因子分成$(t_2+1)(t_3+1)...(t_h+1)$类，其中每一类第一个数不含素因子$p_1$,第二个数为第一个数乘上$p_1$,第三个为第二个乘上$p_1$,...
于是我们知道由于每一类数末尾数周期不小于2，所以除非这类第一个数末尾就是要求的3,7或9,而且周期是2，并且$t_1$是偶数，不然满足要求的数必然不会超过一半。
所以如果存在$p_i$末尾数不是9或者1（也就是存在周期4），那么我们知道满足要求的约数必然不超过一半。
而如果所有$p_i$末尾数都是9或者1，那么所有因子的末位数也只能是1和9，也就是末尾要求是3和7的情况满足要求的约数必然不超过一半。
而对于末位要求是9的情况，同样如果某种分解方式中使用了尾数为3或7的素因子，我们已经知道满足要求的约数不超过一半；如果某种分解方式所有素因子的尾数都是9或1
我们可以把所有尾数为9的素因子看成一类，尾数为1的素因子看成异类，显然只有在尾数为9的素因子总次数为奇数时结果才满足要求。
不妨设$p_1,p_2,...,p_s$是所有尾数为9的素因子($s<=t$),于是尾数为9的余数的比例是满足$0<=x_i<=t_i$的所有$(t_1+1)....(t_s+1)$种情况中,$x_1+x_2+...+x_s$是奇数的比例就是所求的比例。而其中只要任意一个$t_i$是奇数，那么这个比例就是$1/2$.而如果所有$t_i$都是偶数，容易归纳证明这个比例必然小于$1/2$,所以满足要求的数也必然不会超过一半。
而如果对于k是偶数而且$k>2$的情况，我们总可以选择一个素因子p有要求的末位数，然后其余的素因子末位数都是1，可以达到一半的约数这个条件。
而对于$k=2$,那么这个数只能是素数，取满足要求的素数正好一半达到要求。
但是对于k是奇数的情况，情况就更加复杂了，如果k是素数，那么唯一可能因子分解形式是$p^{k-1}$，其余情况更加复杂，但是我们可以知道严格小于一半。
对于要求目标为偶数2,4,6,8,必然含素因子2,类似前面，其周期是4，必然可以得出约数数目不超过一半满足条件

mathe

k是奇数，目标末位数为9,那么我们可以达到${k-1}/2$个。而k为奇数，目标为3,7时，猜测，在k含模4为3的素因子时，设其中最小的模4为3的素因子为u,结果为${u+1}/{4u}$,而如果k的所有素因子模4都是1,那么结果猜测就是${k-1}/{4k}$

mathe

在k为奇数，而且目标个位数是3或7时，我们假设其因子分解形式为$p_1^{t_1}...p_h^{t_h}$,我们先查看其中最多只有一个$p_i$的个位数不是1的情况，不妨设$p_1$个位数不是1，其余的个位数都是1.由于k为奇数，所以有$t_i>=2$而且它们都是偶数。
对于这种情况我们只要看$1,p_1,p_1^2,...,p_1^{t_1}$中有多少个末尾数是3或7，由于周期是4，显然这个数目不超过\(\lfloor\frac{t_1+1+2}4\rfloor\)，其中在$p_1$的个位数就是目标个位数时取到这个最佳值。
也就是在这种分解模式下，满足条件的约数的比例是\(\frac{1}{t_1+1}\lfloor\frac{t_1+1+2}{4}\rfloor\)
这个函数在$t_1+1 -=3 (mod 4)$时为\(\frac{t_1+1+1}{4(t_1+1)}=\frac{1}{4}+\frac{1}{4(t_1+1)}\)是$t_1+1$的减函数而且结果不小于$1/4$，但是不大于$1/3$,对应$t_1+1=3$的特殊情况;而在$t_1+1 -=1(mod 4)$时为\(\frac{t_1+1-1}{4(t_1+1)}=\frac{1}{4}-\frac{1}{4(t_1+1)}\)是$t_1+1$的增函数而且结果不大于$1/4$。所以所有的这种模式下的解，如果k存在模4为3的因子，我们挑选它作为$t_1+1$必然比挑选模4为1的因子好。而所有模4为3的因子，由于越小结果越好，所以必然挑选最小的模4为3的素因子。而如果k所有因子都模4为1，那么这时需要挑选最大的因子，也就是k本身作为$t_1+1$,于是这时满足条件的余数的比例小于$1/4$但是不小于$1/5$,对于$k=5$时的情况。
现在我们查看因子分解中至少有两个$p_i$的约数个位数不是1，同样如果其中有$t_1$模4为3，那么我们可以容易得到，总体比例还是必然不大于\(\frac{t_1+1+1}{4(t_1+1)}=\frac{1}{4}+\frac{1}{4(t_1+1)}\) （对$t_2$的不同取值分类，其中每一类按$t_1$的取值模4再分类，那么不同类的个位数不同，但是每一类数目比例都不超过上面这个比例）
而如果每个$t_i$都是模4为1，我们直到每个$p_i^{x_i}$中都是个位数是1的情况比其它个位数多一种，归纳法可以得到乘积结果也是3,7,9数目相同，而1的数目最多，然后计算可以得知，$p_1^{t_1}p_2^{t_2}$组合的情况得到的3，7，9的数目会和直接使用$p_1^{(t_1+1)(t_2+1)-1}$的情况的数目是一模一样的。同样归纳可以得知分拆成更多各素因子的情况也一样。
也就是说k的所有因子都是模4为1的情况，最优结果还是\(\frac{k-1}{4k}=\frac{1}{4}-\frac{1}{4k}\),只是达到最优结果的方案有很多种不同的选择。

gxqcn

mathe 仔细分析了各种情况，回答了楼主的问题。

我的想法则是：通过特殊而不失一般性的构造手法，直接获取目标答案。


为方便叙述，在保留以上帖子中的数学符号的基础上，新引进一些符号。

已知：某数 \(m\)（\(m\geqslant 2, m\in \NN\)），刚好有 \(k\) 个约数，
请问：最多有多少个约数的个位数字是 \(n\in\{0,1,\dots,9\}\)？求出此时的 \(m\) 之一及对应的约数个数 \(\max(n)\)

1）当 \(n\in\{1,2,3,5,7,9\}\) 时，

令 \(k=p*r\)，其中 \(p\) 为 \(k\) 的最小素因子（当 \(k\) 为素数时，\(r=1\)），显然 \(p\gt 1\)，

当 \(n=1\) 时，　　令 \(m =11^{k-1}, \;\quad\qquad \max(1)=k\)；
当 \(n=5\) 时，　　令 \(m =5^{k-1}, \!\qquad\qquad \max(5)=k-1\)；
当 \(n=2,3,7\) 时，令 \(m=n^{p-1}11^{r-1}, \quad \max(n)=\left\lceil\dfrac{p-1}{4}\right\rceil*r\)；
当 \(n=9\) 时，　　令 \(m=19^{p-1}11^{r-1}, \quad \max(9)=\left\lceil\dfrac{p-1}{2}\right\rceil*r\)；

2) 当 \(n\in\{0,4,6,8\}\) 时，情况略复杂一些。


新问题： 上述已讨论的方案中，
1、若限定 \(m\) 的素因子必须在 \(\{2,3,5,7,11,19\}\) 集合内，是否已使 \(m\) 最小化？
2、若取消上述限定，当 \(m\) 最小化时，其末尾非 \(1\) 的素因子是否必定在一个有限集合中？比如：\(\{2,\;\;3,13,23,\;\;5,\;\;7,17,37,\;\;19\}\)

备　注：昨天回帖时临近下班，略显仓促，有些思想未表达清楚；现重新"抛砖引玉"。

mathe

gxqcn 发表于 2018-6-1 16:17
mathe 仔细分析了各种情况，回答了楼主的问题。

我的想法则是：通过特殊而不失一般性的构造手法，直接获 ...

n是3,7时需要修改一下。如果k是奇数而且含有素因子p除以4的余数为3，那么应该选择这个p（而且要求其最小)
模式为$n^{p-1}11^{r-1}$，但是如果k全部素因子除以4的余数为1，那么应该直接选$n^{k-1}$
比如n=3,k=25,那么选择$3^4*11^4$满足条件的只有5个，而$3^24$有6个。