# Determine the Base where a Given Equation is True

Given 3 integers, determine the lowest possible base for the first two integers to multiply into the third. If you think of the Answer to the Ultimate Question of Life, The Universe, and Everything, 6 * 9 == 42, is true in Base 13.

The inputs can include any numbers whose digits use the characters 0-9, a-z, and A-Z, where a equals 10 in Base 10, and Z is 61 in Base 10.

The inputs should be inputted in any way you like (except for hard-coding), and you can write either an individual function or an entire program.

The maximum base that must be considered is Base 62, and the minimum base is Base 2.

You can assume that the first two values are smaller than the third. You can also conclude that the minimum base is one greater than the highest digit/character from the inputs (for example, if the inputs are 3 1a 55, the minimum base would be Base 11, because a is the highest digit).

If there is no such base, return a junk value of your choice.

This is code golf, so the shortest code wins.

Test Cases

6 9 42     -->   13
a a 64     -->   16
aA bB 36jk -->   41
2 3 20     -->   <junk value>
10 10 100  -->   2

• I think STDIN would probably be better, and either would be fine. Commented Oct 27, 2014 at 12:17
• As a point of clarification what should be done if multiple bases are valid such as your last example (which has now been removed - it was 10*10=100) where it is also valid in base 10 and indeed any other base you care to mention... Commented Oct 27, 2014 at 17:28
• @Kay If I define the positional system in base b in a general way like a_0 b^0 + a_1 b^1 + a_2 b^2 + ... (where a_0 is the least significant digit) than base 1 definitely makes sense. Furthermore, the OP's conclusion would also include base 1 in the search if the largest present digit is 0. Commented Oct 27, 2014 at 17:44
• About base 1, unary is a number system. en.m.wikipedia.org/wiki/Unary_numeral_system Commented Oct 27, 2014 at 18:20
• Going up to base 62 AND requiring error cases really puts a wrench in the system. Commented Mar 8, 2019 at 23:59

# APL (Dyalog Unicode), 30 bytesSBCS

⊢{3⊃e=×/2↑e←⍵⊥⍺:⍵⋄⍺∇⍵+1}1+⌈/∘,


Try it online!

Thanks to Adám for the help.

Explanation:

⊢{3⊃e=×/2↑e←⍵⊥⍺:⍵⋄⍺∇⍵+1}1+⌈/∘, ⍝
⊢                              ⍝ left argument ⍺: the vector (do nothing)
1+⌈/∘, ⍝ right argument ⍵: our starting base.
, ⍝             start by flattening the matrix of arguments                               ⌈/   ⍝             reduce by max (find the highest number)
∘  ⍝             compose both of these together
1+     ⍝             increment by one
{         ⍵⊥⍺         }       ⍝ convert inputs to the current base
{       e←            }       ⍝ store the converted values in 3
{      2↑             }       ⍝ take the first 2 values
{    ×/               }       ⍝ multiply them together (reduce-multiply)
{  e=                 }       ⍝ compare with e (the converted inputs)
{3⊃                   }       ⍝ only keep the result of the comparison with the 3rd element (expected result)
{             :⍵      }       ⍝ if truthy, return the current base.
{               ⋄     }       ⍝ otherwise...
{                ⍺∇⍵+1}       ⍝ ...recurse with the base incremented


We use a helper function, In, to receive the input into a more palatable format. Otherwise the input is received a matrix of 3 columns.

'3 9 42' would give, for example (read top-down then left-to-right):

0 0 4
3 9 2


And for 'aA bB 36jk' (same here. a is 10, b is 11, A is 36, etc)

 0  0  3
0  0  6
10 11 19
36 37 20


## CJam, 5251 48 bytes

