13
\$\begingroup\$

Another sequence, another challenge.*

Definition

A prime p is in this sequence, let's call it A, iff for every digit d in p's decimal expansion, you replace d with d copies of d and the resulting integer is still prime; zeros are not permitted.

For example, 11 is trivially in this sequence (it's the first number, incidentally). Next in the sequence is 31, because 3331 is also prime; then 53 because 55555333 is also prime, and so on.

Challenge

Given an input n, return A(n), i.e. the nth item in this sequence.

Examples

Here are the first 20 terms to get you started. This is A057628 on OEIS.

11, 31, 53, 131, 149, 223, 283, 311, 313, 331, 397, 463, 641, 691, 937, 941, 1439, 1511, 1741, 1871

This means A(0) = 11, A(1) = 31, etc., when using zero indexing.

Rules

  • You can choose zero- or one-based indexing; please specify in your answer which.
  • Instead of returning just the nth element, you can instead choose to return the first n terms.
  • You can assume that the input/output will not be larger than your language's native integer format; however, the repeated-digit prime may be larger than your language's native format, so that will need to be accounted for.
  • For example, 1871, the last number of the examples, has a corresponding prime of 18888888877777771, which is quite a bit larger than standard INT32.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Output can be to the console, returned from a function, displayed in an alert popup, etc.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

*To be fair, I had come up with the first few terms of the sequence just playing around with some numbers, and then went to OEIS to get the rest of the sequence.

\$\endgroup\$
  • 2
    \$\begingroup\$ I wonder if there exists a prime whose repeated digit result also is in this sequence, and whose repeated digit result also is in this sequence, and so on, ad infinitum. Seems highly unlikely. \$\endgroup\$ – Steadybox Nov 28 '17 at 21:14
  • 1
    \$\begingroup\$ @Steadybox 11 meets this condition, ad infinitum. But other than that it would be interesting to see how many times you could apply the digit repeating operation and keep getting primes. \$\endgroup\$ – dylnan Nov 28 '17 at 21:20
  • \$\begingroup\$ Given that 1666666999999999 is prime, why isn't 169 in the sequence? \$\endgroup\$ – Pablo Oliva Mar 8 '18 at 21:37
  • 2
    \$\begingroup\$ @PabloOliva Because 169 itself isn't prime, it's 13 * 13. \$\endgroup\$ – AdmBorkBork Mar 9 '18 at 13:26
6
\$\begingroup\$

Husk, 15 bytes

!fo§&öεpd´ṘΠdİp

Try it online!

!                 Index into
             İp     the list of primes
 f                    for which:
            d            the digits of p
  o§&                      satisfy both:
     öεpd´Ṙ                  repeated "themselves" times, they form a prime.
           Π                 they are all nonzero.

Erik the Outgolfer saved a byte. Using instead of εp would save another byte, but that makes the program so slow it times our even for n = 2.

\$\endgroup\$
  • 1
    \$\begingroup\$ @H.PWiz I don't think we judge on speed here... \$\endgroup\$ – Erik the Outgolfer Nov 28 '17 at 21:35
  • \$\begingroup\$ I really should speed up in the interpreter, it's crazy how it's slower than finding all prime factors... \$\endgroup\$ – Zgarb Nov 28 '17 at 21:48
6
\$\begingroup\$

05AB1E, 14 13 bytes

-1 byte thanks to Emigna!

µNSÐPŠ×JpNpPĀ½

Try it online!

Explanation

µNSÐPŠ×JpNpPĀ½
µ              # Do until the input is reached...
 N              # Push the iteration counter
  S             # Split it to its digits
   Ð            # And push two copies of it to the stack
    P           # Get the digital product of the counter
     Š          # And place it two places down the stack
      ×J        # Repeat each digit by itself and join it back to a number
        p       # Check for primality on that result
         Np     # And on the original counter as well
           PĀ   # Create the product and truthify the result
                # Implicit: If it is true increment the input number
\$\endgroup\$
5
\$\begingroup\$

Jelly, 18 14 bytes

ÆPaDxDḌÆPaDẠµ#

Try it online!

Mr. Xcoder: -1 Byte (logical all)

Erik the Outgolfer: -2 Bytes (one line instead of two)

HyperNeutrino: -1 Byte (return first n elements of sequence)

Explanation

ÆPaDxDḌÆPaDẠµ#     First Link
ÆP                Is prime?
  a               logical and
   D              convert number to list of digits
    xD            repeat each digit as many times as it's value
      Ḍ           convert to an integer
       ÆP         is prime?
         a        logical and
          D       list of digits
           Ạ      logical all
            µ     the following link as a monad
             #    Do this until n matches are found and return them all

Edit: originally submitted an answer that included numbers with 0 in it's decimal representation which is specifically not allowed.

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 100 bytes

Nest[#+1//.i_/;!PrimeQ@FromDigits[##&@@#~Table~#&/@(l=IntegerDigits@i)]||Min@l<1:>NextPrime@i&,1,#]&

Try it online!

Jonathan Frech saved 3 bytes

and -7 bytes from JungHwan Min

-15 bytes from Martin Ender

also thanks to Jenny Mathy

\$\endgroup\$
4
\$\begingroup\$

Alice, 72 70 66 62 56 bytes

Thanks to Leo for saving 5 bytes.

/.\&wh...tz~F0/*$\W.tzt$W?K/ o
\i/&.,a:.$K;d&\FR/K.!w.a%

Try it online!

Uses 1-based input.

Explanation

The neatest golfing trick here (even though it only saves a couple of bytes) is that I'm using a primality test which gives 0 for composite n for n for non-composite n. That way, we don't have to use the result directly in a conditional, but we can pass it straight on to the next part that checks that the input doesn't contain any zeros.

/i\       Read all input in Ordinal mode (the usual way to read decimal input).
&w        Push the current IP position onto the return address stack (RAS)
          n times. This effectively begins our main loop. We will return
          here after each number we've checked, but whenever we come across
          a repeated digit prime (RDP), we will pop one copy of the address
          from the RAS, so that the loops ends once we've found n RDPs.

h.        Increment our main loop iterator X (initially an implicit zero on
          the empty stack) and duplicate it.
.         Make another copy.
.tz       Drop all factors less than X. This gives X for prime X and 1 for
          non-prime X.
~F        Check whether X divides this value. Of course, X divides X so this
          gives X for non-composite X. But X doesn't divide 1 (unless X is 1),
          so we get 0 for composite X. Call this Y.
0         Push a 0.
\         Switch to Ordinal mode.
F         Implicitly convert both to string and check whether Y contains 0.
$/K       If it does, return to the w. Either way, switch back to Cardinal mode.
          Note that the only numbers that get to this point are 1 and prime
          numbers which don't contain 0. It's fine that we let 1 through here,
          because we'll use a proper primality test for the digit-expanded
          version later on.
.!        Store a copy of X on the tape. Let's call the copy that remains on
          the stack Z, which we're now decomposing into digits while expanding
          them.
w         Push the current IP position to the RAS. This marks the beginning
          of an inner loop over the digits of Z.

  .a%       Duplicate Z and retrieve its last digit D by taking Z % 10.
  \./       Duplicate D (in Ordinal mode but that doesn't matter).
  &.        Duplicate D, D times. So we end up with D+1 copies of D.
  ,         Pop the top D and pull up the Dth stack element, which is Z.
  a:        Discard the last digit by taking Z / 10.
  .$K       If Z is zero now, skip the K and end the inner loop, otherwise
            repeat the inner loop.
;         Discard the 0 (what used to be Z).
          We now have D copies of each digit D on the stack, but the digits
          were processed in reverse order, so the last digit is at the bottom.
d&        Repeat the next command once for each stack element.
\*        Concatenate in Ordinal mode. This joins all the digits on the
          stack into a single string.
R         Reverse that string. This is the digit-expanded version of X.
/         Switch back to Cardinal mode.
W         Pop the inner loop's return address from the RAS. We could have done
          this right after the most recent K, but putting it here helps lining
          up the two Ordinal sections in the program layout.
.tzt      Is the digit-expanded number a prime?
$W        If so, we've found an RDP. Pop one copy of the main loop address 
          from the RAS.
g         Recover the current value of X from the top left grid cell.
K         Jump back to the w if any copies of the return address are left 
          on the RAS. Otherwise, we leave the main loop.
/o        Implicitly convert the result to a string and print it in
          Ordinal mode.
          The IP will then bounce off the top right corner and start
          travelling through the program in reverse. Whatever it does
          on the way back is utter nonsense, but it will eventually get
          back to the division (:). The top of the stack will be zero
          at that point and therefore the division terminates the program.
\$\endgroup\$
4
\$\begingroup\$

Python 2, 130 bytes

  • Thanks to ArBo for this four byte shorter solution.
f=lambda n,c=9:n and f(n-(('0'in`c`)<p(c)*p(int("".join(d*int(d)for d in`c`)))),c+1)or~-c
p=lambda n:all(n%m for m in xrange(2,n))

Try it online!


Python 2, 195 179 167 140 138 136 135 134 bytes

  • Saved 27 bytes thanks to ovs; using xrange instead of range, thus circumventing a MemoryError and compacting the prime function; improving integer index counting.
  • Saved two bytes; using binary pipe or operations | to save bytes over or.
  • Saved two bytes; inverting the prime function and doing some further logic manipulation.
  • Saved a byte; using ~- instead of 0** to invert the existence of a zero in j, as & followed by a true boolean isolates this value's boolean property.
  • Saved a byte thanks to Lynn; golfing ~-A&B&C (equivalent to (not A) and B and C) with A, B, C being booleans to A<B==C.
def f(n,j=9,p=lambda n:all(n%j for j in xrange(2,n))):
 while n:j+=1;n-=("0"in`j`)<p(j)==p(int("".join(d*int(d)for d in`j`)))
 print j

Try it online! (1-indexed)

Explanation

Defines a main function f which takes in an integer index, n, and a by default set value j, the current sequence canditate (intitiated to 9 to improve performance whilst keeping program size) and a prime checking function.
As long as n is non-zero, the n-th sequence entry is not yet found. Thus j is incremented and n is decremented by one iff j is a number which satisfies the required properties.
When the loop ends, j is the n-th sequence entry and thus printed.

\$\endgroup\$
  • \$\begingroup\$ I'm a bit late to the party, but you can shave off 4 more bytes \$\endgroup\$ – ArBo Apr 18 at 21:25
  • \$\begingroup\$ @ArBo Thank you. \$\endgroup\$ – Jonathan Frech Apr 19 at 9:22
3
\$\begingroup\$

Pyth, 21 bytes

.f&.AKjZT&P_ss*VK`ZP_

Try it here!

Rather lengthy as Pyth doesn’t have a Decimal Expansion built-in.

  • Take the first N positive integers (.f), that:
    • Have all the digits truthy (.AKjZT), and (&)...
    • The vectorized multiplication of their string representation with their digits (*VK`Z), joined together and converted to an integer (ss) are prime (P_), and (&)...
    • That are primes themselves (P_).
\$\endgroup\$
  • \$\begingroup\$ You can remove e as per a new rule amendment. \$\endgroup\$ – Erik the Outgolfer Nov 28 '17 at 21:26
  • \$\begingroup\$ @EriktheOutgolfer Done, thanks \$\endgroup\$ – Mr. Xcoder Nov 28 '17 at 21:27
2
\$\begingroup\$

Perl 6, 51 bytes

{(grep {!/0/&is-prime $_&S:g/./{$/x$/}/},2..*)[$_]}

Try it online!

  • grep {...}, 2..* filters the infinite sequence of natural numbers starting from 2 using the predicate function between the braces. (...)[$_] indexes into this filtered list using the function's argument $_.
  • !/0/ filters out numbers that contain a zero digit.
  • S:g/./{$/ x $/}/ replicates each digit in the test number's decimal expansion.
  • is-prime $_ & S:g/./{$/ x $/}/ calls the built-in is-prime function with an and-junction of $_, the test number, and the number resulting from replicating its digits. The function will return true if both members of the and-junction are prime.
\$\endgroup\$
2
\$\begingroup\$

J, 81 bytes

f=.[:1&p:(*@(*/)*x:@#~)&.(10&#.inv)
[:{.(4&p:@{.@]([,]+f@[){:@])^:([>{:@])^:_&2 0

This is one of those situations for which I haven't yet found a good J solution.

Nevertheless, I post this in hopes of learning something new.

f tells us if a given number is a "repeated digit prime". It breaks down as follows:

[:1&p:                               is the following a prime?
      (*@                            the signum of...
         (*/)                        the product of the digits
             *                       times...
              x:@                    force extended precision of...
                 #~)                 self-duplicated digits
                    &.               "Under": perform this, then perform its inverse at the end
                      (10&#.inv)     convert to a list of digits

And finally the main Do... While verb, with its pesky, seemingly unavoidable boilerplate, which arises from the fact that we need to use a list to store our progress, which requires both "current prime" and "found so far" registers, since our left argument is already taken to store the stopping condition, ie, n. This means that we must use many precious bytes for the simple task of specifying args ([ and ]) and unpacking our 2 element list ({. and {:):

[:{.                                                take the first element of the final result, of the following Do... While:
    (4&p:@                                          the next prime after...
          {.@                                       the first element of...
             ]                                      the right arg 
                       {:@])                        the last (2nd) elm of the arg...
              ([,]+f@[)                             those two now become the left and right args to this verb...
               [,                                   left arg appended to...
                 ]+                                 right arg plus...
                   f@[                              f of the left arg...
                             ^:(      )^:_          keep doing all that while...
                                [>                  the left is bigger than...
                                  {:@]              the last elm of the right arg
                                          &2 0      seed the process with 2 0, ie,
                                                    the first prime, and 0 rdps found so far.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Is it really fewer bytes to have a helper function? Can't you just replace f with the helper function wrapped in parentheses. Also, I tried my hand at golfing the helper function and came up with 1 p:('x',~"."0#])&.":, which unfortunately doesn't successfully exclude primes with '0' in them. Do you have any thoughts? It also has to have the 'x',~ part to get extra precision ... \$\endgroup\$ – cole Nov 30 '17 at 7:20
  • \$\begingroup\$ @cole yes re: helper function adds a byte, but at this point we are polishing brass on the Titanic, so i figured why bother, just retain the clarity, and maybe miles or FrownyFrog will chime in with an idea that saves real bytes \$\endgroup\$ – Jonah Nov 30 '17 at 14:08
  • \$\begingroup\$ i’ll check out your golfing of the helper function later \$\endgroup\$ – Jonah Nov 30 '17 at 14:09
  • \$\begingroup\$ 57 bytes so far (((0>.-)((*&(1&p:)0&e.|10#.#~),.&.":))([,(+*)~)])/^:_@,&2, use 10x to extend the range otherwise n = 15 will skip 937 \$\endgroup\$ – miles Dec 1 '17 at 1:19
  • \$\begingroup\$ @miles, you are a J god. already found some nice new tricks in here. going to look it over again tomorrow to make sure i understand the iteration / decrementing. I don't know if you noticed the link to my SO question, but would you say this is a general technique that could answer solve the issue I raised there? \$\endgroup\$ – Jonah Dec 1 '17 at 5:02

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.