15
\$\begingroup\$

Task

Your task is to print or output all positive numbers in which every multi-digit substring in its decimal representation is also prime. If the number has at least 2 digits, this would imply that the number itself also needs to be prime.

Example

  • 6197 is in the sequence because every multi-digit substring in 6197 is prime, namely: 61, 19, 97, 619, 197, 6197 (itself).
  • Note that 6 is not a prime but 6197 is still in the sequence because 6 is not a multi-digit substring of 6197.
  • 8 is also in the sequence because every multi-digit substring in 8 is prime. There is no multi-digit substring in 8, so this is a case of vacuous truth.

Specs

  • Standard loopholes apply, except that you are allowed to hardcode the output or store information related to the output in your program.
  • The numbers in the output can be in any order.
  • The numbers in the output are allowed to have duplicates.
  • You may use any separator, if you choose to print instead of output.
  • You are allowed to prefix and/or postfix output if you choose to print instead of output.
  • The separator and the prefix and the postfix may not contain any digits (U+0030 to U+0039).

Full list (58 items)

1
2
3
4
5
6
7
8
9
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
113
131
137
173
179
197
311
313
317
373
379
419
431
479
613
617
619
673
719
797
971
1373
3137
3797
6131
6173
6197
9719

Reference


As always, please feel free to address in the comments anything I should clarify.

\$\endgroup\$
  • 2
    \$\begingroup\$ I will give +300 bounty to anyone except @Fatalize who submits the smallest answer to this challenge in Brachylog (wiki link) (TIO link) (chatroom). \$\endgroup\$ – Leaky Nun Aug 16 '16 at 16:17
  • 2
    \$\begingroup\$ Poor @Fatalize. That's what you get for creating a language \$\endgroup\$ – Luis Mendo Aug 16 '16 at 16:31
  • 3
    \$\begingroup\$ I have a 50 bytes answer :( \$\endgroup\$ – Fatalize Aug 17 '16 at 6:48
  • 1
    \$\begingroup\$ Must the program terminate? \$\endgroup\$ – Fatalize Jul 3 '17 at 8:00
  • 2
    \$\begingroup\$ @LeakyNun Looks like somebody's going to get that bounty! \$\endgroup\$ – Jordan Oct 11 at 16:22

20 Answers 20

8
\$\begingroup\$

Brachylog, 18 bytes

9719⟦₁{sᶠℕ₁₀ˢṗᵐ&}ˢ

Try it online!

So...am I ready for the "bounty"? :D

\$\endgroup\$
7
\$\begingroup\$

05AB1E, 15 13 bytes

Code:

4°GN§ŒD9›ÏpP–

Explanation:

  G            # For N in range 1,
4°             #   10000
   N           # Push N
    §          # Convert that to string
     Π        # Get all substrings
      D9›Ï     # Keep all substrings that are greater than 9
          p    # Check each of them if they are prime
           P   # Product
            –  # If 1, print N

Uses the CP-1252 encoding. Try it online! (might take a few seconds).

\$\endgroup\$
4
+300
\$\begingroup\$

Brachylog, 18 17 15 16 15 bytes

ℕ₁<l4&≜sᶠ{Ḋ|ṗ}ᵐ

Try it online!

-1 byte after a discussion with Fatalize inspired me to just see what happens if I swap the l and the < around.

This predicate generates the output through the input variable, so long as the output variable is left unconstrained. Since duplicates are allowed, each number is generated with multiplicity equal to 2 to the power of the number of its digits which are prime numbers.

ℕ₁                 The input variable is a natural number
  <                less than
   l4              some number with length 4 (maximized as 9999).
     &≜            Assign a number to the input, and assert that
       sᶠ          every substring of it
         { | }ᵐ    is either
            ṗ      a prime number
          Ḋ        or a single digit.

Older versions:

{≜ℕsᶠ{Ḋ!|ṗ}ᵐ&}ᶠ⁵⁹b
7^₅⟦₁{sᶠ{Ḋ|ṗ}ᵐ&}ˢ
8ḟ⟦₁{sᶠ{Ḋ|ṗ}ᵐ&}ˢ
∧8ḟ>?ℕ₁≜sᶠ{Ḋ|ṗ}ᵐ
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 18 bytes

Another Brachylog solution. I couldn't get it shorter than Erik The Outgolfer's Brachylog solution; it's the exact same length, but approaches the generation from the opposite direction.

{≜ℕ{sℕ₁₀}ᶠṗᵐ&}ᶠ⁵⁹b

Looks like Unrelated String has beaten this by many a character, whom I congratulate.

Explanation:

{≜ℕ                Brute force all nonnegative integers to find any that match the constraints
   {s               Create a predicate that finds all subsequences of digits of said integer
     ℕ₁₀            Constrains those subsequences to be >= 10
        }ᶠ          Finds all possible values of that predicate: all multi-digit subsequences
          ṗᵐ        Apply a primality constraint to all of those subsequences
            &       Make the predicate output the input integer rather than a prime subsequence
             }ᶠ⁵⁹   Find the first 59 results (all of the puzzle's solutions, and zero)
                 b  Remove the first element of the list, i.e. 0

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 17 bytes

DẆṖÐfḌÆP€Ạ
³²RÇÐf

My first Jelly answer! Saved 3 bytes thanks to @Leaky Nun!

Try it online

Explanation:

DẆṖÐfḌÆP€Ạ      The helper link, which checks if a given number satisfy the conditions.
DẆ              Convert the argument to a list of its digits and get all its substrings.
  ṖÐf           Remove all lists of length 1.
     ḌÆP€Ạ      Convert back each element to an integer and check if all of them are prime.

³²RÇÐf          Main link.
³²              Create a 100 and square it, which gives 10000.
  R             Create a list from 1 to it.
   ÇÐf          Filter out all the elements where the helper link gives false.
\$\endgroup\$
  • \$\begingroup\$ Congratulations on your first Jelly answer! \$\endgroup\$ – Leaky Nun Aug 16 '16 at 17:05
  • 2
    \$\begingroup\$ RÇÐf can be replaced with Ç€T. ṖÐfḌÆP€ can be replaced with ḌḟDÆP. \$\endgroup\$ – Dennis Aug 16 '16 at 19:56
3
\$\begingroup\$

Java 8, 182 bytes

v->{for(int n=0;++n<1e4;)if(P(n)>0)System.out.println(n);}int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}int P(int n){return n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):n<10?n:p(n);}

