数学研发论坛

 找回密码
 欢迎注册
查看: 232|回复: 6

[讨论] 报数游戏(增加难度版)

[复制链接]
发表于 2022-7-10 13:51:59 | 显示全部楼层 |阅读模式

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

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

x
报数游戏是一个广为流传的休闲小游戏。

参加游戏的每个人要按一定顺序轮流报数,

但如果下一个报的数是7的倍数,或十进制表示中含有数字7,

就必须跳过这个数,否则就输掉了游戏。

在一个风和日丽的下午,mathe和fans闲得无聊玩起了这个报数游戏。

但在只有两个人玩的情况下计算起来还是比较容易的,因此他们玩了很久也没分出胜负。

此时mathe灵光一闪,决定把这个游戏加强:

任何一个十进制中含有数字7的数,它的所有倍数都不能报出来!

形式化地,设p(x)表示x的十进制表示中是否含有数字7,若含有则p(x)=1,否则p(x)=0。

则一个正整数x不能被报出,当且仅当存在正整数y和z,使得x=yz且p(y)=1。

例如,如果mathe报出了6,由于7不能报,所以fans下一个需要报8;

如果fans报出了33,则由于34=17*2,35=7*5都不能报,mathe下一个需要报出36;

如果mathe报出了69,由于70~79的数都含有7,fans下一个需要报出80才行。

他们很快就发现这个游戏可比原版的游戏难玩多了。

他们想知道无限玩下去之后,报出的数的密度函数是怎样的?

这个密度比素数分布的密度更稀疏还是更密集?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-7-10 18:14:58 | 显示全部楼层
也许比素数分布更稀疏?
用筛法得出1亿以内的这种数有5491316个(包含0),
而素数有5761455个。
当然,这点证据过于粗浅。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-7-10 21:10:46 | 显示全部楼层
密度远远低于素数的密度,一个数x是素数的概率密度大概是$\frac1{\ln(x)}$, 而对于充分大的x,满足题目中要求的数会大部分是素数,而且还不包含数字7,所以密度大概为$\frac{(\frac9{10})^{\lg(x)}}{\ln(x)}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-7-11 10:30:37 | 显示全部楼层
mathe 发表于 2022-7-10 21:10
密度远远低于素数的密度,一个数x是素数的概率密度大概是$\frac1{\ln(x)}$, 而对于充分大的x,满足题目中要 ...

总感觉不对,密度没有这么小。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-7-11 10:55:57 来自手机 | 显示全部楼层
数字小的时候,合数比例比较高,但是数字超级大时,合数比例会越来越低了

点评

能否找到一個分界,之後合數的比例就會下降,且再也不會上升。  发表于 2022-7-11 14:24
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-7-11 22:12:02 | 显示全部楼层
如果我们查看一个n位数x,那么它的所有位数都不是7的概率为\(\left(\frac9{10}\right)^n\), 所以它所有位数都不是7而且是素数的概率为\(\frac{\left(\frac9{10}\right)^n}{\ln(x)}\).
而如果一个n位数x是合数,那么它必然有一个真因子不小于\(\sqrt{x}\),所以至少\(\frac n2\)位,所以它的所有位数都不是7而且这个真因子的所有位数也不为7的概率为\(\left(\frac9{10}\right)^{\frac{3n}2}=\frac{\left(\frac9{10}\right)^n}{\left(\frac{10}9\right)^{\frac n2}}\),也就是它符合题目条件的概率小于这个数。
所以当\(\left(\frac{10}9\right)^{\frac n2}\gt \ln(x) \approx n \ln(10)\)时,必然有满足条件的合数少于数目。
这个条件约等于n=104, 也就是我们可以估计出数字位数达到104左右,已经可以确保满足条件的n位素数数目多于合数数目。
而实际上再次考虑分解成两个因子乘积时,这两个因子的长度之和约等于n,所以我们可以通过\(\left(\frac{10}9\right)^n\gt \ln(x) \approx n \ln(10)\)来判断超越的位数,所以大概44位左右时,就会有素数的数目多余合数的数目。
而位数越大,两者比例差别为越大,到后面,合数完全可以忽略。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-8-18 13:18 , Processed in 0.076190 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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