分解质因式707829217

isee

土生土长的北京妞儿，在胡同里长大，房不多，就一个四合院和近郊的别墅。不算美如天仙但还算标致，在清华读的经管，现在在做基金经理(不想被人肉，就不暴露单位啦) ,个人擅长基本面分析，价值投资。现在只想找个聪明靠谱的IT男。硬性要求是年龄，不要超过88年，还有不要特别矮或胖。我对智商的要求比较高，下面就出个题测试下。

我的微信ID是大写字母NY后面跟着两个质数，大的在前，小的在后，乘积是707829217，可直接搜索添加，另外还有个附加题目，在刚刚微信ID的数字中，从1开始到这个数字的奇数序列里，一共出现了多少个3，如果私信我正确的答案，我将直接邀你见面!期待缘分降临~

主要意思是，先分解质因式：707829217，并将这两个质数组成一个新数（大的在前，小的在后），从1开始到这个数的奇序列中，一共出现了多少个数字3？

用软件试了下，竟然是真的。。。故发上来了。。。

kuing

“竟然是真的”是指你真的加上了而且她真的邀你见面？？

isee

回复 2# kuing

题是真的……
当然，也有这么个人，你说的是没有了的

青青子衿

1. PrimeFactor = FactorInteger[707829217][[All, 1]]
2. SortP = Sort[PrimeFactor, Greater]
3. VXIDNum = FromDigits@Flatten@(IntegerDigits /@ SortP)

Copy the Code

\[707829217=86627\times8171\]
$866278171$（八亿六千六百二十七万八千一百七十一）

1. Count[StringCases[ToString[Range[1, 10000000, 2]], DigitCharacter],
2.   "3"] // AbsoluteTiming

Copy the Code

...算到一千万（$10000000$）都已经很费劲了...
{14.5102s, 4000000}

kuing

分解因数没啥好讲的了，但是计算有多少个 `3` 还挺有意思，也有点难度的。

设 `\{a_1,a_2,\ldots\}`（`a_1\ne0`）为给定的数码序列，设不超过 `\overline{a_1a_2\cdots a_k}` 的所有正整数一共出现 `f(k)` 个 `3`，设 `\overline{a_1a_2\cdots a_k}` 自身含 `g(k)` 个 `3`。

现在考虑当 `k` 变成 `k+1` 时个数变为多少。

先暂且将个位的 `3` 不当作是 `3`，那么：

（1）当个位取 `0` 到 `a_{k+1}` 时，前面的与 `k` 位时相同，共 `(a_{k+1}+1)f(k)` 个；

（2）当个位取 `a_{k+1}+1` 到 `9` 时，与（1）的区别仅在于前面不能取 `\overline{a_1a_2\cdots a_k}`，因而需要减去 `g(k)`，即共 `(9-a_{k+1})\bigl(f(k)-g(k)\bigr)` 个。

最后补回个位的 `3`，当 `a_{k+1}\geqslant3` 时，由于前面任何不超过 `\overline{a_1a_2\cdots a_k}` 的都要补一个（注意包括零），所以就是补 `\overline{a_1a_2\cdots a_k}+1` 个，即
\[f(k+1)=10f(k)-(9-a_{k+1})g(k)+\overline{a_1a_2\cdots a_k}+1,\]而当 `a_{k+1}<3` 时少补一个，不要后面的 `\!{}+1` 就是。

由此我们就可以进行逐步计算了，下面来解决原题，注意原题有奇数条件，最后一位需另行处理，先看前八位，即计算 `86627817` 的是多少。
%（其实这个例子不好，因为此数一个 `3` 都没有，`g(k)` 总是零，无法检验关于 `g(k)` 那部分有没有错）

`f(1)` 即不超过 `8`，显然就 `1` 个，即 `f(1)=1`；

`f(2)` 即不超过 `86`，个位不小于 `3`，所以 `f(2)=10f(1)+8+1=19`；

`f(3)` 即不超过 `866`，个位不小于 `3`，所以 `f(3)=10f(2)+86+1=277`；

`f(4)` 即不超过 `8662`，个位小于 `3`，不要 `\!{}+1`，所以 `f(4)=10f(3)+866=3636`；

如此类推：
\begin{align*}
f(5)&=10f(4)+8662+1=45023,\\
f(6)&=10f(5)+86627+1=536858,\\
f(7)&=10f(6)+866278=6234858,\\
f(8)&=10f(7)+8662781+1=71011362,
\end{align*}也就是说不过超过 `86627817` 的共 `71011362` 个。

最后，就是加最后一位了，虽然只能取 `1`, `3`, `5`, `7`, `9`，但方法还是那样，注意刚才已经说过这里 `g(k)` 恒为零，所以无需再像开头那样分类讨论，直接地，不计个位的 `3` 时为 `5f(8)`，补个位的 `3` 时不要 `\!{}+1`，所以就是 `5f(8)+86627817=441684627`，这就是最终答案。

kuing

随便找一个有 3 的数，利用 MMC(A) 来检验一下楼上的公式。

求不超过 309309 的所有正整数一共出现多少个 3。

按楼上的公式来计算，这次有 `g(k)` 的了，为：

1. f[1] = 1;
2. f[2] = 10*% - (9 - 0)*1 + 3;
3. f[3] = 10*% - (9 - 9)*1 + 30 + 1;
4. f[4] = 10*% - (9 - 3)*1 + 309 + 1;
5. f[5] = 10*% - (9 - 0)*2 + 3093;
6. f[6] = 10*% - (9 - 9)*2 + 30930 + 1

Copy the Code

得出 163081。

然后再暴力统计验证：

