20
\$\begingroup\$

Given 2 non-negative integers as input, output a non-negative integer that cannot be created through any mathematical operators on the 2 inputs.

For example, given inputs 2 and 3, 6, 0, 5, 1, 9, 8, 23, 2 are all invalid outputs.

Operations that must be taken into account are:

Addition        (a + b)
Subtraction     (a - b) and (b - a)
Multiplication  (a * b)
Division        (a / b) and (b / a)
Modulus         (a % b) and (b % a)
Exponentiation  (a ** b) and (b ** a)
Bitwise OR      (a | b)
Bitwise XOR     (a ^ b)
Bitwise AND     (a & b)
Concatenation   (a.toString() + b.toString()) and (b.toString() + a.toString())

In cases where an operation would lead to a non-integer (such as 2 / 3), always floor. So 2 / 3 = 0

Assume any invalid operations (such as dividing by 0) result in 0.

Input

2 non-negative integers.

Standard I/O methods are accepted

You can assume the input will always be within a handleable range for your given language, however remember standard loopholes still apply.

Output

Any non-negative integer that can not be created via any of the above operations on the 2 inputs.

Testcases

Input  -> Invalid outputs
2, 3   -> 0, 1, 2, 3, 5, 6, 8, 9, 23, 32
0, 0   -> 0
17, 46 -> 0, 2, 12, 17, 29, 63, 782, 1746, 4617, 18487710785295216663082172416, 398703807810572411498315063055075847178723756123452198369
6, 6   -> 0, 1, 6, 12, 36, 66, 46656
1, 1   -> 0, 1, 2, 11

Scoring

This is so fewest bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Skidsdev May 24 '17 at 14:20
  • \$\begingroup\$ I think the one way to solve this is to find some prime number that is larger than (a+b) \$\endgroup\$ – Dead Possum May 24 '17 at 14:22
  • 1
    \$\begingroup\$ @DeadPossum would definitely be a valid solution, although perhaps not the only, or golfiest ;) \$\endgroup\$ – Skidsdev May 24 '17 at 14:23
  • \$\begingroup\$ I bet that there is some fancy language that can do it in couple bytes :D \$\endgroup\$ – Dead Possum May 24 '17 at 14:24
  • 15
    \$\begingroup\$ Unrelated \$\endgroup\$ – HyperNeutrino May 24 '17 at 14:24

18 Answers 18

20
\$\begingroup\$

Retina, 3 bytes

.
1

Try it online!

Takes inputs separated by space (or any single non-newline character)

Replaces all digits with 1, and joins the resulting numbers with another 1.

Proof of correctness

Courtesy of Martin Ender

\$\endgroup\$
  • \$\begingroup\$ technically this isn't joining the resulting numbers with another 1, it's simply taking input as a string of 2 space-separated numbers, and replacing every character with a 1. But that being said I can't find any examples that prove you wrong... yet \$\endgroup\$ – Skidsdev May 24 '17 at 16:07
  • \$\begingroup\$ @Mayube of course it does, and as such it could work with any string, not only one composed by two numbers separated by a single space. My explanation is in terms of the "two input numbers" abstraction. \$\endgroup\$ – Leo May 24 '17 at 16:15
  • 2
    \$\begingroup\$ "It is know [sic] [...] that a repunit in base 10 cannot [...] be a perfect power." No operation in the given list other than exponentiation can result in more digits than the total number of input digits, so this should be valid. \$\endgroup\$ – Martin Ender May 24 '17 at 17:29
  • \$\begingroup\$ You cheeky bugger! +1 \$\endgroup\$ – Nic Hartley May 24 '17 at 18:12
  • \$\begingroup\$ Works in QuadR too! \$\endgroup\$ – Adám Jun 27 '17 at 10:32
11
\$\begingroup\$

Jelly, 3 bytes

+Æn

Try it online!

Explanation:

+Æn Arguments: x, y
+                            x + y.
 Æn Find a prime larger than
\$\endgroup\$
  • \$\begingroup\$ I think this is valid... \$\endgroup\$ – Erik the Outgolfer May 24 '17 at 14:25
  • \$\begingroup\$ I assume this sums the input and outputs the first prime greater than the sum? \$\endgroup\$ – Skidsdev May 24 '17 at 14:25
  • 1
    \$\begingroup\$ @DeadPossum I was about to write one. Hope I golfed it well. \$\endgroup\$ – Erik the Outgolfer May 24 '17 at 14:33
  • 1
    \$\begingroup\$ Bertrand's postulate should be almost good enough to prove concatenation works. Concatenating with the smaller number b on the right we have a..b >= 10a > 4a > 2(a + b), and concatenating with the smaller number b on the left we have b..a > (b+1)a. The only non-small interesting case here should be b = 1, where we have 1..a > 2a = 2(a + b) - 2. The place where this bound is the tightest is for a = 9....9. This is the only non-small case which might be a problem for Bertrand's postulate. However, there are better results like mathoverflow.net/questions/2724 \$\endgroup\$ – tehtmi May 25 '17 at 4:17
  • 1
    \$\begingroup\$ I guess there's a version of Bertrand's postulate the proves n < p < 2n - 2 which should work for everything. I was thinking n < p < 2n. \$\endgroup\$ – tehtmi May 25 '17 at 9:37
