免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 分解质因式707829217

在某微信群中看到的。如附件。

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

用软件试了下,竟然是真的。。。故发上来了。。。
707829217.jpg
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

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

TOP

回复 2# kuing

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

TOP

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

\[707829217=86627\times8171\]
$866278171$(八亿六千六百二十七万八千一百七十一)
  1. Count[StringCases[ToString[Range[1, 10000000, 2]], DigitCharacter],
  2.   "3"] // AbsoluteTiming
复制代码
...算到一千万($10000000$)都已经很费劲了...
{14.5102s, 4000000}

TOP

分解因数没啥好讲的了,但是计算有多少个 `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`,这就是最终答案。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

随便找一个有 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
复制代码
得出 163081。

然后再暴力统计验证:
  1. n3 = 0;
  2. Do[n3 = n3 + Count[IntegerDigits[i], 3], {i, 1, 309309}];
  3. n3
复制代码
同样输出 163081,看来应该没问题。

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

TOP

试着将 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]]
复制代码
这里就是计算不超过 271828 的正整数出现 8 的个数,结果是 128492。

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

再来验证 4# 的一千万(且有奇数条件),需先计算一百万的,赋值 n = 1000000 运行输出 600000,然后与 5# 最后一步一样,5*600000+1000000 = 4000000
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 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]]
复制代码
这样 m 就能任取 0~9 了。
运行得到不超过 271828 的正整数一共出现 128462 个 0。

TOP

回复 8# kuing


除了了佩服,没别的了。

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

TOP

本帖最后由 realnumber 于 2019-4-14 12:36 编辑

觉得可以直接把每个位置上的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$个.

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

TOP

回复 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,需要另计,当然这也不是难事。

TOP

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

TOP

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

TOP

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

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

TOP

返回列表 回复 发帖