素数の各桁の数値を数える

素数の各桁の数値を数える

素数の各桁が何種類の数字からなっているかを数えてみます。例えば11は1種類の数字からなっていて、13は2種類からなっているというようにカウントします。

以下のプログラムは素数一覧に対して素数の各桁の数値を数えるものです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countdigit( int n );

int main( int ac, char *av[] )
{
    int count, n;
    char buf[1024];

    while( fgets( buf, 1024, stdin ) ) {
        n = strtol( buf, NULL, 10 );
        count = countdigit( n );
        printf( "%d %d\n", n, count );
    }

    return( 0 );
}


int countdigit( int n )
{
    int     i, types[10], count;
    char    buf[1024];

    for( i = 0; i < 10; i++ )
        types[i] = 0;

    sprintf( buf, "%d", n );
    for( i = 0; i < strlen( buf ); i++ )
        types[buf[i] - '0']++;

    count = 0;
    for( i = 0; i < 10; i++ )
        if( types[i] != 0 )
            count++;

    return( count );
}

1億以下の素数の中で、1種類の数字だけからなるものは2,3,5,7,11だけでした。1桁の場合は必ず1種類なのは当たり前ですから、実質11のみという事になります。1以外の数字が1種類でなる素数は有り得ませんが、111111のような素数がもっとあるかと予想したのですが。

2種類以上は数が多すぎて全てを列挙できませんので、それぞれの素数の数だけを記します。

(2012/2/15追記)

素数一覧を10億まで求めたので、こちらも10億以下にデータを更新しました。

(2020/4/7追記)

10兆以下まで調べました。

素数の各桁の数字の数一覧

1万以下

各桁の数字の種類の数 素数の数
1 5個
2 109個
3 605個
4 510個
5 0個
6 0個
7 0個
8 0個
9 0個
10 0個

10万以下

各桁の数字の種類の数 素数の数
1 5個
2 230個
3 2,201個
4 4,627個
5 2,529個
6 0個
7 0個
8 0個
9 0個
10 0個

100万以下

各桁の数字の種類の数 素数の数
1 5個
2 337個
3 7,111個
4 26,882個
5 33,924個
6 10,239個
7 0個
8 0個
9 0個
10 0個

1000万以下

各桁の数字の種類の数 素数の数
1 5個
2 678個
3 19,981個
4 132,641個
5 279,552個
6 197,772個
7 33,950個
8 0個
9 0個
10 0個

1億以下

各桁の数字の種類の数 素数の数
1 5個
2 1,087個
3 53,901個
4 582,793個
5 1,896,171個
6 2,248,373個
7 888,615個
8 90,510個
9 0個
10 0個

10億以下

各桁の数字の種類の数 素数の数
1 5個
2 1,918個
3 153,410個
4 2,404,651個
5 11,337,828個
6 20,444,470個
7 13,280,421個
8 3,079,604個
9 145,227個
10 0個

100億以下

各桁の数字の種類の数 素数の数
1 5個
2 3,401個
3 418,988個
4 9,498,405個
5 63,853,547個
6 159,703,179個
7 157,697,475個
8 56,559,903個
9 7,317,608個
10 0個

1000億以下

各桁の数字の種類の数 素数の数
1 5個
2 6,783個
3 1,175,763個
4 36,868,690個
5 340,341,299個
6 1,154,455,341個
7 1,579,544,959個
8 836,200,941個
9 162,979,490個
10 6,481,542個

1兆以下

各桁の数字の種類の数 素数の数
1 5個
2 10,908個
3 3,180,217個
4 142,034,872個
5 1,753,062,047個
6 7,877,503,209個
7 14,312,385,526個
8 10,445,405,851個
9 2,865,203,856個
10 209.125.527個

10兆以下

各桁の数字の種類の数 素数の数
1 5個
2 21,931個
3 9,027,553個
4 541,797,196個
5 8,843,677,758個
6 51,537,570,823個
7 121,153,557,156個
8 116,461,576,255個
9 42,948,123,092個
10 4,570,185,070個

あおやぎのさいと2.0初歩の整数論プログラミング