找回密码
 欢迎注册
楼主: iseemu2009

[讨论] 五道难题求解

[复制链接]
发表于 2025-2-22 19:12:44 | 显示全部楼层
wayne 发表于 2025-2-22 08:37
16核全开,直接上暴力美学.
第一题: $1929374254627488900 = 1389019170^2$

第一题可以挺快的,首先平方是10的倍数,这个数必然是10的倍数,末尾可以不搜索。
其次它除以10以后,平方末三位是8x9,得到这个数末三位只有24种选择。
然后它的范围在\(10^8\)到\(\sqrt{2}10^8\)之间,我们需要穷举前5位加上最后3位24种选择共41422*24种情况。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-2-22 19:54:28 | 显示全部楼层
末位数能被8整除, 所以有三种情况,$809, 849,889$. 然后就是 7位数的穷举. 我是这种思路.
如果计算模1000的情况,确实是24种情况,这样又少了3个数, 于是只需要 穷举 4位数. 重新 实现了一下mathe的思路, 很快.
  1. tmp = Select[Range[10^3 - 1], IntegerDigits[#^2, 10, 3][[-1]] == 9 &&  IntegerDigits[#^2, 10, 3][[-3]] == 8 &];
  2. sol = Flatten[
  3.    Table[FromDigits[
  4.      Flatten[{1, IntegerDigits[i, 10, 5],
  5.        IntegerDigits[j, 10, 3]}]], {i, 1010, 38902}, {j, tmp}], 1];
  6. Select[sol, AllTrue[Differences[IntegerDigits[#^2][[1 ;; -1 ;; 2]]], # == 1 &] &]
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-2-22 23:33:43 | 显示全部楼层
基于mathe的思路,改成计算平方的末尾是五位数的情况,即模10^5, 有240个解.这样,前面的只需要计算10-389的情况. 总共只需要枚举$389*240$种情况, 于是1秒钟出结果.,
  1. tmp=Select[Range[10^5-1],IntegerDigits[#^2,10,5][[{1, 3, 5}]]=={7,8,9}&];
  2. sol=Flatten[Table[FromDigits[Flatten[{1,IntegerDigits[i,10,3],IntegerDigits[j,10,5]}]],{i,10,389},{j,tmp}],1];
  3. ans=Select[sol,AllTrue[Differences[IntegerDigits[#^2][[1;;-1;;2]]],#==1&]&]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-2-23 08:41:45 | 显示全部楼层
第4题的实现代码:
  1. ClearAll["Global`*"];
  2. x=Permutations[Range@9];y=Select[IntegerPartitions@9,Length@#>1&&Count[#,1]<5&];
  3. n=0;s={};
  4. Do[c=Product[m!,{m,Tally[b][[All,2]]}];k=0;
  5. Do[r=TakeList[a,b];
  6. k+=Times@@Boole[Union[PrimeQ/@FromDigits/@r]],{a,x}];
  7. k/=c;n+=k;AppendTo[s,{k,b}],{b,y}];{n,s}
复制代码



{44680,{{11483,{8,1}},{8844,{7,2}},{2052,{7,1,1}},{6572,{6,3}},{2482,{6,2,1}},{205,{6,1,1,1}},{6424,{5,4}},{2049,{5,3,1}},{535,{5,2,2}},{646,{5,2,1,1}},{13,{5,1,1,1,1}},{942,{4,4,1}},{945,{4,3,2}},{449,{4,3,1,1}},{410,{4,2,2,1}},{54,{4,2,1,1,1}},{136,{3,3,3}},{292,{3,3,2,1}},{20,{3,3,1,1,1}},{32,{3,2,2,2}},{82,{3,2,2,1,1}},{2,{3,2,1,1,1,1}},{8,{2,2,2,2,1}},{3,{2,2,2,1,1,1}}}}

主要问题是重复计数的太多,该如何优化提速?

点评

{2,2,2,2,1} 重复计数24次  发表于 2025-2-23 08:48
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-2-23 08:46:55 | 显示全部楼层
仿3楼代码多核同时计算:

  1. SetSharedVariable[n,lst];n=0;lst={};
  2. x=Permutations[Range@9];y=Select[IntegerPartitions@9,Length@#>1&&Count[#,1]<5&];
  3. ParallelDo[c=Product[m!,{m,Tally[b][[All,2]]}];k=0;
  4. Do[r=TakeList[a,b];
  5. k+=Times@@Boole[Union[PrimeQ/@FromDigits/@r]],{a,x}];
  6. k/=c;n+=k;AppendTo[s,{k,b}],{b,y}];{n,s}
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-2-23 12:02:23 | 显示全部楼层
素数都是形如$6n\pm1$,所以我们按照6为模分成6组.

点评

放弃了. 不过, 我写了一个递归版本的代码,不需要去重.  发表于 2025-2-24 08:49
愿闻其详  发表于 2025-2-23 21:06
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-2-24 00:23:36 | 显示全部楼层
northwolves 发表于 2025-2-22 16:30
第4题:44680

组合                     数量

可读性可能不那么好,代码需要 1.1秒钟. 局部地方有重复逻辑,是可以进一步优化速度的,比较懒,暂时先这样吧.
  1. pool = Table[{i,Select[FromDigits /@ Permutations[Range[9], {i}], PrimeQ]}, {i, 1,8}];
  2. ans = GroupBy[
  3.    Flatten[Table[
  4.      Union[Sort /@
  5.        Lookup[NestWhile[
  6.           GroupBy[Join[Lookup[#, True, {}],
  7.              Flatten[Table[
  8.                Flatten[Table[{Flatten[{p[[1]], t}],
  9.                   Complement[p[[2]],
  10.                    Flatten[IntegerDigits /@ {p[[1]], t}]]}, {len,
  11.                   Flatten[{Range[IntegerLength[p[[1, -1]]],
  12.                     Length[p[[2]]]/2], Length[p[[2]]]}]}, {t,
  13.                   Select[FromDigits /@
  14.                     Permutations[
  15.                     Complement[p[[2]],
  16.                     Flatten[IntegerDigits /@ {p[[1]], t}]], {len}],
  17.                    PrimeQ]}], 1], {p, Lookup[#, False, {}]}],
  18.               1]], #[[2]] == {} &] &,
  19.           GroupBy[Table[{{i}, Complement[Range[9], IntegerDigits[i]]}, {i, pool[[m, 2]]}], #[[2]] == {} &],
  20.           Lookup[#, False, {}] != {} &], True, {}][[All, 1]]], {m, 1,  4}], 1], Map[IntegerLength, #] &];
  21. Length /@ ans
复制代码


  1. {{{1,8},11483},{{1,1,7},2052},{{1,2,6},2482},{{1,3,5},2049},{{1,4,4},942},{{1,1,1,6},205},{{1,1,2,5},646},{{1,1,3,4},449},{{1,2,2,4},410},{{1,2,3,3},292},{{1,1,1,1,5},13},{{1,1,1,2,4},54},{{1,1,1,3,3},20},{{1,1,2,2,3},82},{{1,2,2,2,2},8},{{1,1,1,1,2,3},2},{{1,1,1,2,2,2},3},{{2,7},8844},{{2,2,5},535},{{2,3,4},945},{{2,2,2,3},32},{{3,6},6572},{{3,3,3},136},{{4,5},6424}}
复制代码

评分

参与人数 1威望 +8 金币 +8 贡献 +8 经验 +8 鲜花 +8 收起 理由
northwolves + 8 + 8 + 8 + 8 + 8 Awesome! YYUR!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2025-6-6 14:26 , Processed in 0.054053 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

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