Port of gastropner's C (gcc) answer, so make sure to upvote his answer!

Try it online.

Explanation:

// Loop in range [1,10000), and print any primes corresponding to the challenge description
v->{for(int n=0;++n<1e4;)if(P(n)>0)System.out.println(n);}

// Checks if the given integer is a prime (return unchanged input if prime, 0 if not)
int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

// Recursive method that checks if every part of length 2+ is a prime, or is below 10
int P(int n){return n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):n<10?n:p(n);}
\$\endgroup\$
2
\$\begingroup\$

PowerShell v2+, 107 104 bytes

1..10+(11..1e4|?{($x=11..($i=$_)|?{"$i"-match$_}).count-eq($x|?{'1'*$_-match'^(?!(..+)\1+$)..'}).count})

Warning: Kinda Slow

Loops from 11 to 1e4 (i.e., 10000) and pulls out numbers using the Where-Object selector (|?{...}). The clause is two components -- the first loops from 11 up to the current number and uses Where-Object to pull out those numbers that form a substring of the current number (via the -match regex operator). We store those substrings in $x. The second portion loops through $x and uses Where-Object to pull out all primes using the prime regex. We then take the .count of both and the check is actually whether those are -equal. For example, 971 will have $x = (71,97,971) and each of those are prime, so 3-eq3 is $TRUE and thus 971 will be selected.

That result is array-concatenated with a range 1..10. The resulting array is left on the pipeline and output is implicit, with a newline between elements by default.

\$\endgroup\$
2
\$\begingroup\$

Japt, 15 bytes

L²õs f_ã fÅe_°j

Test it

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 144 142 140 136 134 132 bytes

-2 thanks to Kevin Cruijssen. -2 thanks to ceilingcat

...And inspired by that, we can get another 2 bytes from that for loop.

Also shamelessly nicked the rather better prime checker from Kevin Cruijssen's answer for another -4.

p(n,i){for(i=2;i<n;)n*=n%i++||n<10;i=n;}P(n){n=p(n)*(n<99||p(n%100)*p(n%1000)*P(n/10));}f(n){for(n=1e4;--n;)P(n)&&printf("%d\n",n);}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ ||n<10 can be |n<10 and for(n=1;n<1e4;n++) can be for(n=0;++n<1e4;) for -2 bytes. \$\endgroup\$ – Kevin Cruijssen Mar 29 '18 at 11:34
  • \$\begingroup\$ @KevinCruijssen Cheers! \$\endgroup\$ – gastropner Mar 29 '18 at 14:26
