22
\$\begingroup\$

Well, the librarian caught you cheating at your job by using your sorting algorithm, so now you're being punished. You've been ordered to create some code so the librarian can impress the object of their unrequited affection, the math teacher. So that's what "Other duties as assigned" means ...

Everyone is familiar with the natural number sequence in base 10, called \$\mathbb N\$:

0, 1, 2, 3, 4, 5, 6, ...

From that, we can generate the prime number sequence, let's call it \$\mathbb P\$, such that every element in \$\mathbb P\$ has exactly two divisors in \$\mathbb N\$, namely 1 and itself. This sequence is:

2, 3, 5, 7, 11, 13, ...

OK, pretty routine so far.

The librarian thought of a nifty function \$F(x, y)\$ that takes a number \$x\$ from \$\mathbb N\$, with the condition \$0 \le x \le 9\$, and a number \$y\$ from \$\mathbb N\$, and inserts \$x\$ into \$y\$'s decimal expansion in every position (i.e., prepending, inserting, or appending \$x\$ into \$y\$), then returns the sorted set of new numbers.

For example, \$F(6, 127)\$ would result in

1267, 1276, 1627, 6127

That's still kinda boring, though. The librarian wants to spice things up a bit more by instead specifying a new function \$z \to \{p : p \in \mathbb P , F(z,p) \subset \mathbb P\}\$, sorted ascending.

For example, \$z(7)\$ would be

3, 19, 97, 433, 487, 541, ...

because \$37\$ and \$73\$ are both prime, \$719\$, \$179\$ and \$197\$ are all prime, etc.

Note that \$z(2)\$ is empty, because no prime that has a \$2\$ appended will ever still be prime. Similarly for \$\{0,4,5,6,8\}\$.

Your task is to write code that will generate and output the first 100 numbers in sequence \$z(x)\$ for a given \$x\$.

Input

A single integer \$x\$ such that \$0 \le x \le 9\$. Input can be via function argument, STDIN, or equivalent.

Output

A sequence of the first 100 numbers, delimited by your choosing, to STDOUT or equivalent, such that the sequence satisfies \$z(x)\$ as described above. If \$z(x)\$ is empty, as is the case for \$\{0,2,4,5,6,8\}\$, the words Empty Set should be output instead.

Restrictions

  • This is code-golf, since you'll need to transcribe this to an index card so the librarian can show the math teacher, and your hand cramps easily.
  • Standard loophole restrictions apply. The librarian doesn't tolerate cheaters.

Reference sequences

x=1 : A069246
x=3 : A215419
x=7 : A215420
x=9 : A215421

Related: Find the largest fragile prime / Find the smallest prime from a substring / Find largest prime which is still a prime after digit deletion

Improve this question
\$\endgroup\$

6 Answers 6

Reset to default
5
\$\begingroup\$

Pyth, 49 bytes

Like the Python3 and other Pyth answer, the runtime for finding 100 numbers is prohibitive. (test suite gives 10)

?}z"1379".f&!tPZ!|FmtPvjzc`Z]dhl`Z*TT3"Empty Set"

Try it online

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The trailing " is unnecessary, very nice work though. \$\endgroup\$
    – FryAmTheEggman
    Commented Oct 6, 2015 at 13:30
  • \$\begingroup\$ Thanx for the reminder. Because EOL no longer terminates a string, I've avoided unterminated strings, but of course, EOF still works \$\endgroup\$
    – Brian Tuck
    Commented Oct 7, 2015 at 6:27
4
\$\begingroup\$

Python 3, 188 bytes

x=input()
k=1
i=100
if x in"024568":i=print("Empty Set")
while i:k+=1;s=str(k);i-=all(sum(p%d<1for d in range(2,p))<4for p in[k*int(s[:j]+x+s[j:])for j in range(len(s)+1)])and not print(k)

Badly golfed, but here's something for now. Instead of checking p in P and F(z,p) subset of P, we check that p*f is a semiprime for each f in F(z,p). Combine that with trial division for primality testing, and you get an O(scary) algorithm.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice trick in setting i to None. \$\endgroup\$
    – lirtosiast
    Commented Oct 6, 2015 at 3:37
4
\$\begingroup\$

Perl, 124 bytes

$p=prime_iterator;y/1379//or$i=+~print'Empty Set'}while($i<100){$_=&$p;is_prime"$`@F$'"or redo while//g;$i++

Requires the following command line option: -palMntheory=:all, counted as 16. Input taken from stdin.

Uses @DanaJ's Math::Prime::Util module for perl (loaded with the pragma ntheory). Get it with:

cpan install Math::Prime::Util
cpan install Math::Prime::Util::GMP

is_prime is deterministic for all values less than 264, which is sufficient for our purposes.

Sample Usage

$ echo 2|perl -palMntheory=:all oscary.pl
Empty Set

$ echo 7|perl -palMntheory=:all oscary.pl
3
19
97
433
487
541
691
757
853
1471
.
.
.
718705783
720574573
737773357
745157779
747215167
767717017
768743377
770294977
771778477
774577777

Expected Runtimes

x = 1 : 1m 09.2s
x = 3 : 0m 04.2s
x = 7 : 2m 52.5s
x = 9 : 0m 11.5s

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 37 bytes

D-ṭJœṖ€$j€Ṗ€ḌẒȦ
1Ẓ×çɗȷ2#µ“¬ḟ¦⁻v»ẇ?⁽¢°

Try it online! (takes the first 10 instead of 100)

How it works

D-ṭJœṖ€$j€Ṗ€ḌẒȦ - Helper link. Takes n on the left and d on the right
D               - Digits of n
 -ṭ             - Append -1; Call this D
       $        - To the digits:
   J            -   Indices; Yield [1, 2, ..., len(D)]
      €         -   Over each index i:
    œṖ          -     Partition D at the index i
        j€      - Join each with d
          Ṗ€    - Remove the -1s
            Ḍ   - Convert back to integers
             Ẓ  - Is prime?
              Ȧ - True for all?

1Ẓ×çɗȷ2#µ“¬ḟ¦⁻v»ẇ?⁽¢° - Main link. Takes a digit d on the left
                 ?    - If statement:
                ẇ ⁽¢° -   Condition: d is one of 1,3,7,9?
        µ             -   Then:
    ɗ                 -     Define a dyad f(n, d):
 Ẓ                    -       n is prime?
  ×                   -       and
   ç                  -       the helper link is true
1    ȷ2#              -     Count up k = 1, 2, ... and return the first 100 k for
                             which f(k, d) is true
         “¬ḟ¦⁻v»      -   Else: Return "Empty Set"
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pyth, 58

L}bPb|*"Empty Set"}Qj204568T.f&yZ.Amyi++<JjZTdQ>JdThl`Z100

This test suite only calculates the first 10 numbers because it takes far too long to generate the rest. Brute forces both primality and the inserting of the digits. Demonstrates such bad performance that I haven't been able to run it up to 100, so please tell me if there are problems.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 25 bytes

₀+æ[λS₅ʀ?vṀ⌊JæA;₁ȯ|`∵Ǒ ƛ£

Try it Online! (first 5)

   [                      # If
₀+                        # 10+input
  æ                       # Is prime
                 ȯ        # Find the first
                ₁         # 100
    λ          ;          # positive integers where
              A           # All of
            J             # n and
        ?                 # Input digit
         vṀ               # Inserted at
       ʀ                  # Indices 0..
      ₅                   # len(input)
     S                    # In str(input)
           ⌊              # Converted back to integers 
             æ            # Are prime? 
                  |       # Otherwise
                   `∵Ǒ ƛ£ # "Empty Set"
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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