6
\$\begingroup\$

Inspired by: Find an Unrelated Number


Challenge

Given two positive integers as input, output the mathematical operations that can be used on those inputs to generate every number from 1 to n inclusive where n is the smallest prime greater than the sum of the two inputs. If the number cannot be generated using the list of mathematical operations below, the output for that number should indicate that it is "unrelated".

For example, for the inputs 2 and 3, n=7 so one valid output would be
Subtraction, Modulus, Bitwise OR, Unrelated, Addition, Multiplication, Unrelated
(see Output section below for clarification on valid outputs)

(If Erik the Outgolfer's answer is valid, the last term will always be unrelated.)

Operations that must be considered 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)
Bitwise OR      (a | b)
Bitwise XOR     (a ^ b)
Bitwise AND     (a & b)

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

Exponentiation is not included because it is never required. a**b and b**a will always be larger than 2(a+b)-2 (which is (probably) the largest possible n) except for the cases a=1|b=1 or a=b=2. The cases a=b=1 and a=b=2 have valid solutions that do not use exponents: * and /|U+U, respectively. For the rest of the cases where a=1,b>1, a**b=1 which can also be found with a%b and b**a=b which can also be found with b*a.

Concatenation is not included because it was shown to always be larger than n.

Input

2 positive integers.
Standard I/O methods are accepted. Standard loopholes are forbidden.
You can assume the input will always be within a valid range for your given language.

Output

A list or array of the mathematical operations that can be used with the inputs to generate every number from 1 to n inclusive where n is the smallest prime larger than the sum of the two inputs. (You do not need to output the value of n.)

Output can be in any format valid for your language so long as it is clearly understood. For instance, it can be an array where each value is a separate operation, a string with a delimiter between each value, or even just a solid string where each character is a different value.

You can use any character(s) so long as each possible result has a unique representation. For instance, +-*/%|^&U will work and so will 123456789, UNRELATID, and CODEgolf!. You are advised to include a legend or explanation of how the output can be read.

If more than one operation can be used to generate a given number, you may output any one of them. Do not output all of them.

Testcases

Input  |   n  |   Example Valid Output
-----------------------------------------
2, 3   |   7  |   Subtraction, Modulus, Bitwise OR, Unrelated, Addition, Multiplication, Unrelated
2, 3   |   7  |   -%|U+*U
2, 3   |   7  |   2579139
1, 1   |   3  |   [*,+,U]
6, 6   |  13  |   ["/","U","U","U","U","&","U","U","U","U","U","+","U"]
6,12   |  19  |   U/U&U-UUU^UUU|UUU+U
12,6   |  19  |   U/U&U-UUU^UUU|UUU+U
7,11   |  19  |   /U&-UU%UUUU^UU|UU+U
7,15   |  23  |   %/UUUU%-UUUUUU|UUUUUU+U  (2nd value is a floor divide)

(I can easily add more test cases if someone finds an interesting one.)

I think the test case outputs are all valid but I've been known to mistakes. Please tell me if you spot one.

Scoring

This is so fewest bytes wins!

\$\endgroup\$
  • \$\begingroup\$ That last one makes this a lot harder \$\endgroup\$ – Cyoce May 24 '17 at 20:38
  • \$\begingroup\$ @Cyoce By "the last one", do you mean Do not output all of them. ? \$\endgroup\$ – Engineer Toast May 24 '17 at 20:47
  • 2
    \$\begingroup\$ Maybe just remove that operator, then. \$\endgroup\$ – mbomb007 May 24 '17 at 21:03
  • 2
    \$\begingroup\$ Say a = 1, b = 5. Then exponentiation is needed to make 1. \$\endgroup\$ – isaacg May 24 '17 at 21:54
  • 5
    \$\begingroup\$ I think I've proven that the concatenation must be greater than the prime, unless I made an error: pastebin.com/EsR9AXNr \$\endgroup\$ – faubi May 24 '17 at 23:24
2
\$\begingroup\$

Jelly, 52 49 35 bytes

:;%;ạ;+;×;|;^;&;:@;%@
³çi
+ÆnRç@€%8

Try it online!

Explanation

:;%;ạ;+;×;|;^;&;:@;%@ - helper link 0, finds related numbers
:;%;ạ;+;×;|;^;&;:@;%@ - just lists all of the operations, separated by
                         `;` which appends each result to the previous
                         results. Uses `@` to reverse args on : and %

³çi                   - helper link 1, saves a byte in control flow
 ç                    - helper link 0, called on
³                     - first program input and
                         (implicit) second program input
   i                  - find the index of the input whole number in
                         the output list from helper link 0
+ÆnRç@€%8
+Æn                   - find the nearest prime greater than the sum
   R                  - all whole numbers less than or equal to the prime
    ç@€               - for each whole number, call helper link 1 
                         with first argument second program input and
                         second argument the whole number
       %8             - modulo 8 each index: Maps the reversed argument
                         functions to the non-reversed functions