1. n3 = 0;
2. Do[n3 = n3 + Count[IntegerDigits[i], 3], {i, 1, 309309}];
3. n3

Copy the Code

同样输出 163081，看来应该没问题。

3 也可以改成其他数码，道理一样。

kuing

试着将 5# 的算法也写成 MMC(A) 程序：

1. m = 8;
2. n = 271828;
3. nlist = IntegerDigits[n];
4. g[k_] := Count[Take[nlist, k], m]
5. f[0] = 0;
6. Do[f[k + 1] = 10 f[k] - (9 - nlist[[k + 1]]) g[k] + FromDigits[Take[nlist, k]] + If[nlist[[k + 1]] < m, 0, 1], {k, 0, Length[nlist] - 1}];
7. f[Length[nlist]]

Copy the Code

这里就是计算不超过 271828 的正整数出现 8 的个数，结果是 128492。

然而试着代 m=0 结果不正确，看来 0 的个数会有些细节不同，时间关系明天再细想。

再来验证 4# 的一千万（且有奇数条件），需先计算一百万的，赋值 n = 1000000 运行输出 600000，然后与 5# 最后一步一样，5*600000+1000000 = 4000000

kuing

回复 7# kuing

搞清楚了，算多少个 0 的确有一点不同，就是补回个位时，由于要求正整数，当个位取 0，前面就不能取零，所以此时与 5# 的差别就是“（注意包括零）”得改成“（注意不包括零）”，而且也没有少补一个的情形，因此递推式就只有一条：
\[f(k+1)=10f(k)-(9-a_{k+1})g(k)+\overline{a_1a_2\cdots a_k},\]另外，此时 `f(1)=0` 是肯定的，可见 0 的个数是更简单的。

综上所述，将结论重新写一下：
设 `\{a_1,a_2,\ldots\}`（`a_1\ne0`）为给定的数码序列，设不超过 `\overline{a_1a_2\cdots a_k}` 的所有正整数一共出现数码 `m` 的个数为 `f(k,m)`，设 `\overline{a_1a_2\cdots a_k}` 自身含数码 `m` 的个数为 `g(k,m)`，则有
\[
f(k+1,m)=\led
&10f(k,m)-(9-a_{k+1})g(k,m)+\overline{a_1a_2\cdots a_k}+1, && a_{k+1}\geqslant m>0,\\
&10f(k,m)-(9-a_{k+1})g(k,m)+\overline{a_1a_2\cdots a_k}, && m=0\lor a_{k+1}<m.
\endled
\]
由此，就可以将楼上的程序改进一下，即：

1. m = 0;
2. n = 271828;
3. nlist = IntegerDigits[n];
4. g[k_] := Count[Take[nlist, k], m];
5. f[0] = 0;
6. Do[f[k + 1] = 10 f[k] - (9 - nlist[[k + 1]]) g[k] + FromDigits[Take[nlist, k]] +
7.     If[m == 0 || nlist[[k + 1]] < m, 0, 1], {k, 0, Length[nlist] - 1}];
8. f[Length[nlist]]

Copy the Code

这样 m 就能任取 0~9 了。
运行得到不超过 271828 的正整数一共出现 128462 个 0。

isee

回复 8# kuing


除了了佩服，没别的了。

我第一感觉是化三进制是错得太多了哦。

realnumber

觉得可以直接把每个位置上的3求出来，可能和上面重复了.
比如所有1~866278171数字,个位看作第一位，十位第2位，百位第3位，依次类推
第9位的3,是这样3abcdefgh，a~g可以是0~9任意一个，h只能1，3，5，7，9共$5\times10^7$个.
第8位的3，只能这样x3abcdefg,x取0~8中某个，abcdef取0~9任意一个，g只能1，3，5，7，9共$5\times9\times 10^6$个.
第7位的3，xy3abcdef,xy从0~86，abcde取0~9任意一个，f只能1，3，5，7，9共$5\times87\times10^5$个.
第6位置的3，xyz3abcde,xyz从0~865,abcd取0~9任意一个,e只能1，3，5，7，9共$5\times866\times10^4$个.
就到这里吧.
第1位（个位）的3，m3,m可以是0~86627816,有86627817个3.

每位都有约$4.4\times10^7$个按此大概估计的话，有$4.4\times10^8$个.

奇数忘了考虑了，修改好了.

kuing

回复 10# realnumber

这个计算方法也不错
具体数字我帮你算完好了：
10^7*5 + (8 + 1)*10^6*5 + (86 + 1)*10^5*5 + (866)*10^4*5 + (8662 + 1)*10^3*5 + (86627 + 1)*10^2*5 + (866278)*10*5 + (8662781 + 1)*5 + 86627817 = 441684627
规律也是那样子，要不要 + 1 得看数字与 3 的大小。

不过还是我上面说过的：原题这个数不好，因为此数一个 3 都没有，如果有，你的计算里也需要改变一下。
比如，改成 863278171 的话，当计算 xy3abcdef 时，xy 从 0~85 时后面任取，但 xy 取 86 时后面 abcdef 就不能大于 278171，需要另计，当然这也不是难事。

游客

弄2个大点的素数，算出两数乘积，然后让别人去分解？

realnumber

回复 12# 游客
是编程题目，更大都可以.不是笔算.慢点用循环1~√n去尝试，快点埃拉托色尼筛法或欧拉筛法建素数表，去尝试，更大用高精度字符去对付.
其实1楼问题，信息学竞赛也就小学组难度.

isee

回复 13# realnumber

是编程题目，更大都可以.不是笔算.慢点用循环1~√n去尝试，快点埃拉托色尼筛法或欧拉筛法建素 ...
realnumber 发表于 2019-4-14 20:19

编程，这可能是此图的源头