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

请按任意键继续. . .

gxqcn 发表于 2008-11-20 14:51:22

源代码

//////////////////////////////////////////////////////////////////////////
//
// 目的：搜索串珠素数（形如ababab...ababa的素数）
// 设计：郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
// 日期：2008-11-20
//
// Web: http://www.emath.ac.cn/
// BBS: http://bbs.emath.ac.cn/
//
//////////////////////////////////////////////////////////////////////////

// Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
//      Win32 Debug:    Debug Multithreaded DLL
//      Win32 Release:Multithreaded DLL

#include <stdio.h>

#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"
#include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"// 10进制系统

#pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )

#define MAX_DIGITS    100

int main(int argc, char* argv[])
{
    printf( "Call %s\n\n", HugeCalc::GetVer());

    if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
    {
      printf( "\n警告：您未通过 HugeCalc.dll 的许可认证！" \
            "\n解决方案可选下列方案之一：" \
            "\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
            "\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" );
    }
    else
    {

      UINT32 n, a, b, s, count=0;
      CHugeInt stepA( 101 ), stepB, p;

      HugeCalc::EnableTimer();
      HugeCalc::ResetTimer();

      for ( n=1; n<MAX_DIGITS/2; ++n )
      {
            ( stepB = stepA ).DecRShift( 1 );

            for ( a=1, p=stepA; a<10; a+=2, ++p+=stepA )
            {
                for ( b=0, s=(n+1)*a; b<10; ++b, s+=n )
                {
                  if ( 0!=(s%3) && p.IsPrime() )
                  {
                        printf( "%s\tNo.%u\t(digits,a,b)=(%u,%u,%u)\n", HugeCalc::GetTimerStr(), ++count, 2*n+1, a, b );
                  }
                  p += stepB;
                }
            }

            ++stepA.DecLShift( 2 );
      }
    }

    system( "pause" );
    return 0;
}

gxqcn 发表于 2008-11-20 14:55:25

用结果中的部分数据搜索，有结果如下：
A059758Undulating 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 =

如果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 <- ,
                  a <- ,
                  b <- ,
                  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

那，这次你先来。。。:lol
页: [1] 2 3 4
查看完整版本: 串珠素数问题