experimental-projects/oeis-research/Michel Marcus/Primes where every 0-splitting is prime/prog.pl

#!/usr/bin/perl

# Daniel "Trizen" Șuteu
# Date: 08 August 2019
# https://github.com/trizen

# !!! UPDATE !!! a(5) does NOT exist!
# https://www.primepuzzles.net/puzzles/puzz_970.htm

# Sequence by Michel Marcus, Aug 08 2019:
#   a(n) is the least prime that can be written as a sequence of primes separated by n single zeros, and where every 0-splitting is prime.

# OEIS:
#   https://oeis.org/A309566

# a(n) = {307, 130307, 309370307, ...}

# Example:
#   130307 is a term since 3, 7, 13, 307, 1303, 130307 are all prime.

# Upper-bound for a(4):
#   a(4) <= 30281172370306703

# In 09 August 2019, Giovanni Resta confirmed:
#   a(4) = 30281172370306703

# Examples for a(4):
#   30281172370306703, 301594362103085903, 303761778310306703, 304443276703085903, 305939303094354103, 3011778479030992903, 3011896539670306703, 3012927194890306703, 3014963894903097103, 3016816935703093703, 3023139498103093703, 3026588214703075703, 3032246286703075703, 3035470309252484903, 3037764428290306703, 3038473344190306703, 3039932330304465103, 3044821843103097103, 3049368719030358103, 3049985459770306703, 3057445198903075703, 3061847197030993103, 3064846888303093703, 3067030183974572303, 3067030332163394903, 3067030348527266903, 3067030478639642303, 3067030497473248703, 3067030997681711303, 3067645533103075703, 3072491497703097103, 3072749526103085903, 3073889590305544103, 3073963252903093703, 3075577030113527903, 3078489641030718703, 3084581832490306703, 3084649030419787703, 3086251985903097103, 3093183836530306703, 3093183838103097103, 30124737689030718703, 30183614870309146303, 30195833413030354703, 30228888229303075703, 30265851669103075703, 30465664615303075703, 30515363257303075703, 30543121279903075703, 30552963618703075703, 30593930303461578103, 30595584988303075703, 30658392925903075703, 30665897679103075703, 30792830304538443103, 30859030371371987303, 30859030593194365703, 30859030712278822103, 30861769663030354703, 30877390305379612103, 30937030215236599703, 30937030367883386303, 30937030415566234103, 30937030461799766903, 30937030568452513103, 30937030635824981903, 30937030724629916303, 30939861431030992903, 30971030354345164903, 30971030684898898903, 30971030891554947103, 30971030971751481703, 30971030992452727303, 301111195733030358103, 301155918319030354703, 301177237253030227303, 301182958529030899903, 301457243267030899903, 301895697247030993103, 301954662769030993103, 301968654439030354703, 302145543341030752903, 302178129677030718703, 302273030783455968703, 302273030798864794303, 302273030943448723303, 302273030951867635903, 302295824591030358103, 302447371181030718703, 302518794379030993103, 302531921143030354703, 302546383691030745103, 302664968561030718703, 302987953469030899903, 303149392669030993103, 303547030232725648703, 303547030256915137103, 303547030624198963103, 303547030753956287303, 303547030819182295703, 303581030216517976903, 303581030225361652303, 303581030624539152703, 303581030693888175103, 303581030739547761103, 303625387553030668903, 303743375543030745103, 303819438431030853703, 304185898931030853703, 304412629751030992903, 304497569459030745103, 304582316261030745103, 304612953677030227303, 304648733281030993103, 304685654327030962903, 304777645351030354703, 304955262413030718703, 304956514699030993103, 305372856263030992903, 305623794551030752903, 305999166773030992903, 306526556789030962903, 306654259489030354703, 306689030353582242703, 306689030788674993103, 306689030924845335103, 306986548411030354703, 307187030298754279903, 307187030596887453703, 307187030792675985103, 307187030817836769703, 307451030117887267903, 307451030414578392703, 307451030441367118303, 307451030674636122103, 307529030179968442903, 307967599427030752903, 308189735963030718703, 308415448829030358103, 308458618691030745103, 308537030244192331303, 308537030289217692103, 308537030638276218703, 308537030686626996703, 308537030728574626903, 308537030817544923703, 308537030964448899103, 308982713933030668903, 308999030355783949903, 308999030479684449703, 308999030561545797103, 308999030698945558903, 308999030773651467103, 309399351769030993103, 309629030485525183903, 309629030984544487903, 309913134263030853703, 309929030798191633903, 309929030822141634103, 309931030269443182703, 309931030323235967903, 309931030571152946303, 309931030624229551703, 309991984789030354703

