KeyTo9_Fans 发表于 2022-7-10 13:51:59

报数游戏(增加难度版)

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

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

但如果下一个报的数是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才行。

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

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

这个密度比素数分布的密度更稀疏还是更密集?

xiaoshuchong 发表于 2022-7-10 18:14:58

也许比素数分布更稀疏?
用筛法得出1亿以内的这种数有5491316个(包含0),
而素数有5761455个。
当然,这点证据过于粗浅。

mathe 发表于 2022-7-10 21:10:46

密度远远低于素数的密度,一个数x是素数的概率密度大概是$\frac1{\ln(x)}$, 而对于充分大的x,满足题目中要求的数会大部分是素数,而且还不包含数字7,所以密度大概为$\frac{(\frac9{10})^{\lg(x)}}{\ln(x)}$

xiaoshuchong 发表于 2022-7-11 10:30:37

mathe 发表于 2022-7-10 21:10
密度远远低于素数的密度,一个数x是素数的概率密度大概是$\frac1{\ln(x)}$, 而对于充分大的x,满足题目中要 ...

总感觉不对,密度没有这么小。

mathe 发表于 2022-7-11 10:55:57

数字小的时候,合数比例比较高,但是数字超级大时,合数比例会越来越低了

mathe 发表于 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位左右时,就会有素数的数目多余合数的数目。
而位数越大,两者比例差别为越大,到后面,合数完全可以忽略。
页: [1]
查看完整版本: 报数游戏(增加难度版)