\$\endgroup\$
  • \$\begingroup\$ I think your TIO header has the letter O instead of the number 0 for Unrelated but the output seems correct. \$\endgroup\$ – Engineer Toast May 25 '17 at 7:07
5
\$\begingroup\$

JavaScript (ES6), 134 bytes

(a,b)=>eval("for(t=a+b,i=0;i=i<t;)for(++t;t%++i;);for(q=n='';n++<t;)[...'+-*/%^&|>'].every(o=>n^eval(a+(p=o)+b)&&n^eval(b+o+a)),q+=p")

Using the standard symbols for operations in JavaScript, except for unrelated that is >

Less golfed

(a,b)=>
{
  // find the smallest prime greater than the sum of a and b
  for (t = a + b, i = 0; i < t; )
    for(i=1, ++t; t % ++i; );

  // loop from 1 to t
  // accumulate output in q
  for(q='', n = 0; n++ < t; )
  {
    // try all binary operators
    // to avoid error in 'eval', I need a binary operator for 'unrelated', so I choose '>'
    [...'+-*/%^&|>'].every( // every terminates early if the result is false
      o => (
        p = o,
        n ^ eval(a+o+b) && n ^ eval(b+o+a)
      )
      // using xor to check for equality, the result is cast to integer
      // eventually flooring the division result
    )
    q += p
  }
  return q
}

Test

F=
(a,b)=>eval("for(t=a+b,i=0;i=i<t;)for(++t;t%++i;);for(q=n='';n++<t;)[...'+-*/%^&|>'].every(o=>n^eval(a+(p=o)+b)&&n^eval(b+o+a)),q+=p")

console.log(2,3,F(2,3))
console.log(1,1,F(1,1))
console.log(6,6,F(6,6))
console.log(6,12,F(6,12))
console.log(7,15,F(7,15))

\$\endgroup\$
  • \$\begingroup\$ nice use of every \$\endgroup\$ – Octopus May 25 '17 at 18:55
3
\$\begingroup\$

Ruby, 131 129+7 = 138 135 bytes

Uses the -rprime flag.

C for concatenation and U for unrelated.

->a,b{(1..Prime.find{|i|i>a+b}).map{|i|("C+-*/%|^&".chars+["**",""]).find{|o|o.tr!?C,'';eval([a,b]*o)==i||eval([b,a]*o)==i}||?U}}

Try it online!

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

Jelly, 37 bytes

⁾ðɓ;@€”⁹;€“+ạ×d|^&”j”,¤v€⁸F
+Æni@€¢%8

Try it online! (footer formats the output from the native list of numbers to print a representation using the operation symbols from the question)

How?

Ignores checking of string concatenation and exponentiation as they are unnecessary.

Creates two (similar) links of Jelly code and evaluates them to evaluate to find the values of applying each of the 9 dyadic operations with the arguments in both orders. Flattens this into a single list and finds the index at which each value in the range [1,p] is first found, or 0. Takes the result modulo 8 to collapse the two values for each of reversed subtraction, reversed div and reversed mod to a single values.

⁾ðɓ;@€”⁹;€“+_×d|^&”j”,¤v€⁸F - Link 1: evaluate all operations: number a, number b
⁾ðɓ                         - literal "ðɓ"
      ”⁹                    - literal '⁹'
   ;@€                      - concatenate for €ach -> ["⁹ð","⁹ɓ"]
                      ¤     - nilad followed by link(s) as a nilad:
          “+_×d|^&”         -   literal "+_×d|^&"
                    ”,      -   literal ','
                   j        -   join -> "+,_,×,d,|,^,&"
        ;€                  - concatenate for €ach -> ["⁹ð+,_,×,d,|,^,&","⁹ɓ+,_,×,d,|,^,&"]
                         ⁸  - link's left argument, a
                       v€   - evaluate €ach with argument a:
                            - 1 ⁹ð+,_,×,d,|,^,&
                            -   ⁹               - right argument, b
                            -    ð              - dyadic chain separation
                            -      , , , , , ,  - pair results (yields a list like [[[[[[a+b,aạb],a×b],adb],a|b],a^b],a&b])
                            -     +             - addition
                            -       _           - subtraction
                            -         ×         - multiplication
                            -           d       - divmod (returns a pair of values)
                            -             |     - bitwise-or
                            -               ^   - bitwise-xor
                            -                 & - bitwise-and
                            -
                            - 2 ⁹ɓ+,_,×,d,|,^,& - just like above except:
                            -    ɓ              - dyadic chain separation
                            -                   - ...with argument reversal
                            -
                          F - flatten the two into one list

+Æni@€¢%8 - Main link: number a, number b
+         - addition -> a+b
 Æn       - next prime
      ¢   - call last link (1) as a dyad -> Link(1)(a, b) = [b+a,b-a,b*a,b/a,b%a,b|a,b^a,b&a,a+b,a-b,a*b,a/b,a%b,a|b,a^b,a&b]
   i@€    - first index for €ach (e.g. if a=8, b=3 and n=5 the first index of 5 is 10, a-b)
       %8 - modulo 8             (... 10%8 = 2, aligning with b-a. Same goes for / and %)