63,{_ea{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#


Test it here. The online tester doesn't support input via ARGV. The closest alternative is to put put the input like 6 9 42 into STDIN and use:

lS/:E;
63,{_E{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#


This prints -1 if no valid base up to 62 can be found.

Many thanks to Peter for the digit parsing code!

I fixed a lot of problems which added 14 bytes to the count. The following explanation is still for my original submission, and I'll update it some time tomorrow.

63,{_ea{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#
63,                                              "Push the array [0 1 .. 62].";
{                                          }# "Find the first index for which the block returns
a truthy value.";
_                                            "Duplicate the current base.";
ea                                          "Read ARGV into an array of strings.";
{                        }f%              "Apply this block to each character.";
i32b                                     "Convert to code point, and then to base-32. The
most significant digit now identifies the 'type'
of digit.";
~\(                                  "Unwrap the array. Swap the digits. Decrement.";
[G-35-9]                          "Push array [16 -35 -9] of digit offsets.";
=-                        "Select the relevant offset and subtract it from
the least significant digit.";
_                       "Duplicate the current digit D.";
Xe>:X;                 "X := max(X,D). X is predefined as 1.";
fb            "Convert all numbers to the current base.";
W%          "Reverse the list of numbers.";
~         "Unwrap the array.";
*=       "Multiply factors. Check equality with product.";
\      "Swap result with current base.";
X>    "Ensure base is greater than X.";
*   "Multiply boolean results.";


The index is printed automatically at the end of the program.

• In GS the digits can be parsed as 32base~\[-16.35 9]=+. I know CJam has shorter base conversion. Commented Oct 27, 2014 at 14:11

# Python 2 - 197 213

What a monster... (compared to CJam)

from string import*
I=raw_input()
x,y,z=I.split()
B=lambda s,b:sum(b**i*(digits+lowercase+uppercase).find(s[-i-1])for i in range(len(s)))
print([b for b in range(B(max(I),10)+1,62)if B(x,b)*B(y,b)==B(z,b)]+[0])[0]


Unfortunately int's base conversion can only handle bases up to 36. So I needed to implement it by myself. (See this wonderful solution.)

• Does this make sure not to return a base less than or equal to the largest digits? Commented Oct 27, 2014 at 17:04
• @MartinBüttner: I'm not sure. At least not explicitly. Do you have a test case where this is an issue? (Actually, generating test cases should be taken care of by the OP...) Commented Oct 27, 2014 at 18:18
• Try 2*3=20 which has base 3 in an error case. 3 is not a digit in a ternary numeral system. Commented Oct 27, 2014 at 18:34

lA,s'{,97>+'[,65>+f#_$W=1e>)63,>_@Wa/W%f{fb~*=}1#\0+=  Takes the three input from STDIN like 6 9 42  Prints 0 if product in any base is not possible Will try to golf it further. Try it here # Prolog - 195 bytes Basically the same idea as my Erlang answer: :-use_module(library(main)). main(A):-between(2,62,B),maplist(x(B),A,[F,G,P]),0is F*G-P,write(B). c(I,B,Q,O):-Q=[H|T]->(H<65->D=48;H<97->D=29;D=87),H-D<B,c(I*B+H-D,B,T,O);O=I. c(B)-->name,c(0,B).  In readable: :- use_module(library(main)). main(Args) :- between(2, 62, Base), maplist(convert(Base), Args, [Factor1, Factor2, Product]), 0 is Factor1 * Factor2 - Product, write(Base). convert(Accumulator, Base, List, Output) :- List = [Head|Tail] -> ( Head < 65 -> Offset = 48; Head < 97 -> Offset = 29; Offset = 87), Head - Offset < Base, convert(Accumulator * Base + Head - Offset, Base, Tail, Output); Output = Accumulator. convert(Base, Input, Output) :- name(Input, List), convert(0, Base, List, Output).  Invocation: $ swipl -qg main x.pl 6 9 42
13
$swipl -qg main x.pl aA bB 36jk 41$ swipl -qg main x.pl 2 3 20
ERROR: Unknown message: goal_failed(main([2,3,20]))


# JavaScript (E6) 129 139

Recursively try all bases from 2 up to 62, returning -1 if no value is ok.
JavaScript parseInt function works with base up to 36, so a little help is needed for greater bases.
Beware, the parameters x,y,z are strings, not numbers.
It's more difficult than it seems. Thanks to Martin for pointing out a basic bug in the first version.

F=(x,y,z,b=2,N=n=>[for(d of(t=0,n))t=(v=parseInt(d,36)+(d>'@'&d<'a')*26)<b?t*b+v:NaN]&&t)=>b<63?N(x)*N(y)!=N(z)?F(x,y,z,b+1):b:-1


Less golfed

F=(x,y,z,b=2,
D=d=>parseInt(d,36)+(d>'@'&d<'a')*26, // parse a single digit
N=n=>[for(d of(t=0,n))t=(v=D(d))<b?t*b+v:NaN]&&t // parse a string
)=>b<63?N(x)*N(y)!=N(z)?F(x,y,z,b+1):b:-1


Test In FireFox/FireBug console.
The test tries 1000 numbers with different bases (up to 36, not 62). It's worth noting that the found base could be correct but less than the base that generated the test case.

for(i=0;i<1000;i++)
{
x=Math.random()*100|0,y=Math.random()*100|0,z=x*y,b=Math.random()*35+2|0
bx=x.toString(b),by=y.toString(b),bz=z.toString(b),
nb=F(bx,by,bz)
nx=parseInt(bx,nb),ny=parseInt(by,nb),nz=parseInt(bz,nb)
// if (nx*ny != nz) // uncomment to se output for errors only
console.log(x,y,z,'base '+b,bx,by,bz, 'found base '+nb,nx,ny,nz,nx*ny)
}

• @MartinBüttner the parameters are strings (as possible values are something like aA bB 36jk ...). Clarified in the answer. Commented Oct 28, 2014 at 6:53
• Oh right, that makes sense. Commented Oct 28, 2014 at 6:57

# Charcoal, 28 bytes

Ｉ⌊Φ…⊕⍘⌈⁺⁺θηζ⁶²¦⁶³⁼×⍘θι⍘ηι⍘ζι


Try it online! Link is to verbose version of code. Outputs None if no valid base can be found. Explanation:

         θ                      First input
⁺                       Concatenated with
η                     Second input
⁺                        Concatenated with
ζ                    Third input
⌈                         Maximum character (by ordinal)
⍘                          Converted from base
⁶²                  Literal 62
⊕                           Incremented
…                            Range up to
⁶³               Literal 63
Φ                             Filtered by
θ           First input
⍘            Converted from base
ι          Current value
×             Multiplied by
η        Second input
⍘         Converted from base
ι       Current value
⁼              Equals
ζ     Third input
⍘      Converted from base
ι    Current value
⌊                              Minimum
Ｉ                               Cast to string
Implicitly print

• Is it possible to have a TIO program that uses the actual code you posted? Commented Mar 6, 2019 at 19:18
• @mbomb007 You can Try it online! but the AST generator seems to think ⍘ is Any for some reason...
– Neil
Commented Mar 6, 2019 at 21:14

# Jelly, 16 bytes

62ḊḅṪ=PƊ¥@ƇeoḢ{ɗ


Try it online!

Takes input similar to the APL answer. For example, aA bB 36jk is input as [10, 36], [11, 37], [3, 6, 19, 20]. The Footer does this for you.

If this isn't acceptable, +10 bytes to convert from a list of strings.

Outputs 1 as the junk value.

## How it works

I'll explain the preceding 10 bytes for the longer version first, as both share the same ending 16 bytes:

ØBŒsiⱮⱮ⁸’µ - Main link. Takes a list of strings on the left
ØB         - Yield '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
Œs       - Swap-case
Ɱ⁸   - Over each string in the left argument:
Ɱ     -   Over each character:
i      -     1-based index
’  - Decrement to 0-index
µ - Use this list of numbers as the argument from now on

62ḊḅṪ=PƊ¥@ƇeoḢ{ɗ - Main link. Takes an list of lists of integers on the left
62               - Yield 62
Ḋ              - Dequeue; [2, 3, 4, ..., 62]
Ƈ      - Filter this array...
¥        -    ...on the following, ...
@       -    ...with the list on the right:
ḅ             -   Convert from base
Ɗ         -   To this array of integers:
Ṫ            -     Does the tail...
=           -     equal...
P          -     ...the product without the tail?
ɗ - Using the input on the right and the filtered array on the left:
e     -   Is the filtered array in the input?
Ḣ{  -   Yield the first element of the filter
o    -   If the filtered array is in the input, return 1, else the first element


# Erlang (escript) - 200

main(X)->m(2,X).
m(63,_)->0;m(C,X)->try[F,G,I]=[c(0,C,Y)||Y<-X],I=F*G,io:fwrite("~p",[C])catch _:_->m(C+1,X)end.
c(A,B,[H|T])->D=H-if$A>H->$0;$a>H->29;0<1->87end,if D<B->c(A*B+D,B,T)end;c(A,_,_)->A.  Add two leading newlines which must be present. In readable: #!/usr/bin/env escript main(Args) -> test(2, Args). test(63, _) -> 0; test(Base, Args) -> try [Factor1, Factor2, Product] = [convert(0, Base, Arg) || Arg <- Args], Product = Factor1 * Factor2, io:fwrite("~p", [Base]) catch _:_ -> test(Base + 1, Args) end. convert(Accumulator, Base, [Head|Tail]) -> Digit = Head - if Head <$A -> $0; Head <$a -> $A - 10 - 26; true ->$a - 10
end,
if Digit < Base ->
convert(Accumulator * Base + Digit, Base, Tail)
end;
convert(Accumulator, _, _) -> Accumulator.


Invocation:

$escript x.erl 6 9 42 13$ escript -i x.erl a a 64
16
$escript -i x.erl aA bB 36jk 41$ escript -i x.erl 2 3 20
(no output)
$escript -i x.erl 10 10 100 2  • Does this make sure not to return a base less than or equal to the largest digits? Commented Oct 27, 2014 at 17:07 • Yes, the if Digit < Base -> … end part takes care of it. If an if block has no true branch, then an exception is thrown, which gets caught in try … catch _:_ -> … end. Commented Oct 27, 2014 at 17:10 # Haskell 216 char (177?) Tried to golf this as much as possible. If imports are counted, then this is my shortest code (216) import Data.Char import Data.List m=maximum j[]=0;j(x:_)=x f=reverse.map(\x->ord x-48) g[]_=0;g(m:n)x=m+x*g n x main=do l<-getLine let k@[x,y,z]=words l print$j[n|n<-[2..62],g(f x)n*g(f y)n==g(f z)n,n>(m.map(m.f)$k)]  However, were imports not counted, then this is my best version (177): import Data.Char import Data.List import Control.Applicative m=maximum j[]=0;j(x:_)=x f=reverse.map(\x->ord x-48) g[]_=0;g(m:n)x=m+x*g n x main=words<$>getLine>>= \k@[x,y,z]->print$j[n|n<-[2..62],g(f x)n*g(f y)n==g(f z)n,n>(m.map(m.f)$k)]


This treats each number as a polynomial P(x) where x is the base, on condition that no coefficient is larger than x; I then evaluate the polynomials over each possible base, stopping when I reach one that satisfies the equality P(x)*Q(x)=R(x). The 'base is bigger than largest digit' rule is enforced with the last guard in the pattern match, namely n>(m.map(m.f)$k). I know that different golfing challenges and different challenge-makers have different policies regarding imports vis-a-vis scoring, so take the second one with a grain of salt. • The solutions are actually 216 and 177 bytes/characters, respectively. But the second solution is invalid, because imports are counted unless the OP explicitly specifies otherwise, which is not the case here as far as I can tell. – user344 Commented Oct 27, 2014 at 20:24 # Julia, 122 bytes (79 with bending rules) Julia has an in-built up to base 62 integer parser, but the problem is uppercase characters come before lowercase f(l,n=2)=try L=[parse(Int,join(i+32(i>'9')-64(i>'Z') for i=j),base=n) for j=l] L[1]L[2]==L[3]||$
n
catch
n<62&&f(l,n+1)end


$ isn't define and will raise an error when the equality isn't right Try it online! # Julia, 79 bytes by swapping uppercase and lowercase If I'm allowed to swap lowercase and uppercase, It would shave off a lot of bytes (or at least if there was a swapcase function) f(l,n=2)=try L=parse.(Int,l,base=n) L[1]L[2]==L[3]||$
n
catch
n<62&&f(l,n+1)end


Try it online!