9
\$\begingroup\$

Python 2, 8 bytes

'1'.join

Try it online!

Takes a list of two number strings as inputs, outputs a single number string. Concatenates the numbers with a 1 in the middle.

The result has too many digits for anything but exponent. Note that the output for (x,y) has one more digit than x and y combined, unless x or y is 0. For exponent, we check we check that this means x**y never matches.

  • If x is 0 or 1, then so is x**y, which is too small
  • If y<=1, then x**y<=x is too small
  • If y==2, then x**2 must have two more digits than x. This happens up to x=316, and we can check none of those work.
  • If y==3, then x**3 must have two more digits than x. This happens up to x=21. We can check that none of those work.
  • If 3<y<13, then x**y quickly gets too long. It only plausible has the right number of digits for x<=25, and we can check these.
  • If y>=14, then x**y is too long even for the smallest possible x==2.
\$\endgroup\$
7
\$\begingroup\$

CJam (7 chars)

{+))m!}

This creates a number (a+b+2)! which is larger than the largest related number in almost all cases.

It's fairly obvious that the largest related number must be one of a ** b, b ** a, concat(a, b), concat(b, a).

If we consider logarithms, we find that

  • log(a ** b) = b log a
  • log(concat(a, b)) ~= (log a) + log (b)
  • log((a + b + 2)!) ~= (a + b + 2) log (a + b + 2) - (a + b + 2)

Thus asymptotically it's larger, and we only need to worry about a few small cases. In fact, the only case for which the value output is not larger than all related numbers is 0, 1 (or 1, 0), for which it gives 6 and the largest related number is 10.

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

JavaScript (ES6), 15 bytes

Takes input in currying syntax.

a=>b=>a*a+b*b+2

a² + b² + 1 would fail for many entries such as 3² + 5² + 1 = 35 or 7² + 26² + 1 = 726 (concatenation). a² + b² + 2 should be safe. This was exhaustively tested for 0 ≤ a ≤ b ≤ 50000.

Demo

let f =

a=>b=>a*a+b*b+2

for(a = 0; a < 5; a++) {
  for(b = a; b < 5; b++) {
    console.log(a, b, f(a)(b));
  }
}

for(i = 0; i < 10; i++) {
  a = Math.random() * 1000 | 0;
  b = Math.random() * 1000 | 0;
  console.log(a, b, f(a)(b));
}

\$\endgroup\$
  • 1
    \$\begingroup\$ This should be safe from concatenation. Let b be the number concatenated on the right. Fixing b, we can solve a quadratic equation for a: a^2 + b^2 + 2 - 10^k * a - b = 0. The discriminant of the quadratic must be a perfect square for this equation to have an integer solution. The discriminant is 10^2k - 4(b^2 - b + 2) = 10^2k - (2b - 1)^2 - 7. Consider modulo 9. k doesn't matter and we never get a quadratic residue for any b. \$\endgroup\$ – tehtmi May 25 '17 at 7:39
3
\$\begingroup\$

Python, 115 95 79 bytes

Stupid straightforward solution. Feel free to outgolf me.

x,y=input()
f=lambda x,y:[x+y,x*y,x**y,int(`x`+`y`)]
print max(f(x,y)+f(y,x))+1

+12 bytes because of stupid x/0.
-20 bytes thanks to @RobinJames
-16 bytes thanks to @tehtmi

\$\endgroup\$
  • \$\begingroup\$ x/y if y else 0 will be less than or equal x*y for x,y non-negative so I think you can have those 12 bytes back plus another 3 \$\endgroup\$ – Robin James May 24 '17 at 23:27
  • \$\begingroup\$ @RobinJames Ah yes, I'm dumb. Thanks. \$\endgroup\$ – HyperNeutrino May 25 '17 at 2:17
  • 1
    \$\begingroup\$ I think you should be able to remove more cases: 1) x - y <= x <= x +y; 2) x%y <= y <= x + y; 3,4,5) x | y = x ^ y + x & y <= x ^ y + 2*(x & y) = x + y. (For that last one, XOR is like add without carry, and AND is finding the bits that would carry. OR is taking (1, 1) -> 1 instead of (1,1) -> 2 like in real addition.) \$\endgroup\$ – tehtmi May 25 '17 at 8:41
2
\$\begingroup\$

Python, 27 bytes

lambda a,b:(a+b+9)**(a+b+9)

Outputs a number larger than all the related numbers.

Try it online!

-1 byte thanks to Kevin Cruijssen.
-2 bytes thanks to Dead Possum.

