串珠素数问题

无心人

我们把形如 ababab........ababa形式的素数叫串珠素数 其中1 <= a <= 9, 0 <= b <= 9 现在问题是 10^100内有多少串珠素数？？

gxqcn

Call HugeCalc V8.0.0.0 0.000008 s No.1 (n,a,b)=(1,1,0) 101 0.001869 s No.2 (n,a,b)=(1,1,3) 131 0.001953 s No.3 (n,a,b)=(1,1,5) 151 0.001984 s No.4 (n,a,b)=(1,1,8) 181 0.002011 s No.5 (n,a,b)=(1,1,9) 191 0.002046 s No.6 (n,a,b)=(1,3,1) 313 0.002073 s No.7 (n,a,b)=(1,3,5) 353 0.002098 s No.8 (n,a,b)=(1,3,7) 373 0.002124 s No.9 (n,a,b)=(1,3,8) 383 0.002154 s No.10 (n,a,b)=(1,7,2) 727 0.002180 s No.11 (n,a,b)=(1,7,5) 757 0.002206 s No.12 (n,a,b)=(1,7,8) 787 0.002231 s No.13 (n,a,b)=(1,7,9) 797 0.002258 s No.14 (n,a,b)=(1,9,1) 919 0.002283 s No.15 (n,a,b)=(1,9,2) 929 0.002318 s No.16 (n,a,b)=(2,1,8) 18181 0.002354 s No.17 (n,a,b)=(2,3,2) 32323 0.002381 s No.18 (n,a,b)=(2,3,5) 35353 0.002412 s No.19 (n,a,b)=(2,7,2) 72727 0.002845 s No.20 (n,a,b)=(2,7,4) 74747 0.002882 s No.21 (n,a,b)=(2,7,8) 78787 0.002913 s No.22 (n,a,b)=(2,9,4) 94949 0.002941 s No.23 (n,a,b)=(2,9,5) 95959 0.003219 s No.24 (n,a,b)=(3,1,2) 1212121 0.003302 s No.25 (n,a,b)=(3,1,6) 1616161 0.003428 s No.26 (n,a,b)=(4,3,2) 323232323 0.003498 s No.27 (n,a,b)=(4,3,8) 383838383 0.003570 s No.28 (n,a,b)=(4,7,2) 727272727 0.003644 s No.29 (n,a,b)=(4,9,1) 919191919 0.003710 s No.30 (n,a,b)=(4,9,2) 929292929 0.003778 s No.31 (n,a,b)=(4,9,7) 979797979 0.003846 s No.32 (n,a,b)=(4,9,8) 989898989 0.004163 s No.33 (n,a,b)=(5,1,2) 12121212121 0.004398 s No.34 (n,a,b)=(5,1,4) 14141414141 0.004957 s No.35 (n,a,b)=(5,3,2) 32323232323 0.005488 s No.36 (n,a,b)=(5,9,1) 91919191919 0.006650 s No.37 (n,a,b)=(7,1,5) 151515151515151 0.007172 s No.38 (n,a,b)=(7,3,8) 383838383838383 0.007569 s No.39 (n,a,b)=(7,7,3) 737373737373737 0.008365 s No.40 (n,a,b)=(8,3,8) 38383838383838383 0.008698 s No.41 (n,a,b)=(8,7,2) 72727272727272727 0.008937 s No.42 (n,a,b)=(8,7,4) 74747474747474747 0.009184 s No.43 (n,a,b)=(8,7,5) 75757575757575757 0.009485 s No.44 (n,a,b)=(8,9,1) 91919191919191919 0.009721 s No.45 (n,a,b)=(8,9,4) 94949494949494949 0.009994 s No.46 (n,a,b)=(8,9,5) 95959595959595959 0.010345 s No.47 (n,a,b)=(9,1,1) 1111111111111111111 0.011252 s No.48 (n,a,b)=(10,3,7) 373737373737373737373 0.011513 s No.49 (n,a,b)=(10,3,8) 383838383838383838383 0.011787 s No.50 (n,a,b)=(10,7,8) 787878787878787878787 0.012206 s No.51 (n,a,b)=(11,1,1) 11111111111111111111111 0.012737 s No.52 (n,a,b)=(11,3,5) 35353535353535353535353 0.013919 s No.53 (n,a,b)=(11,9,1) 91919191919191919191919 0.014415 s No.54 (n,a,b)=(12,1,3) 1313131313131313131313131 0.015475 s No.55 (n,a,b)=(13,3,7) 373737373737373737373737373 0.015926 s No.56 (n,a,b)=(13,7,8) 787878787878787878787878787 0.016480 s No.57 (n,a,b)=(13,9,7) 979797979797979797979797979 0.018184 s No.58 (n,a,b)=(15,1,7) 1717171717171717171717171717171 0.019006 s No.59 (n,a,b)=(16,1,9) 191919191919191919191919191919191 0.022527 s No.60 (n,a,b)=(18,1,7) 1717171717171717171717171717171717171 0.023872 s No.61 (n,a,b)=(19,7,3) 737373737373737373737373737373737373737 0.026389 s No.62 (n,a,b)=(21,1,2) 1212121212121212121212121212121212121212121 0.029477 s No.63 (n,a,b)=(22,9,7) 979797979797979797979797979797979797979797979 0.033815 s No.64 (n,a,b)=(25,3,1) 313131313131313131313131313131313131313131313131313 0.038910 s No.65 (n,a,b)=(27,1,6) 1616161616161616161616161616161616161616161616161616161 0.041608 s No.66 (n,a,b)=(28,3,8) 383838383838383838383838383838383838383838383838383838383 0.049650 s No.67 (n,a,b)=(31,1,5) 151515151515151515151515151515151515151515151515151515151515151 0.057147 s No.68 (n,a,b)=(32,9,4) 94949494949494949494949494949494949494949494949494949494949494949 0.067217 s No.69 (n,a,b)=(35,7,2) 72727272727272727272727272727272727272727272727272727272727272727272727 0.077794 s No.70 (n,a,b)=(38,1,8) 18181818181818181818181818181818181818181818181818181818181818181818181818181 0.080939 s No.71 (n,a,b)=(38,7,5) 75757575757575757575757575757575757575757575757575757575757575757575757575757 0.088900 s No.72 (n,a,b)=(40,3,7) 373737373737373737373737373737373737373737373737373737373737373737373737373737373 0.095140 s No.73 (n,a,b)=(41,3,1) 31313131313131313131313131313131313131313131313131313131313131313131313131313131313 0.113239 s No.74 (n,a,b)=(44,1,5) 15151515151515151515151515151515151515151515151515151515151515151515151515151515151515151 0.132402 s No.75 (n,a,b)=(47,7,8) 78787878787878787878787878787878787878787878787878787878787878787878787878787878787878787878787 0.143494 s No.76 (n,a,b)=(49,7,2) 727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727 请按任意键继续. . .

