报数游戏（增加难度版）

KeyTo9_Fans

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

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

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

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

mathe

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

xiaoshuchong

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

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

mathe

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

mathe

如果我们查看一个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位左右时，就会有素数的数目多余合数的数目。
而位数越大，两者比例差别为越大，到后面，合数完全可以忽略。