11
\$\begingroup\$

We have many challenges based on base 10, base 2, base 36, or even base -10, but what about all the other rational bases?

Task

Given an integer in base 10 and a rational base, return the integer in that base (as an array, string, etc.).

Process

It's difficult to imagine a rational base, so let's visualize it using Exploding Dots:

Consider this animation, expressing 17 in base 3:

enter image description here

Each dot represents a unit, and boxes represent digits: the rightmost box is the one's place, the middle box is the 3^1 place, and the leftmost box is the 3^2 place.

We can begin with 17 dots at the one's place. However, this is base 3, so the ones place has to be less than 3. Therefore, we "explode" 3 dots and create a dot on the box to the left. We repeat this until we end up with a stable position with no explodable dots (i.e. 3 dots in the same box).

So 17 in base 10 is 122 in base 3.


A fractional base is analogous to exploding some number of dots to more than one dots. Base 3/2 would be exploding 3 dots to create 2.

Expressing 17 in base 3/2:

enter image description here

So 17 in base 10 is 21012 in base 3/2.


Negative bases work similarly, but we must keep track of signs (using so-called anti-dots, equal to -1; represented by an open circle).

Expressing 17 in base -3:

enter image description here

Note, there are extra explosions to make the sign of all the boxes the same (ignoring zeros).

Thus, 17 in base 10 is 212 in base -3.

Negative rational bases work similarly, in a combination of the above two cases.

Rules

  • No standard loopholes.
  • The sign of each "digit" in the output must be the same (or zero).
  • The absolute value of all digits must be less than the absolute value of the numerator of the base.
  • You may assume that the absolute value of the base is greater than 1.
  • You may assume that a rational base is in its lowest reduced form.
  • You may take the numerator and the denominator of the base separately in the input.
  • If a number has multiple representations, you may output any one of them. (e.g. 12 in base 10 can be {-2, -8} and {1, 9, 2} in base -10)

Test cases:

Format: {in, base} -> result

{7, 4/3}        ->  {3, 3}
{-42, -2}       ->  {1, 0, 1, 0, 1, 0}
{-112, -7/3}    ->  {-6, -5, 0, -1, 0}
{1234, 9/2}     ->  {2, 3, 6, 4, 1}
{60043, -37/3}  ->  {-33, -14, -22, -8}

Since some inputs may have multiple representations, I recommend testing the output using this Mathematica snippet on TIO.

This is , so submissions with shortest byte counts in each language win!


For more information on exploding dots, visit the global math project website! They have a bunch of cool mathy stuff!

\$\endgroup\$
1

3 Answers 3

6
\$\begingroup\$

Python 2, 42 39 bytes

n,a,b=input()
while n:print n%a;n=n/a*b

Try it online!

Thanks to @xnor for finding the shorter form.

Obsolete version (42 bytes):

f=lambda n,a,b:n and[n%a]+f(n/a*b,a,b)or[]

Try it online!

Parameters: input, numerator (with sign) and denominator.

Returns an array, lowest digit first.

This just works because the division and modulo in Python follows the sign of the denominator, so we don't have to care about same signs explicitly.

Test case output:

f(7, 4, 3)       == [3, 3]
f(-42, -2, 1)    == [0, -1, -1, -1, -1, -1, -1]
f(-112, -7, 3)   == [0, -1, 0, -5, -6]
f(1234, 9, 2)    == [1, 4, 6, 3, 2]
f(60043, -37, 3) == [-8, -22, -14, -33]
\$\endgroup\$
2
  • 4
    \$\begingroup\$ Unusually, it looks like a program is shorter. \$\endgroup\$
    – xnor
    Mar 5, 2018 at 4:48
  • \$\begingroup\$ @xnor Thanks, I always forget that way to write something... \$\endgroup\$
    – Bubbler
    Mar 5, 2018 at 4:54
4
\$\begingroup\$

Aheui (esotope), 91 bytes

벙수벙섞벙석
희빠챠쌳뻐삭빠빠싻싸삯라망밣밭따맣사나삮빠싸사땨

Try it online!

Takes integer, numerator of base, and denominator of base.

Due to the limitation of the TIO interpreter, each input must end with a newline.

Implementation of @Bubbler's Python 2 answer. Luckily, this Aheui interpreter is written in Python, so we can use the same trick.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ o_O what on earth is this language... D: \$\endgroup\$
    – hyper-neutrino
    Mar 5, 2018 at 7:54
3
\$\begingroup\$

05AB1E, 11 10 bytes

[D_#²‰`,³*

Try it online!

Takes integer, numerator of base and denominator of base like all answers. Since 05AB1E interpreter is written in Python(?), Bubbler's Python 2 answer trick can be used in 05AB1E too.

Explanation

[D_#²‰`,³*
[                                        Infinite Loop
 D_#                                     If the number is 0, exit loop (implicit input
                                         in the first iteration)
     ²                                   Get the numerator of base
      ‰                                  Divmod
       `                                 Push all elements into the stack
        ,                                Print the remainder
         ³                               Get the denominator of base
          *                              Multiply it.

So the program works roughly the same as this Python code:

i1, i2, i3 = input()
stack = []
while 1:
 stack = (stack or [i1])
 stack += [stack[-1]]
 if not stack[-1]: break
 stack += [i2]
 stack = stack[:-2] + [divmod(stack[-2], stack[-1])]
 stack = stack[:-1] + list(stack[-1])
 print stack[-1]
 stack = stack[:-1]
 stack += [i3]
 stack = stack[:-2] + [stack[-2] * stack[-1]]

11 > 10 Thanks Neil

\$\endgroup\$
2
  • \$\begingroup\$ I think you can use _ instead of 0Q here. \$\endgroup\$
    – Neil
    Mar 5, 2018 at 11:07
  • \$\begingroup\$ @Neil Oh true, I forgot about negative boolean! \$\endgroup\$ Mar 5, 2018 at 12:11

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.