gxqcn

1. //////////////////////////////////////////////////////////////////////////
2. //
3. // 目的：搜索串珠素数（形如ababab...ababa的素数）
4. // 设计：郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
5. // 日期：2008-11-20
6. //
7. // Web: http://www.emath.ac.cn/
8. // BBS: http://bbs.emath.ac.cn/
9. //
10. //////////////////////////////////////////////////////////////////////////
12. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
13. // Win32 Debug: Debug Multithreaded DLL
14. // Win32 Release: Multithreaded DLL
16. #include <stdio.h>
18. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"
19. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
21. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
22. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
24. #define MAX_DIGITS 100
26. int main(int argc, char* argv[])
27. {
28. printf( "Call %s\n\n", HugeCalc::GetVer());
30. if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
31. {
32. printf( "\n警告：您未通过 HugeCalc.dll 的许可认证！" \
33. "\n解决方案可选下列方案之一：" \
34. "\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
35. "\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" );
36. }
37. else
38. {
40. UINT32 n, a, b, s, count=0;
41. CHugeInt stepA( 101 ), stepB, p;
43. HugeCalc::EnableTimer();
44. HugeCalc::ResetTimer();
46. for ( n=1; n<MAX_DIGITS/2; ++n )
47. {
48. ( stepB = stepA ).DecRShift( 1 );
50. for ( a=1, p=stepA; a<10; a+=2, ++p+=stepA )
51. {
52. for ( b=0, s=(n+1)*a; b<10; ++b, s+=n )
53. {
54. if ( 0!=(s%3) && p.IsPrime() )
55. {
56. printf( "%s\tNo.%u\t(digits,a,b)=(%u,%u,%u)\n", HugeCalc::GetTimerStr(), ++count, 2*n+1, a, b );
57. }
58. p += stepB;
59. }
60. }
62. ++stepA.DecLShift( 2 );
63. }
64. }
66. system( "pause" );
67. return 0;
68. }

