22
\$\begingroup\$

Given a positive integer as input, output the smallest positive integer such that appending its digits (in base 10) to the end of the input number will form a prime number.

Examples

1     -->   1
2     -->   3
8     -->   3
9     -->   7
11    -->   3
20    -->  11
43    -->   1
134   -->  11
3492  -->  11
3493  -->   9
65595 -->  19

Rules and Scoring

  • This is code golf, so shortest code wins
  • Standard rules and loopholes apply
  • Use any convenient I/O format
  • The largest concatenated number (which is larger than both the input and output) your solution supports must be at least \$2^{53} - 1\$. (This is the largest odd integer that can be represented with double precision floats)
  • Leading zeros should not be added to numbers before appending them to the input number
  • Primality tests must be exact
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Math question: is there a guarantee that such an integer always exists? Are there interesting test cases where the first such integer is huge? \$\endgroup\$
    – quarague
    Apr 16, 2021 at 8:48
  • 3
    \$\begingroup\$ @quarague: Yes, but I'm not sure it's guaranteed to fit in a double precision float. This topic has been covered on Math.SE at math.stackexchange.com/q/60825/3862 . \$\endgroup\$
    – Brian
    Apr 16, 2021 at 14:36
  • \$\begingroup\$ There's something that I cannot understand about this site, and I am honestly confused. There has been some discussion about discouraging challenges that focus on prime numbers, and oftentimes they are treated as such. But sometimes they are not. Is there any consensus or clear rules about this? \$\endgroup\$ Apr 17, 2021 at 21:35
  • 2
    \$\begingroup\$ @polfosolఠ_ఠ: In most languages (without a prime-check builtin), yes, there might be less code required that's not unique to this challenge if it had been "make it square" instead of "make it prime". (Specifically square is simple enough that it might open up algorithms other than brute-force trial and error, IDK. Mathematically, we're doing x * 10^n + m when we append base-10 digits.) Or maybe "make it a multiple of 7" or "11" or something is easier to test without sqrt functions, just a single modulo, so simplifies brute-force and is even more likely to allow some neat math. \$\endgroup\$ Apr 17, 2021 at 22:39

22 Answers 22

10
\$\begingroup\$

Jelly, 7 bytes

1ṭVẒɗ1#

Try it online!

How it works

1ṭVẒɗ1# - Main link. Takes n on the left
    ɗ   - Define a dyad f(k, n) from the previous 3 links:
 ṭ      -   Tack; Yield [n, k]
  V     -   Eval; Smash together into a single integer
   Ẓ    -   Is prime?
1    1# - Starting from k = 1, find the first k such that f(k, n) is true
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6),  51  50 bytes

Saved 1 byte thanks to @l4m2

Expects the input number as a string.

f=(n,k)=>eval('for(d=x=n+k;x%--d;)d')<3?k:f(n,-~k)

Try it online!

\$\endgroup\$
1
  • 6
    \$\begingroup\$ 50 \$\endgroup\$
    – l4m2
    Apr 15, 2021 at 15:36
5
\$\begingroup\$

05AB1E, 5 bytes

05AB1E treating strings and integers equal helps again.

∞.Δ«p

Try it online! or Try all cases

∞      # in the list of positive integers
 .Δ    # find the first one
   «   # that, when concatenated to the input,
    p  # is a prime number
\$\endgroup\$
2
  • \$\begingroup\$ Ah, you got there a second before I did, +1! \$\endgroup\$ Apr 15, 2021 at 15:26
  • \$\begingroup\$ Same here. Why do I always get ninja'd... :/ \$\endgroup\$
    – Makonede
    Apr 15, 2021 at 15:59
4
\$\begingroup\$

Brachylog, 5 bytes

;.cṗ>

Try it online!

,.ṗ> seems like it should work, but , seems to be somewhat bugged with unbound variables. It's a bit hard to tell why.

;.c      The input's concatenation with the output
   ṗ     is a prime number
    >    greater than the output.

Uses > rather than so as to force the output to be an integer--otherwise, it would be an empty list for prime inputs.

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

Husk, 9 8 bytes

Saved 1 byte thanks to Leo

ḟöṗr+⁰s1

Try it online!

Explanation:

ḟöṗr+⁰s
ḟ         Find first number at least
       1  1 such that
      s   when it's converted to a string,
    +⁰    and appended to the input
   r      and read as an integer,
  ṗ       the result is prime