# The n-th term contains binomial(n+2, n) zero-splitting primes (including itself), not necessary distinct.

# The 10 zero-splitting primes in 309370307 are:         [3, 3, 7, 307, 937, 30937, 93703, 3093703, 9370307, 309370307]
# The 15 zero-splitting primes in 30281172370306703 are: [3, 3, 3, 67, 3067, 6703, 306703, 28117237, 2811723703, 3028117237, 302811723703, 2811723703067, 281172370306703, 302811723703067, 30281172370306703]

# The term a(5), which is currently unknown, would contain 21 zero-splitting primes.

use 5.020;
use ntheory qw(:all);
use experimental qw(signatures);

sub isok ($p) {

    is_prob_prime($p) || return;

    my @P   = split('0', $p);
    my $end = $#P;

    foreach my $i (0 .. $end - 1) {
        foreach my $j ($i + 1 .. $end) {
            is_prob_prime(join('0', @P[$i .. $j])) || return;
        }
    }

    vecall { is_prob_prime($_) } @P;
}

# These numbers are OK
foreach my $p (
               qw(
               307 130307 309370307 3067030853 13903093703 22303075703
               30369101303 30670301531 30670302287 30670308887 30752903023 30859030313
               30281172370306703 301594362103085903 303761778310306703 304443276703085903
               305939303094354103 3011778479030992903 3011896539670306703 3012927194890306703
               3014963894903097103 3016816935703093703 3023139498103093703 3026588214703075703
               3032246286703075703 3035470309252484903 3037764428290306703 3038473344190306703
               3039932330304465103 3044821843103097103 3049368719030358103 3049985459770306703
               3057445198903075703 3061847197030993103 3064846888303093703 3067030183974572303
               3067030332163394903 3067030348527266903 3067030478639642303 3067030497473248703
               3067030997681711303 3067645533103075703 3072491497703097103 3072749526103085903
               3073889590305544103 3073963252903093703 3075577030113527903 3078489641030718703
               3084581832490306703 3084649030419787703 3086251985903097103 3093183836530306703
               3093183838103097103 30124737689030718703 30183614870309146303 30195833413030354703
               30228888229303075703 30265851669103075703 30465664615303075703 30515363257303075703
               30543121279903075703 30552963618703075703 30593930303461578103 30595584988303075703
               30658392925903075703 30665897679103075703 30792830304538443103 30859030371371987303
               30859030593194365703 30859030712278822103 30861769663030354703 30877390305379612103
               30937030215236599703 30937030367883386303 30937030415566234103 30937030461799766903
               30937030568452513103 30937030635824981903 30937030724629916303 30939861431030992903
               30971030354345164903 30971030684898898903 30971030891554947103 30971030971751481703
               30971030992452727303 301111195733030358103 301155918319030354703 301177237253030227303
               301182958529030899903 301457243267030899903 301895697247030993103 301954662769030993103
               301968654439030354703 302145543341030752903 302178129677030718703 302273030783455968703
               302273030798864794303 302273030943448723303 302273030951867635903 302295824591030358103
               302447371181030718703 302518794379030993103 302531921143030354703 302546383691030745103
               302664968561030718703 302987953469030899903 303149392669030993103 303547030232725648703
               303547030256915137103 303547030624198963103 303547030753956287303 303547030819182295703
               303581030216517976903 303581030225361652303 303581030624539152703 303581030693888175103
               303581030739547761103 303625387553030668903 303743375543030745103 303819438431030853703
               304185898931030853703 304412629751030992903 304497569459030745103 304582316261030745103
               304612953677030227303 304648733281030993103 304685654327030962903 304777645351030354703
               304955262413030718703 304956514699030993103 305372856263030992903 305623794551030752903
               305999166773030992903 306526556789030962903 306654259489030354703 306689030353582242703
               306689030788674993103 306689030924845335103 306986548411030354703 307187030298754279903
               307187030596887453703 307187030792675985103 307187030817836769703 307451030117887267903
               307451030414578392703 307451030441367118303 307451030674636122103 307529030179968442903
               307967599427030752903 308189735963030718703 308415448829030358103 308458618691030745103
               308537030244192331303 308537030289217692103 308537030638276218703 308537030686626996703
               308537030728574626903 308537030817544923703 308537030964448899103 308982713933030668903
               308999030355783949903 308999030479684449703 308999030561545797103 308999030698945558903
               308999030773651467103 309399351769030993103 309629030485525183903 309629030984544487903
               309913134263030853703 309929030798191633903 309929030822141634103 309931030269443182703
               309931030323235967903 309931030571152946303 309931030624229551703 309991984789030354703
               )
  ) {
    isok($p) || die "false-negative: $p";
}