\$\endgroup\$
2
\$\begingroup\$

Haskell, 163 162 bytes

import Data.Bits
f a b=[last$0:[n|(n,(#))<-zip[1..][(+),(-),(*),div,mod,(^),(.|.),(.&.),xor],a#b==c||b#a==c]|c<-[1..head[p|p<-[a+b+1..],all((>0).mod p)[2..p-1]]]]

Output is given as a list of integers, which correspond to operations as follows:

0 = Unrelated
1 = Addition
2 = Subtraction
3 = Multiplication
4 = Division
5 = Modulo
6 = Exponentiation
7 = Bitwise OR
8 = Bitwise AND
9 = Bitwise XOR

It will never output concatenation, since I've proven that it will never occur.

-1 byte by replacing /= with > in the primality test.

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

Python 2, 175 173 172 bytes

This doesn't handle exponentiation or concatenation, because I don't think there will ever be a case where they are necessary. `a`+`b` should always be greater than n. Same with a**b. If someone proves this one way or another, let me know.

a,b=input()
n=a+b+1
while 0 in[n%m for m in range(2,n)]:n+=1
for i in range(n):
 for o in'+-*/%|^&':
    x='a'+o+'b==i+1'
    if eval(x)+eval(x[::-1]):print o;break
 else:print 0

Try it online

Prints the operator for a solution, or 0 if unrelated.

\$\endgroup\$
  • \$\begingroup\$ while 0 in[n%m for m in range(2,n))]:n+=1 should save one byte \$\endgroup\$ – PattuX May 24 '17 at 23:01
  • \$\begingroup\$ @PattuX Clever, but it's the same length. \$\endgroup\$ – mbomb007 May 26 '17 at 2:42
  • \$\begingroup\$ The additional 0 in is 4 bytes while removing all and <1 removes 5 bytes. \$\endgroup\$ – PattuX May 26 '17 at 8:50
  • \$\begingroup\$ Also for i in range(n): and then x='a'+o+'b==i+1' saves another 2 bytes. \$\endgroup\$ – PattuX May 26 '17 at 8:54
  • \$\begingroup\$ tio.run/nexus/python2#RY7NCsIwEITP7lOEQk1jIroVeojkSUqFRKIG221J/… \$\endgroup\$ – mbomb007 May 27 '17 at 0:30
1
\$\begingroup\$

JS (ES6), 249 194 188 bytes

(a,b)=>{
  p=n=>{for(i=n;n%--i;);return i-1};    // return 0 if n is prime, non-zero otherwise
  for(n=a-~b;p(n);)n++;                 // increment n until it is prime
  for(z=Array(n).fill(0),               // set all to 'unrelated' (0) and ...
      o="+-*/%|^&",c=0;h=o[c];c++)      // loop through the various operators
    for(v="ab",q=2;q--;)                // try both a?b and b?a
      i=~~eval(v[q]+h+v[1-q]),          // calc the value and floor it
      i>n||i>0&&(z[i-1]=h);             // if within limits, record it
  return z
}

This is a complete overhaul of my original answer which was a 249 byte solution.

Technically this does potentially include exponentiation and concatenation, but since they never show up in the answers, I culled out the code. Heh.

A single line answer:

(a,b)=>{p=n=>{for(i=n;n%--i;);return i-1};for(n=a-~b;p(n);)n++;for(z=Array(n).fill(0),o="+-*/%|^&",c=0;h=o[c];c++)for(v="ab",q=2;q--;)i=~~eval(v[q]+h+v[1-q]),i>n||i>0&&(z[i-1]=h);return z}

f=
(a,b)=>{p=n=>{for(i=n;n%--i;);return i-1};for(n=a-~b;p(n);)n++;for(z=Array(n).fill(0),o="+-*/%|^&",c=0;h=o[c];c++)for(v="ab",q=2;q--;)i=~~eval(v[q]+h+v[1-q]),i>n||i>0&&(z[i-1]=h);return z}

console.log(f(2,3))
console.log(f(1,1))
console.log(f(6,6))
console.log(f(6,12))
console.log(f(7,15))

Recently, switched to stack snippet instead of tio.run and changed console.log(z) to return z. I was returning at first then switched to console.log because I though returning was against the rules. Its never quite clear to me when I'm allowed to return values rather than outputting them directly, but I see other golfers do it this way.

Also, Try it online! (redundant, I know, but I finally figured out tio.run.)

\$\endgroup\$
  • \$\begingroup\$ I'm having trouble with tio.run, having barely used it before. If anyone knows how to fix that, please let me know. \$\endgroup\$ – Octopus May 25 '17 at 5:08
  • \$\begingroup\$ TIO doesn't have "regular" JS. As such, you cannot use it. You'd have to use a stack snippet. \$\endgroup\$ – Luke May 25 '17 at 10:13
  • \$\begingroup\$ @Luke, well I had it working and producing the correct results. It was only when I tried to make it a linkable, that it stopped doing as expected. Had it set to javascript-node. \$\endgroup\$ – Octopus May 25 '17 at 18:17

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.