\$\endgroup\$
2
  • \$\begingroup\$ No need to flip , just pass its argument in the right order: Try it online! \$\endgroup\$
    – Leo
    Apr 16, 2021 at 0:58
  • \$\begingroup\$ @Leo Thanks, I didn't realize that! I think I originally tried doing it without superscript 0 and left it in. \$\endgroup\$
    – user
    Apr 16, 2021 at 1:56
4
\$\begingroup\$

R, 64 62 61 60 bytes

function(n){while(sum(!(x=n*10^nchar(+F)+F)%%1:x)>2)F=F+1;F}

Try it online!

-1 byte thanks to @Dominic's idea and then another one (in both versions).

R, 60 59 bytes

function(n){while(sum(!(x=n*10^nchar(F)+F)%%1:x)>2)F=F+1;F}

Try it online!

Slower version from @Dominic.

Abuses the fact that n*10^5 will never be prime (but checks it in the first iteration, that's why it's so slow).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Much slower, but 2 bytes shorter: try it... \$\endgroup\$ Apr 16, 2021 at 22:06
  • 1
    \$\begingroup\$ -1 byte from both versions by exchanging '<-' for '='. \$\endgroup\$ Apr 19, 2021 at 20:08
3
\$\begingroup\$

Stax, 8 bytes

É3º╩(\╝░

Run and debug it

Explanation

wi;i\$e|p!
w          while
   |p! end result is not prime, do:
 i          push index
  ;i        push input and index again
\$      stringify
      e     convert to int
           final index is implicitly output
\$\endgroup\$
3
\$\begingroup\$

Japt, 8 bytes

ÈsiU j}a

Try it

ÈsiU j}a     :Implicit input of integer U
È            :Function taking an integer as an argument
 s           :  Convert to string
  iU         :  Prepend U and convert back
     j       :  Is prime?
      }      :End function
       a     :Get the first integer >=0 that returns true
\$\endgroup\$
2
\$\begingroup\$

Python 3, 82 bytes

def x(n,i=1):k=int(f"{n}{i}");return all(k%j for j in range(2,k))and i or x(n,i+1)

Try it online!

-30 bytes thanks to @Manish Kundu, @MarcMush and @ophact

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

J, 22 bytes

>:@]^:(0 p:,&.":)^:_&1

Try it online!

Increment counter >:@] while ^:_ original number catted with counter ,&.": is not prime 0 p:, with counter starting at 1 &1.

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

Pyth, 6 bytes

fP_s+z

Test suite

Fairly different approach to the existing Pyth answer.

Explanation:

fP_s+z  | Full code
fP_s+zT | with implicit variables
--------+-----------------------------------
f       | first positive integer T such that
    +zT | input and T concatenated
   s    | as an integer
 P_     | is prime
\$\endgroup\$
2
\$\begingroup\$

Ruby, 58 bytes

->n,r=1{(2...x=([n,r]*'').to_i).any?{|c|x%c<1}?f[n,r+1]:r}

Try it online!

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

Lyxal, 7 bytes

≬?pæṅJṅ

Try it Online!

Uses magic. -1 thanks to @vyxal.

\$\endgroup\$
4
  • \$\begingroup\$ Using the implicit range was smart considering the added digits never seem to surpass the input digit. \$\endgroup\$
    – Underslash
    Aug 4, 2021 at 10:54
  • \$\begingroup\$ 7 bytes \$\endgroup\$
    – lyxal
    Aug 4, 2021 at 10:54
  • \$\begingroup\$ @vyxal It's quite nice how you're using both overloads of . Thanks! \$\endgroup\$
    – emanresu A
    Aug 4, 2021 at 10:55
  • \$\begingroup\$ This is the reason I changed my username...just for this joke \$\endgroup\$
    – lyxal
    Aug 4, 2021 at 10:57
1
\$\begingroup\$

Julia 0.4, 39 bytes

with julia 0.4 for isprime and parse

>(x,n=1)=isprime(parse("$x$n"))?n:x>n+1

Try it online!

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

JavaScript, 65 bytes

f=(n,x=1)=>[...Array((i=n+x)-2)].every((_,e)=>i%(e+2))?x:f(n,x+1)