# These numbers are NOT OK
foreach my $p (
               qw(
               13030307
               202030207
               302030203
               30937030704161
               3074510309146303
               30143088130306703
               30174190301812103
               )
  ) {
    isok($p) && die "false-positive: $p";
}

my @primes = grep { $_ != 2 } grep { $_ != 5 } grep { !/0/ } @{primes(1e4)};

sub generate_from_prefix ($root, $k) {

    #~ return if ($root >= 30281172370306703);

    say "k = $k -> $root" if ($k >= 4);

    if ($k >= 5) {
        die "Found: $root";
    }

    foreach my $p (@primes) {

        my $x = join('0', $root, $p);

        if (isok($x)) {
            __SUB__->($x, $k + 1);
        }
    }
}

sub generate_from_suffix ($root, $k) {

    #~ return if ($root >= 30281172370306703);

    say "k = $k -> $root" if ($k >= 4);

    if ($k >= 5) {
        die "Found: $root";
    }

    foreach my $p (@primes) {

        my $x = join('0', $p, $root);

        if (isok($x)) {
            __SUB__->($x, $k + 1);
        }
    }
}

# Look for special form "30P030Q03", which gives upper-bounds for a(4), where P and Q are primes.
sub special_form_search {

    my @primes_p = @{primes(1e7, 1e7 + 1e6)};    #@{primes(1e5)};
    my @primes_q = @{primes(1e4)};

    foreach my $p (@primes_p) {

        say "Testing: $p";

        foreach my $q (@primes_q) {

            my $t = "30${p}030${q}03";

            if ($t >= 30281172370306703) {
                last;
            }

            is_prime("30${p}")        || next;
            is_prime("${q}03")        || next;
            is_prime("30${q}03")      || next;
            is_prime("${p}030${q}")   || next;
            is_prime("30${p}030${q}") || next;
            is_prime("${p}030${q}03") || next;
            is_prime($t)              || next;

            if (isok($t)) {
                die("Found: $t");
            }
        }
    }
}

#special_form_search();

sub exaustive_search {
    foreach my $p (@primes) {
        say ":: Generating from suffix = $p";
        generate_from_suffix($p, 0);
    }
}

#exaustive_search();

sub generate_from_large_primes {    # generate from large prime prefix and suffix

    forprimes {

        #if (/0/ and not /00/) {
        if (!/0/) {

            #~ if (vecall { is_prime($_) } split('0', $_)) {

            #~ my $count = () = /0/g;
            my $count = 0;

            #~ if ($count >= 4) {
            #~ die "Found: $_" if isok($_);
            #~ }

            #generate_from_prefix($_, $count) if ($count < 3);
            #generate_from_suffix($_, $count) if ($count < 3);

            my $t = '30' . $_ . '03';

            if ($count < 2) {
                if (is_prob_prime('30' . $_) and is_prob_prime($_ . '03') and is_prob_prime($t)) {

                    #say "Generating from suffix = $t";
                    generate_from_prefix($t, $count + 2);
                    generate_from_suffix($t, $count + 2);
                }
            }

            #~ }
        }
    }
    1e7, 1e8;
}

generate_from_large_primes();

__END__

Examples with 3-zeros, for primes < 5000:

k = 3 -> 30369101303
k = 3 -> 35710306703
k = 3 -> 46630306703
k = 3 -> 22303075703
k = 3 -> 369703085903
k = 3 -> 13903093703
k = 3 -> 96703093703
k = 3 -> 186103093703
k = 3 -> 61703097103
k = 3 -> 3036910175303
k = 3 -> 2531030227303
k = 3 -> 2789030227303
k = 3 -> 304670265703
k = 3 -> 3028430286103
k = 3 -> 3022970292703
k = 3 -> 301390388903
k = 3 -> 3045610388903
k = 3 -> 3025790421103
k = 3 -> 309370451903
k = 3 -> 309370307
k = 3 -> 30859030313
k = 3 -> 3067030853
k = 3 -> 3035810301493
k = 3 -> 30670301531
k = 3 -> 307570301867
k = 3 -> 308590301933
k = 3 -> 30670302287
k = 3 -> 3022730302663