18
\$\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 N:

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

From that, we can generate the prime number sequence, let's call it P, such that every element in P has exactly two divisors in 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 N, with the condition 0 <= x <= 9, and a number y from 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 -> {p : p in P and F(z,p) subset of 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 <= x <= 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

\$\endgroup\$
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

\$\endgroup\$
  • 1
    \$\begingroup\$ The trailing " is unnecessary, very nice work though. \$\endgroup\$ – FryAmTheEggman Oct 6 '15 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 Oct 7 '15 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.

\$\endgroup\$
  • \$\begingroup\$ +1 for O(scary) \$\endgroup\$ – AdmBorkBork Oct 5 '15 at 15:03
  • 1
    \$\begingroup\$ Nice trick in setting i to None. \$\endgroup\$ – lirtosiast Oct 6 '15 at 3:37
3
\$\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

\$\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.

\$\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.