13
\$\begingroup\$

Background

A bijective base \$b\$ numeration, where \$b\$ is a positive integer, is a bijective positional notation that makes use of \$b\$ symbols with associated values of \$1,2,\cdots,b\$.

Bijective base 2 representations of positive integers look like this:

1 -> 1
2 -> 2
3 -> 11
4 -> 12
5 -> 21
6 -> 22
7 -> 111
8 -> 112
9 -> 121
10 -> 122

Now, let's apply this to a mixed base. Bijective mixed base \$[b_1,b_2,\cdots,b_n]\$ numeration uses \$1,\cdots,b_k\$ as the symbols for each digit place, and the digit value of each digit place is \$\prod_{i=k+1}^{n}b_i\$, as in the usual mixed base. This system can uniquely represent the integers from 1 up to the number represented by \$b_1b_2\cdots b_n\$.

Some numbers in bijective base \$[2,3,4]\$:

1 -> 1
2 -> 2
4 -> 4
5 -> 11
9 -> 21
16 -> 34
17 -> 111
28 -> 134
29 -> 211
40 -> 234

Challenge

Given the base \$b=[b_1,b_2,\cdots,b_n]\$ and a positive integer \$x\$, convert \$x\$ to bijective mixed base \$b\$ as a list of digit values. It is guaranteed that \$x\$ is representable in the system. Some digits of \$b\$ may be greater than 9. You can take the input \$b\$ and give output in either most- or least-significant-digit-first order (mixing is also OK).

Standard rules apply. The shortest code in bytes wins.

Protip: Jelly does not have this built-in.

Test cases

Test cases are written in most-significant-digit-first order.

x = 1, b = [1] -> [1]
x = 3, b = [1,1,1,1] -> [1,1,1]

For b = [2, 1, 2, 3, 4]:
x = 1 -> [1]
x = 4 -> [4]
x = 10 -> [2, 2]
x = 20 -> [1, 1, 4]
x = 35 -> [2, 2, 3]
x = 56 -> [1, 2, 1, 4]
x = 84 -> [1, 1, 2, 2, 4]
x = 112 -> [2, 1, 2, 3, 4]

for b = [8, 9, 10, 11]:
x = 1 -> [1]
x = 2 -> [2]
x = 6 -> [6]
x = 24 -> [2, 2]
x = 120 -> [10, 10]
x = 720 -> [6, 5, 5]
x = 5040 -> [4, 9, 8, 2]
\$\endgroup\$

9 Answers 9

5
\$\begingroup\$

JavaScript (Node.js), 40 bytes

x=>b=>b.flatMap(v=>x?x-(x=~-x/v|0)*v:[])

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Or 38 bytes with BigInts. \$\endgroup\$
    – Arnauld
    Nov 8, 2021 at 7:44
3
\$\begingroup\$

Haskell, 37 bytes

0#_=[]
a#(b:c)|q<-div(a-1)b=a-b*q:q#c

Try it online!

Inputs and outputs are in least-significant-digit-first order.

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

Wolfram Language (Mathematica), 40 bytes

Based on @tsh's Javascript answer.

-6 bytes thanks to @att.

Map[x=#;Pick[x-(x=⌊--x/#⌋)#,x>=0]&]&

Try it online!

Inputs and outputs are in least-significant-digit-first order.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 40 bytes inputting [x][b] \$\endgroup\$
    – att
    Nov 8, 2021 at 6:15
3
\$\begingroup\$

Ruby, 39 bytes

->x,b{b.map{|y|x>0&&x-y*x= ~-x/y}-[!0]}

Try it online!

Freely adapted from tsh's Javascript

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

Python 3, 51 bytes

f=lambda n,l:n*l and[~-n%l[0]+1]+f(~-n//l[0],l[1:])

Try it online!

reversed digit order

\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte by switching to Python 2 and using / instead of //. \$\endgroup\$ Nov 8, 2021 at 9:04
2
\$\begingroup\$

Retina 0.8.2, 43 bytes

\d+
$*
+`(1+),*;(\1)*(1+)
;$#2$*1,$.3
.*;,

Try it online! Link includes test cases. Takes input in the order b₁,...,bₙ;x. Explanation:

\d+
$*

Convert to unary.

+`(1+),*;(\1)*(1+)
;$#2$*1,$.3

Repeatedly divmod x by b in reverse order, but always ensuring that the remainder is non-zero, and convert the remainder to decimal, but keep the quotient in unary.

.*;,

Delete any unused bases.

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

Charcoal, 20 bytes

W∧θ⊟η«≦⊖θ←⸿I⊕﹪θι≧÷ιθ

Try it online! Link is to verbose version of code. I/O is in left-to-right order. Explanation:

W∧θ⊟η«

While x is nonzero, retrieve the previous mixed base b from the list of mixed bases.

≦⊖θ

Decrement x.

←⸿I⊕﹪θι

Reduce x modulo b, then increment the result, and print it on the previous line.

≧÷ιθ

Integer divide x by b.

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

Red, 79 bytes

func[n b][r: copy[]until[insert r(n: n - 1)%(t: take/last b)+ 1 1 > n: n / t]r]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 10 bytes

vD_#<y‰`>,

Inputs are in the order \$[b],x\$. I/O are both in least-significant-digit-first order, so reversed of the challenge description. The output is newline delimited.

Try it online or verify all test cases.

Explanation:

v           # Loop `y` over the first (implicit) input-list:
 D          #  Duplicate the current integer
            #  (which is the second implicit input-integer in the first iteration,
            #  and the quotient of the divmod every other iteration)
  _         #  If this is 0:
   #        #   Stop the loop
    <       #  (Else) Decrease the integer by 1
     y‰     #  Divmod it by `y`
       `    #  Pop and push both values separated to the stack
        >   #  Increase the top (the remainder) by 1
         ,  #  Pop and output it with trailing newline
\$\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.