11
\$\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\$
  • \$\begingroup\$ For reference, it's 200 bytes simply for the string of digits. \$\endgroup\$ – AdmBorkBork Aug 16 '16 at 15:05
  • \$\begingroup\$ @Dopapp "standard loopholes apply" \$\endgroup\$ – Leaky Nun Aug 16 '16 at 15:09
  • 1
    \$\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
  • 1
    \$\begingroup\$ Poor @Fatalize. That's what you get for creating a language \$\endgroup\$ – Luis Mendo Aug 16 '16 at 16:31
  • 2
    \$\begingroup\$ I have a 50 bytes answer :( \$\endgroup\$ – Fatalize Aug 17 '16 at 6:48

11 Answers 11

4
\$\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\$
3
\$\begingroup\$

Brachylog, 18 bytes

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

Try it online!

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

\$\endgroup\$
2
\$\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
  • 1
    \$\begingroup\$ RÇÐf can be replaced with Ç€T. ṖÐfḌÆP€ can be replaced with ḌḟDÆP. \$\endgroup\$ – Dennis Aug 16 '16 at 19:56
2
\$\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\$
1
\$\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\$
1
\$\begingroup\$

C (gcc), 144 142 140 136 bytes

-2 thanks to Kevin Cruijssen.

...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:0;i=n;}P(n){n=n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):p(n)|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
0
\$\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\$
0
\$\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\$
0
\$\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
0
\$\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\$
0
\$\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\$

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.