Feel like this is way too long for some reason. I'm not very good at primality testing, so that takes up the vast majority of my code. Basically checks if every number between 2 and n+[x] [the number with x appended at the end] yields a nonzero remainder when it divides i [n+[x]]. If so, return x, otherwise call f again.

-4 bytes thanks to @Arnauld.

saved 2 more bytes by taking the input number as a string.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ ''+n+x can be turned into n+[x]. [...Array(X).keys()].every(e=> can be turned into [...Array(X)].every((_,e)=>. \$\endgroup\$
    – Arnauld
    Apr 15, 2021 at 15:36
  • \$\begingroup\$ @Arnauld thanks for all the suggestions, I'll try to remember them when I answer in the future. I'm not a very good golfer (I'm ready to admit that) \$\endgroup\$
    – user100690
    Apr 15, 2021 at 15:38
  • \$\begingroup\$ You can save a few more bytes by doing it that way. \$\endgroup\$
    – Arnauld
    Apr 15, 2021 at 15:55
  • \$\begingroup\$ You can save another byte by using %~-~e instead of %(e+2). (But that's still longer than my last suggestion, which would be 61 bytes with a string as input.) \$\endgroup\$
    – Arnauld
    Apr 16, 2021 at 9:30
1
\$\begingroup\$

Pyth, 13 bytes

W!P_s+z=+Z1;Z

Try it online!

Explanation

Z     # Set to 0 by default
z     # Input, taken as a string
=Z+Z1 # Increment Z by 1 and assign Z to it
s+z   # Concatenate z with and convert to integer
W!P_  # While it is not prime
;Z    # Print Z after the while loop finishes

thanks Citty for -1 byte

\$\endgroup\$
1
  • \$\begingroup\$ -1 byte: W!P_s+z=+Z1;Z \$\endgroup\$
    – Citty
    Apr 15, 2021 at 16:05
1
\$\begingroup\$

Wolfram Language (Mathematica), 48 bytes

(k=0;While[!PrimeQ[10^⌊Log10@++k+1⌋#+k]];k)&

Increasing k until n*floor(10^(Log10(k)+1)+k) is prime
Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 44 bytes with ReplaceRepeated, or 46 with For \$\endgroup\$
    – att
    Apr 15, 2021 at 20:14
1
\$\begingroup\$

Python 3.8, 80 bytes

f=lambda n,a=0:math.perm(p:=int(n+str(a)))**2%-~p<1and f(n,a+1)or-~a
import math

Try it online!

Inputs \$n\$ as a string and returns the smallest positive integer that makes a prime when appended to \$n\$.

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

Retina, 53 bytes

.+
_;$&;_10**
+`((.+;).+);(__+)\3+$
_$1;$($1$.2)*
\G_

Try it online! Link includes less slower test cases. Explanation:

.+
_;$&;_10**

Create a working area with the suffix in unary (initially 1), the input prefix, and the current resulting integer in unary (initially one more than ten times the input).

((.+;).+);(__+)\3+$

Match the suffix and prefix, the prefix, and a factor of the resulting integer.

_$1;$($1$.2)*

Increment the suffix, keeping the prefix, and calculate the new integer. $1 actually contains the unary suffix as well as the prefix, but Retina's * operator only considers the numeric portion of the parameter. Additionally, the separator is included in the capture of the suffix, thus automatically incrementing it when its length is taken.

+`

Repeatedly increment the suffix until a prime number is found.

\G_

Convert the suffix to decimal.

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

Perl 5, 54 bytes

sub{$i=pop;$n=1;$n++while(1x"$i$n")=~/^(11+?)\1+$/;$n}

Try it online!

Perl 5, 65 bytes

A slightly different approach, but 11 bytes longer:

sub f{($i,$t)=@_;!$t||(grep"$i$t"%$_<1,2..$i.$t-1)?f($i,$t+1):$t}

Try it online!

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

Python 2, 73 bytes

def f(n,x=1):k=int(n+`x`);return all(k%i for i in range(2,k))or-~f(n,x+1)

Takes input as a string (e.g. f("65595"))

Thanks to ovs

\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte by returning 1 instead of x if you find a prime, and increment on every recursive call: tio.run/… \$\endgroup\$
    – ovs
    Aug 4, 2021 at 12:33
0
\$\begingroup\$

Raku, 28 bytes

{first ($_~*).is-prime,1..*}

Try it online!

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