复制代码

gxqcn

用结果中的部分数据搜索，有结果如下：

A059758 Undulating palindromic primes: numbers that are prime, palindromic in base 10, the digits alternate: ababab... with a != b 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 18181, 32323, 35353, 72727, 74747, 78787, 94949, 95959, 1212121, 1616161, 323232323, 383838383, 727272727, 919191919, 929292929, 979797979, 989898989

里面提供了前32个数据，与我的结果一致。

无心人

呵呵 本来想用haskell算下呢 结果瞎忙也没去解 GxQ够快的啊 呵呵

无心人

另外 a != b a = [1,3,7,9] 如果a = b 则转化为$I_n$素数

gxqcn

HugeCalc 对付此类问题相对别的大数库更拿手， 因为它对十进制数也提供了丰富的接口。

无心人

import Primes(isPrime) readInt :: IO Int readInt = readLn parta a n = fromIntegral \$ sum (take ((div n 2)+1) (iterate (100*) a)) partb b n = fromIntegral \$ sum (take (div n 2) (iterate (100*) (10*b))) isczPrime n = [(n, a, b) | n <- [3, 5..n], a <- [1,3,7,9], b <- [0..9], a /= b, let c = (parta a n) + (partb b n), isPrime c ] main = do putStrLn "Input Digits: " n <- readInt print (isczPrime n) 结果是： Input Digits: 100 [(3,1,0),(3,1,3),(3,1,5),(3,1,8),(3,1,9),(3,3,1),(3,3,5),(3,3,7),(3,3,8),(3,7,2),(3,7,5),(3,7,8),(3,7,9),(3,9,1),(3,9,2),(5,1,8),(5,3,2),(5,3,5),(5,7,2),(5,7,4),(5,7,8),(5,9,4),(5,9,5),(7,1,2),(7,1,6),(9,3,2),(9,3,8),(9,7,2),(9,9,1),(9,9,2),(9,9,7),(9,9,8),(11,1,2),(11,1,4),(11,3,2),(11,9,1),(15,1,5),(15,3,8),(15,7,3),(17,3,8),(17,7,2),(17,7,4),(17,7,5),(17,9,1),(17,9,4),(17,9,5),(21,3,7),(21,3,8),(21,7,8),(23,3,5),(23,9,1),(25,1,3),(27,3,7),(27,7,8),(27,9,7),(31,1,7),(33,1,9),(37,1,7),(39,7,3),(43,1,2),(45,9,7),(51,3,1),(55,1,6),(57,3,8),(63,1,5),(65,9,4),(71,7,2),(77,1,8),(77,7,5),(81,3,7),(83,3,1),(89,1,5),(95,7,8),(99,7,2)]

无心人

下面考虑三个珠子的，即 abcabcabc...模式的 可知，有两种形式 1、结尾数字是a 2、结尾数字是b

gxqcn

那，这次你先来。。。