数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 串珠素数问题
1234下一页
返回列表 发新帖
查看: 20977|回复: 33

[擂台] 串珠素数问题

[复制链接]
无心人
发表于 2008-11-20 11:32:41 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
我们把形如
ababab........ababa形式的素数叫串珠素数
其中1 <= a <= 9, 0 <= b <= 9
现在问题是
10^100内有多少串珠素数？？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

gxqcn
发表于 2008-11-20 14:50:27 | 显示全部楼层

共 76 个

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
发表于 2008-11-20 14:51:22 | 显示全部楼层

源代码

  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
发表于 2008-11-20 14:55:25 | 显示全部楼层
用结果中的部分数据搜索，有结果如下：
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个数据，与我的结果一致。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-11-20 17:29:02 | 显示全部楼层
呵呵
本来想用haskell算下呢
结果瞎忙也没去解
GxQ够快的啊

呵呵
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-11-20 17:30:42 | 显示全部楼层
另外
a != b
a = [1,3,7,9]

如果a = b 则转化为$I_n$素数
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-11-20 20:49:17 | 显示全部楼层
HugeCalc 对付此类问题相对别的大数库更拿手，
因为它对十进制数也提供了丰富的接口。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-11-20 21:43:11 | 显示全部楼层
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)]
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2008-11-21 11:49:23 | 显示全部楼层
下面考虑三个珠子的，即
abcabcabc...模式的
可知，有两种形式
1、结尾数字是a
2、结尾数字是b
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-11-21 12:27:38 | 显示全部楼层
那，这次你先来。。。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-4-27 06:25 , Processed in 0.068479 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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