\$\endgroup\$
  • \$\begingroup\$ Your TIO-link is empty. Also, I think you can remove the space after : if I'm not mistaken. \$\endgroup\$ – Kevin Cruijssen May 24 '17 at 14:51
  • \$\begingroup\$ @KevinCruijssen Whoops, fixed that, thanks! \$\endgroup\$ – Ankoganit May 24 '17 at 14:53
  • \$\begingroup\$ You can remove f= - unnamed lambda is acceptable \$\endgroup\$ – Dead Possum May 24 '17 at 14:57
  • \$\begingroup\$ @DeadPossum Didn't know that, thanks! \$\endgroup\$ – Ankoganit May 24 '17 at 15:00
  • \$\begingroup\$ You could probably do with getting rid of at least one of the two nines (and the corresponding +), but I'm not totally sure. \$\endgroup\$ – Theo May 24 '17 at 15:05
2
\$\begingroup\$

Python 2, 25 bytes

lambda x,y:int(`x`+`y`)+3

Concatenates and adds 3

Try it online

\$\endgroup\$
  • \$\begingroup\$ Does this work if x and y are both 3? \$\endgroup\$ – Robert Benson May 24 '17 at 15:05
  • \$\begingroup\$ @RobertBenson Should do, afaik you can't make 36 from 3 and 3 \$\endgroup\$ – Skidsdev May 24 '17 at 15:07
  • \$\begingroup\$ This seems probably okay to me. The reverse concatenation must have a different residue modulo 9. For exponentiation, there are only a finite number of cases to consider before the result of the exponentiation has too many digits along the lines of xnor's Python answer. I didn't see any conflicts (neither for +1, although +2 has 2**6 = 62 + 2). \$\endgroup\$ – tehtmi May 25 '17 at 8:13
  • \$\begingroup\$ @tehtmi +1 fails on x=y=0 The try it online link tests for all combinations of x and y in the range [0,400] \$\endgroup\$ – TFeld May 26 '17 at 7:01
2
\$\begingroup\$

JS (ES6), 12 bytes

x=>x.join`1`

Same algorithm as this python answer. Takes input as an array of ints.

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

Braingolf, 4 bytes

9&+^

Try it online! (Header & Footer are Interpreter, code is actual braingolf code, args are inputs)

Outputs (a+b+9)**(a+b+9)

From my testing I couldn't find any pairs that this doesn't work on.

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

Python 2, 19 bytes

lambda x,y:x+9<<y+9

Try it online!

I'm pretty sure the bit shift works for all cases, but I'm not 100% on it. Anyway, it saves a few bytes over the exponentiation version.

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

J, 5 bytes

Just a translation of Jelly.

4 p:+

Try it online!

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

APL (Dyalog), 4 bytes

Algorithm taken from here.

!2++

Try it online!

! factorial of

2+¨ two plus

+ the sum

Works in J too.

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

QBIC, 8 bytes

Man, so many cool ways to just take these numbers and get an unrelated number. I just had to try a few, to see how QBIC'd keep up. The shortest one is a port of xnor's Python answer, concatenating the numbers with a 1 in the middle:

?;+@1`+;

All ones, a port of Leo's Retina answer:

[0,_l;|+_l;||Z=Z+@1

Finding the next bigger prime:

c=:+:+1≈µc|+1|c=c+1]?c
\$\endgroup\$
1
\$\begingroup\$

sed, 6 bytes

s/ /1/

Try it online!

Input is via stdin in the form "x y", output is to stdout.

Port of this python answer, which includes the proof of correctness. Many thanks to xnor for such a simple method.

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

Java 8, 15 bytes

a->b->a*a+b*b+2

Port from @Arnauld's amazing JavaScript (ES6) answer.
Try it here.

Straight-forward approach (177 170 bytes):

a->b->{int r=1;for(;a+b==r|a-b==r|a*b==r|(b>0?a/b==r|a%b==r:0>1)|Math.pow(a,b)==r|(a|b)==r|(a^b)==r|(a&b)==r|new Integer(""+a+b)==r|new Integer(""+b+a)==r;r++);return r;}

Try it here.

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

05AB1E, 2 4 bytes

+ØDm

Try it online!

Same as the Jelly answer, finds a prime after the sum. One byte shorter :)

EDIT: Now raises it to its own power to suffice for the exception.

\$\endgroup\$
  • \$\begingroup\$ Not the same algorithm actually, this finds a+b'th prime, while mine finds the smallest prime larger than a+b. \$\endgroup\$ – Erik the Outgolfer May 24 '17 at 18:59
  • \$\begingroup\$ Either way, it should work. \$\endgroup\$ – Neil A. May 24 '17 at 19:30
  • 3
    \$\begingroup\$ Fails for 6443, 3 (which gives prime 64433, the concatenation). \$\endgroup\$ – tehtmi May 25 '17 at 4:30
  • \$\begingroup\$ @tehtmi is correct, this fails. \$\endgroup\$ – Skidsdev May 25 '17 at 7:46
  • \$\begingroup\$ See my edit, should work now \$\endgroup\$ – Neil A. May 26 '17 at 9:50
1
\$\begingroup\$

Brachylog, 3 bytes

+<ṗ

Try it online!

Nothing new here.

       The output
  ṗ    is a prime number
 <     which is strictly greater than
+      the sum of the elements of
       the input.

Now, to figure out how to find an unrelated string...

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