找回密码
 欢迎注册
查看: 37644|回复: 31

[讨论] 从“有多少个约数的个位是1”想到的~

[复制链接]
发表于 2018-5-31 14:34:54 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
之前遇到的一道小学题目
一个数字刚好有12个约数,那么它最多有多少个约数的个位数字是3


这个题目并不复杂,答案是6。
精华


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

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

2、一般化,如果刚好有$k$个约数,那么最多有多少个约数的个位数字是$n\in \{0,1,...,9\}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-31 14:50:08 | 显示全部楼层
\(\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}\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-31 14:56:26 | 显示全部楼层
可以写成$p_1p_2^5$,其中$p_1=3(mod 10),p_2=1(mod 10)$

点评

嗯,我的分析有所遗漏  发表于 2018-5-31 15:01
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-31 17:17:39 | 显示全部楼层
感觉楼上的方法非常好,具有一般性,达到最优化。

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\}\),情况略复杂一些。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-5-31 20:23:58 | 显示全部楼层
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$?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-5-31 21:04:09 | 显示全部楼层
这道题目一般情况答案还是比较复杂的,需要分类
个位数是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,必然可以得出约数数目不超过一半满足条件

点评

建议每种情况隔开一些,方便分类阅读~  发表于 2018-6-1 15:17
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-1 07:16:17 来自手机 | 显示全部楼层
k是奇数,目标末位数为9,那么我们可以达到${k-1}/2$个。而k为奇数,目标为3,7时,猜测,在k含模4为3的素因子时,设其中最小的模4为3的素因子为u,结果为${u+1}/{4u}$,而如果k的所有素因子模4都是1,那么结果猜测就是${k-1}/{4k}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-1 09:01:52 | 显示全部楼层
在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}\),只是达到最优结果的方案有很多种不同的选择。

评分

参与人数 1威望 +12 金币 +12 贡献 +12 经验 +12 鲜花 +12 收起 理由
282842712474 + 12 + 12 + 12 + 12 + 12 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-1 16:17:26 | 显示全部楼层
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 指出了几处修正点,关键在于充分挖掘“上取整”函数的特点。  发表于 2018-6-1 17:10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-1 16:56:15 | 显示全部楼层
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个。

点评

指点得很对!我刚也发现了,正准备编辑帖子,看到你的回复,就不再去编辑它了。  发表于 2018-6-1 17:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 14:30 , Processed in 0.054813 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表