2
\$\begingroup\$

Malbolge Unshackled (20-trit rotation variant), 2,5254e7 bytes or 1,9809e7 bytes

Size of this answer exceeds maximum postable program size (eh), so the code is located in my GitHub repository (note: Don't copy the code using CTRL+A and CTRL+C, just rightclick and click "Save destination element as...").

How to run this?

This might be a tricky part, because naive Haskell interpreter will take ages upon ages to run this. TIO has decent Malbogle Unshackled interpreter, but sadly I won't be able to use it (limitations).

The best one I could find is the fixed 20-trit rotation width variant, that performs very well.

To make the interpreter a bit faster, I've removed all the checks from Matthias Lutter's Malbolge Unshackled interpreter.

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

const char* translation = "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72Fh"
        "OA1CB6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@";

typedef struct Word {
    unsigned int area;
    unsigned int high;
    unsigned int low;
} Word;

void word2string(Word w, char* s, int min_length) {
    if (!s) return;
    if (min_length < 1) min_length = 1;
    if (min_length > 20) min_length = 20;
    s[0] = (w.area%3) + '0';
    s[1] = 't';
    char tmp[20];
    int i;
    for (i=0;i<10;i++) {
        tmp[19-i] = (w.low % 3) + '0';
        w.low /= 3;
    }
    for (i=0;i<10;i++) {
        tmp[9-i] = (w.high % 3) + '0';
        w.high /= 3;
    }
    i = 0;
    while (tmp[i] == s[0] && i < 20 - min_length) i++;
    int j = 2;
    while (i < 20) {
        s[j] = tmp[i];
        i++;
        j++;
    }
    s[j] = 0;
}

unsigned int crazy_low(unsigned int a, unsigned int d){
    unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
    int position = 0;
    unsigned int output = 0;
    while (position < 10){
        unsigned int i = a%3;
        unsigned int j = d%3;
        unsigned int out = crz[i+3*j];
        unsigned int multiple = 1;
        int k;
        for (k=0;k<position;k++)
            multiple *= 3;
        output += multiple*out;
        a /= 3;
        d /= 3;
        position++;
    }
    return output;
}

Word zero() {
    Word result = {0, 0, 0};
    return result;
}

Word increment(Word d) {
    d.low++;
    if (d.low >= 59049) {
        d.low = 0;
        d.high++;
        if (d.high >= 59049) {
            fprintf(stderr,"error: overflow\n");
            exit(1);
        }
    }
    return d;
}

Word decrement(Word d) {
    if (d.low == 0) {
        d.low = 59048;
        d.high--;
    }else{
        d.low--;
    }
    return d;
}

Word crazy(Word a, Word d){
    Word output;
    unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
    output.area = crz[a.area+3*d.area];
    output.high = crazy_low(a.high, d.high);
    output.low = crazy_low(a.low, d.low);
    return output;
}

Word rotate_r(Word d){
    unsigned int carry_h = d.high%3;
    unsigned int carry_l = d.low%3;
    d.high = 19683 * carry_l + d.high / 3;
    d.low = 19683 * carry_h + d.low / 3;
    return d;
}

// last_initialized: if set, use to fill newly generated memory with preinitial values...
Word* ptr_to(Word** mem[], Word d, unsigned int last_initialized) {
    if ((mem[d.area])[d.high]) {
        return &(((mem[d.area])[d.high])[d.low]);
    }
    (mem[d.area])[d.high] = (Word*)malloc(59049 * sizeof(Word));
    if (!(mem[d.area])[d.high]) {
        fprintf(stderr,"error: out of memory.\n");
        exit(1);
    }
    if (last_initialized) {
        Word repitition[6];
        repitition[(last_initialized-1) % 6] =
                ((mem[0])[(last_initialized-1) / 59049])
                    [(last_initialized-1) % 59049];
        repitition[(last_initialized) % 6] =
                ((mem[0])[last_initialized / 59049])
                    [last_initialized % 59049];
        unsigned int i;
        for (i=0;i<6;i++) {
            repitition[(last_initialized+1+i) % 6] =
                    crazy(repitition[(last_initialized+i) % 6],
                        repitition[(last_initialized-1+i) % 6]);
        }
        unsigned int offset = (59049*d.high) % 6;
        i = 0;
        while (1){
            ((mem[d.area])[d.high])[i] = repitition[(i+offset)%6];
            if (i == 59048) {
                break;
            }
            i++;
        }
    }
    return &(((mem[d.area])[d.high])[d.low]);
}

unsigned int get_instruction(Word** mem[], Word c,
        unsigned int last_initialized,
        int ignore_invalid) {
    Word* instr = ptr_to(mem, c, last_initialized);
    unsigned int instruction = instr->low;
    instruction = (instruction+c.low + 59049 * c.high
            + (c.area==1?52:(c.area==2?10:0)))%94;
    return instruction;
}

int main(int argc, char* argv[]) {
    Word** memory[3];
    int i,j;
    for (i=0; i<3; i++) {
        memory[i] = (Word**)malloc(59049 * sizeof(Word*));
        if (!memory) {
            fprintf(stderr,"not enough memory.\n");
            return 1;
        }
        for (j=0; j<59049; j++) {
            (memory[i])[j] = 0;
        }
    }
    Word a, c, d;
    unsigned int result;
    FILE* file;
    if (argc < 2) {
        // read program code from STDIN
        file = stdin;
    }else{
        file = fopen(argv[1],"rb");
    }
    if (file == NULL) {
        fprintf(stderr, "File not found: %s\n",argv[1]);
        return 1;
    }
    a = zero();
    c = zero();
    d = zero();
    result = 0;
    while (!feof(file)){
        unsigned int instr;
        Word* cell = ptr_to(memory, d, 0);
        (*cell) = zero();
        result = fread(&cell->low,1,1,file);
        if (result > 1)
            return 1;
        if (result == 0 || cell->low == 0x1a || cell->low == 0x04)
            break;
        instr = (cell->low + d.low + 59049*d.high)%94;
        if (cell->low == ' ' || cell->low == '\t' || cell->low == '\r'
                || cell->low == '\n');
        else if (cell->low >= 33 && cell->low < 127 &&
                (instr == 4 || instr == 5 || instr == 23 || instr == 39
                    || instr == 40 || instr == 62 || instr == 68
                    || instr == 81)) {
            d = increment(d);
        }
    }
    if (file != stdin) {
        fclose(file);
    }
    unsigned int last_initialized = 0;
    while (1){
        *ptr_to(memory, d, 0) = crazy(*ptr_to(memory, decrement(d), 0),
                *ptr_to(memory, decrement(decrement(d)), 0));
        last_initialized = d.low + 59049*d.high;
        if (d.low == 59048) {
            break;
        }
        d = increment(d);
    }
    d = zero();

    unsigned int step = 0;
    while (1) {
        unsigned int instruction = get_instruction(memory, c,
                last_initialized, 0);
        step++;
        switch (instruction){
            case 4:
                c = *ptr_to(memory,d,last_initialized);
                break;
            case 5:
                if (!a.area) {
                    printf("%c",(char)(a.low + 59049*a.high));
                }else if (a.area == 2 && a.low == 59047
                        && a.high == 59048) {
                    printf("\n");
                }
                break;
            case 23:
                a = zero();
                a.low = getchar();
                if (a.low == EOF) {
                    a.low = 59048;
                    a.high = 59048;
                    a.area = 2;
                }else if (a.low == '\n'){
                    a.low = 59047;
                    a.high = 59048;
                    a.area = 2;
                }
                break;
            case 39:
                a = (*ptr_to(memory,d,last_initialized)
                        = rotate_r(*ptr_to(memory,d,last_initialized)));
                break;
            case 40:
                d = *ptr_to(memory,d,last_initialized);
                break;
            case 62:
                a = (*ptr_to(memory,d,last_initialized)
                        = crazy(a, *ptr_to(memory,d,last_initialized)));
                break;
            case 81:
                return 0;
            case 68:
            default:
                break;
        }

        Word* mem_c = ptr_to(memory, c, last_initialized);
        mem_c->low = translation[mem_c->low - 33];

        c = increment(c);
        d = increment(d);
    }
    return 0;
}

Performance notes

The application ran about 40 minutes on my machine, producing HEX numbers of the sequence. I stopped it around an hour of calculations, and it finished on 0x11.

Note this answer differs from my other one, because this one actually calculates the numbers, and it can be made so it calculates them indefinitely.

The application allocates the spinup buffer, that is around 7 gigabytes big, so better prepare your free RAM.

Alternative variant

Alternative variant uses around 2 gigabytes of memory less, but produces the output in form of ASCII characters (0 = ASCII(0x0), 10 = newline, etc...), and is available here. It doesn't compete though, due to challenge requirements

\$\endgroup\$
  • \$\begingroup\$ Code golf is about giving short answers. \$\endgroup\$ – Alfe Oct 14 at 13:48
  • 2
    \$\begingroup\$ @Alfe Malbolge is a language that was designed to be extremely difficult to program in (wikipedia link); the fact that this is even possible is pretty impressive. \$\endgroup\$ – Giuseppe Oct 14 at 14:38
  • 4
    \$\begingroup\$ So, in fact, this is a short answer. Just the standards are shifted. Slightly. \$\endgroup\$ – Alfe Oct 14 at 14:55
  • 3
    \$\begingroup\$ @Alfe you're welcome to try to shave some bytes off! ;-) \$\endgroup\$ – Giuseppe Oct 16 at 1:27
2
\$\begingroup\$

Python 3, 118 bytes

r=range(9720)
for n in r[1:]:all(all(l%k+9//l for k in r[2:l])for l in(n%10**(i%5)//10**(i//5)for i in r))and print(n)

Try it online!

Explanation

Warning: no actual strings involved in this solution.

r=range(9720)
for n in r[1:]:                                        # For each positive integer up to 9720
 all( ... for l in(n%10**(i%5)//10**(i//5)for i in r)) # Check for all its substrings
  all(l%k ... for k in r[2:l])                         # If it is either prime
   +9//l                                               # Or smaller than 10
and print(n)                                           # Then print
\$\endgroup\$
1
\$\begingroup\$

Ruby, 81 + 8 = 89 bytes

+8 bytes for -rprime.

puts (?1..?9*4).select{|m|(r=2..m.size).all?{|i|r.all?{|j|m[i-2,j].to_i.prime?}}}

See it on repl.it: https://repl.it/CniR/2

\$\endgroup\$
1
\$\begingroup\$

Perl 6,  47 44  43 bytes

for 1..9719 {all(m:ex/..+/).Int.is-prime&&.say}
put grep {is-prime +all(m:ex/..+/):},1..9719
put grep {is-prime +all m:ex/..+/:},1..9719

Explanation:

# print the values space separated, with trailing newline
put

# that match
grep -> $_ {

  # call the method 「.is-prime」 ( that is what 「:」 is for )
  # (autothreaded)
  is-prime

  # convert following to numeric (autothreaded)
  +
  # a junction of
  all(
    # all substrings 2 characters or greater
    $_ ~~ m :exhaustive / . .+ /
  )

  # needed to indicate that 「is-prime」 is a method call
  :

},

# in this Range
1..9719
\$\endgroup\$
1
\$\begingroup\$

C#, 261 249 247 bytes

Saved 12 bytes thanks to Leaky Nun

()=>{Action<int>w=System.Console.WriteLine;int i=0,n,j,k,p,m,b;for(;++i<10001;){n=(i+"").Length;if(n<2)w(i);else{b=1;for(j=1;++j<=n;)for(k=0;k+j<=n;){p=int.Parse((i+"").Substring(k++,j));if(p%2<1)b=0;for(m=3;m<p;m+=2)if(p%m<1)b=0;}if(b>0)w(i);}}};

This compiles to a Func<List<int>>.

The formatted version looks like:

() =>
{
    Action<int> w = System.Console.WriteLine;

    int i = 0, n, j, k, p, m, b;

    for (; ++i < 10001;)
    {
        n = (i + "").Length;

        if (n < 2)
            w(i);

        else
        {
            b = 1;
            for (j = 1; ++j <= n; )
                for (k = 0; k + j <= n; )
                {
                    p = int.Parse((i + "").Substring(k++, j));

                    if (p % 2 < 1)
                        b = 0;

                    for (m = 3; m < p; m += 2)
                        if (p % m < 1)
                            b = 0;
                }

            if (b > 0)
                w(i);
        }
    }
};
\$\endgroup\$
  • \$\begingroup\$ Just print it directly without using a list \$\endgroup\$ – Leaky Nun Aug 16 '16 at 16:14
  • \$\begingroup\$ Instead of false or true, use 0>1 and 0<1 \$\endgroup\$ – Leaky Nun Aug 16 '16 at 16:14
  • \$\begingroup\$ You may refer to this for additional golfing tips. \$\endgroup\$ – Leaky Nun Aug 16 '16 at 16:15
  • \$\begingroup\$ @LeakyNun Thanks for the tips, I usually like to get a kinda golfed version posted then move from there. \$\endgroup\$ – TheLethalCoder Aug 16 '16 at 16:15
1
\$\begingroup\$

Swift 4, 144 bytes

let p={n in !(2..<n).contains{n%$0<1}}
print((1...971).filter{$0<10||p($0)&&($0<100||p($0/10)&&p($0%100))}+[1373,3137,3797,6131,6173,6197,9719])

Try it online!

Explanation

let p={n in !(2..<n).contains{n%$0<1}} // Helper function p, tests if a number is prime
print((1...971).filter{                // Print every number n in the range 1 to 971
 $0<10                                 //  that is less than 10
 ||p($0)&&                             //  or a prime and
 ($0<100                               //   is less than 100 or
  ||p($0/10)&&p($0%100))}              //   n/10 and n%100 are primes
+[1373,3137,3797,6131,6173,6197,9719]) // Print the four digit numbers
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 130 bytes

if i can assume infinite stack i*i<=n&& can be removed and i*i>n turns to i>=n which reduces the code by 9 bytes and maybe convert main function to recursive : https://tio.run/##LYpBDoIwEEX33AMyAxVbXUmccgX2xkWDRYeQaSPqyrvXkrj5ef/lze7j1vHJ8bWTcPMpTQRMWjm6XJFs0/DZ@EM/ASunBmCsKtfG9/rIiJ0rIoEoJpNbKXPdx@1jx5akGEiytqdNYp2nNFr/wR@xHkD2Rn81dpLGIGtYfLuEO0yAmH4 (119 bytes)

_=>eval(`for(a=[i=1];++i<1e4;)P(i)&&a.push(i)`)||a
p=(n,i=1)=>i*i<=n&&n%++i?p(n,i):n%i
P=n=>n>9?p(n)*p(n%100)*p(n%1e3)*P(n/10|0):n

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Malbolge, 1361 bytes

Simple and boring version. Displays numbers from the highest.

D'`r^"!=[YG3yUCvA-csNqp-nJ$HYFgDC#AbQ,|*)\rwvutm3kSonmlkdihg`&dc\aZ_X|V[ZYXQPt7SRQPOHGkKJIHG@d>=<A:98\}|:981U5.-2+0/.'K%$#G!E}e#z!~}v<]yxwpun4rkj0nmfN+ihaf_^$\a`_XW{>=YXWVONrLKPINGkE-IBAe(>=<;_?>=}|:3W1w543,P0).-&J*)(!E}|B"!~}|{zyr8potml2jongfkjibg`&d]\"`_XW{>=YXWVONr54JIHMFj-,HGF?>b%A@?87[;:981w543,P0).-&J*j(!EfeB"!~}_u;yrqpun4rqpihmlkjihg`&d]\"`_X|\[ZYXQuUNMLQJnH0LKJIBAe(>=<`#"8\<5Y9270T43,Pqp.-&J$)"!~D|#"y~}|u;s9qvotsrk1inglkdihg`&d]\"Z~XWVUZYXQu87SLKo2NGFjDIHGF?>bBA#"8\6;:981Uv.32+*)Mnm%$)('~D|{A!xwv{zyr8vXnsrkjoh.fNdchg`ed]#aC_^WVz=YXQPt7SRQPOHGkK-IHGF?>bBA#"8\6;:981Uv.32+*)Mnm%*#"F&%$#cy?}v<]\xwpun4rqSonmf,diha'eG]#a`_X|V[ZYXWPt76LKoIHGLEiCHGFED=aA:?>7[;:981w/4-,PO)o'&J*j(!E%edz@~}_u;yxqpo5mrqpoh.f,jibgf_%]\[!_XW{[ZYXQu87SLKo2NGFjJIHAF?c=BA@?>=<5Y38765.-Q10)o'&J*j(!E%e{z@~}|{ts9qpotsrk1oQglkd*)gIed]#DZ_^]VzZYRQuONMRKJnNGLEJCgG)(D=aA:?>=<;4X816/43,P0).-&+$H('gf|Bcb~w|u;yxwYutmrqj0nmleMib(fH%cba`_X|VUZYXWPt7SRQPOHGkEDIHG@dDC<;@?8\6|:32V0T43,+O)o'&J*)('&}C{"yxwv<tyr8vun4Ukpoh.fN+c)gIed]#DZ_^]VzTSRWPtTSLQJnH0LKJIBAe(>=BA@987[;:381Uv.32+*)Mnm%$)('~D${"y?}_uzyxqpo5srqSonmf,jihgfeG]#a`_X|V[ZYXWPt76LKo2NGFjJIH*)ED=a;@?>76;4X816/43,P*).',%I)('~Ded"y~}|u;srqvo5mlqpih.fN+cba`&d]\aZ~^]VUZSwWPUTSLpJ2NGLEiCHGFED=a;:?>7<5YX876v43,+O).-,+$H('&feBz!x}v{zsr8punsrk1inglkdihg`&d]\"Z~X]V[ZSwQVUTMRKo2NGFjDIHGF?>b%A@?87[;{921U5.3210)M-,%k#(!EfeB"y~}v{zyr8%

Try it online!

\$\endgroup\$
0
\$\begingroup\$

TI-83/84 BASIC, 124 Bytes

For(A,1,E4
DelVar Nint(log(A→P
Ans→Q
While Ans
For(I,0,Q-Ans
10^(P+1
AnsfPart(iPart(A/10^I)/Ans→S
min(Ans={2,3,5
If S≥7 and fPart(.5S
min(remainder(S,3+2cumSum(not(binompdf(int(.5√(S)),0
N+not(Ans→N
End
P-1→P
End
If not(N
Disp A
End

Loops over the first 10k integers. Sets up a counter in N to check each substring prime, and int(log(A retrieves one less than the number of digits in the current number. We then set that number aside in a second variable so we can step P down through each length substring at least 2 digits. 10^... and AnsfPart(iPart(,,, generate the current substring to check for primality, then the following 3 lines do the primality check to 1 or 0 in Ans. If the substring is not prime, we increment N, and after all the substrings are checked if N is still 0 we print the current number.

Possibly some tweaking could be done to increase the efficiency of the primality check toward this test? I'm just glad I found an algorithm in fewer bytes than storing the output directly in TI-83 formatting!

\$\endgroup\$
0
\$\begingroup\$

Python 3.8 (pre-release), 194 bytes

r=range
s=str
l=lambda _:len(s(_))
[*map(print,[t for t in r(1,10**4) if all(all(int(x)%b for b in r(2,int(x))) for x in [s(t)[i:j+1] for i in r(l(t)) for j in r(i,l(t)) if l(s(t)[i:j+1])>1])])]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 135 bytes

for(;++$n<1e4;$p||print"$n
")for($p=$i=0;$i<$l=strlen($n);$i++)for($j=1;$j++<$l-$i;$p|=$k)for($k=($m=substr($n,$i,$j))-1;$k&&$m%$k--;);

Try it online!

for(;                         // level 1 loop on
  ++$n<1e4;                   // all numbers from 1 to 10,000, $n is current number
  $p||print"$n\n"             // at the end of loop for each number, print $n if all multi digit sub strings were prime ($p=0)
)
  for(                        // level 2 loop on each digit of $n
    $p=                       // $p is a flag for all sub string primes and is set to 0 for each new $n
      $i=0;                   // $i is position of current digit (and sub string start position)
    $i<$l=strlen($n);         // $l is the total digits count in $n
    $i++                      // increment $i by one
  )
    for(                      // level 3 loop to create sub strings
      $j=1;                   // $j is length of sub string, we only care about multi digit sub strings so it starts from 1
      $j++<$l-$i;             // continue the loop as long as $j has not reached last digit and increment it by one
      $p|=$k                  // THIS IS RUN AFTER LOOP LEVEL 4: update $p flag based on value of $k
                              //     $p will be left at 0 only if all of the sub strings are prime (if $k is always 0)
    )
      for(                    // level 4 loop to check each sub string to be prime
        $k=(                  // $k is set to current sub string minus 1
          $m=substr($n,$i,$j) // $m is current sub string
        )-1;                  // 
        $k && $m%$k--;        // as long as $k is more than 0 and $m%$k is not zero, decrement $k by one and continue
                              //     a prime number will only get a 0 remainder, when $k gets to 1
                              //     so $k will be 0 for primes and more than 0 for non-primes
      );
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.