20
\$\begingroup\$

Your task is to decompose a number using the format below.

This is similar to base conversion, except that instead of listing the digits in the base, you list the values, such that the list adds up to the input.

If the given base is \$n\$, then each number in the list must be in the form of \$k\times n^m\$, where \$0\le k<n\$ and \$m\$ is unique throughout the list.

Specs

  • Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.
  • Output list can be in any order.
  • 0 can be excluded or included.
  • Leading 0s are allowed.
  • Built-ins are allowed.

Testcases

number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]

Scoring

This is . Shortest solution in bytes wins.

\$\endgroup\$

27 Answers 27

7
\$\begingroup\$

Jelly, 7 bytes

lr0⁹*×b

Try it online! or verify all test cases.

How it works

lr0⁹*×b  Main link. Arguments: x (integer), n (base)

l        Compute the logarithm of x to base n.
 r0      Range; yield all non-negative integers less than the logarithm, in
         decreasing order.
   ⁹*    Elevate n to all integers in that range.
      b  Yield the list of base-n digits of x.
     ×   Multiply each digit by the corresponding power of n.
\$\endgroup\$
2
  • \$\begingroup\$ Ah, reversed range... \$\endgroup\$
    – Leaky Nun
    May 2, 2016 at 4:05
  • \$\begingroup\$ It is so impressive what can be achieved with so few characters \$\endgroup\$ May 3, 2016 at 8:24
5
\$\begingroup\$

JavaScript (ES6), 47 bytes

f=(n,b,p=1,q=b*p)=>[...n<q?[]:f(n,b,q),n%q-n%p]
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(...c)).join`\n`)

\$\endgroup\$
1
  • \$\begingroup\$ Care to include a snippet? :) \$\endgroup\$
    – Leaky Nun
    May 1, 2016 at 9:27
4
\$\begingroup\$

Jelly, 12 bytes

bLR’*@€U
b×ç

Can be waaaay shorter...

Try it online!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ jelly.tryitonline.net/… \$\endgroup\$
    – Leaky Nun
    May 1, 2016 at 3:23
  • 3
    \$\begingroup\$ lḞr0⁴*×b should work. \$\endgroup\$
    – Dennis
    May 1, 2016 at 5:54
  • \$\begingroup\$ Technically, 0r⁴*³%I works as well. \$\endgroup\$
    – Dennis
    May 1, 2016 at 20:49
  • \$\begingroup\$ Scratch that. lr0⁴*×b has the same byte count, without all the extra zeroes. \$\endgroup\$
    – Dennis
    May 2, 2016 at 2:53
  • \$\begingroup\$ @Dennis That's definitely different enough to post as a separate answer. \$\endgroup\$
    – Doorknob
    May 2, 2016 at 3:32
4
\$\begingroup\$

Pyth - 12 11 bytes

Just a FGITW, can be shorter.

.e*b^Qk_jEQ

Test Suite.

\$\endgroup\$
3
  • \$\begingroup\$ Remove the _ for a byte :) \$\endgroup\$
    – Leaky Nun
    May 1, 2016 at 3:17
  • \$\begingroup\$ @KennyLau meant FGITW, it means "Fastest Gun In The West", a phenomenon where people answering first get more upvotes than the better answers. \$\endgroup\$
    – Maltysen
    May 1, 2016 at 3:17
  • \$\begingroup\$ @KennyLau oh that's allowed, derp. \$\endgroup\$
    – Maltysen
    May 1, 2016 at 3:18
4
\$\begingroup\$

J, 20 19 bytes

[(]*(^<:@#\.))#.inv

Usage

   f =: [(]*(^<:@#\.))#.inv
   10 f 123456
100000 20000 3000 400 50 6
   2 f 11
8 0 2 1
   20 f 727
400 320 7
   10 f 101
100 0 1

Explanation

[(]*(^<:@#\.))#.inv
              #.      Given a base and list of digits in that base,
                      converts it to an integer in base 10
                inv   Power conjunction by -1, creates an inverse
                      Now, this becomes a verb that given a base and an integer in base 10,
                      creates a list of digits in that base representing it
[                     Select the base and pass it along
         #\.          Tally each suffix of the list of base digits,
                      Counts down from n to 1
      <:              Decrements each value
        @             More specifically, decrement is composed with the tally and applied
                      together on each suffix
     ^                Raises each value x using base^x
  ]                   Selects the list of base digits
   *                  Multiply elementwise between each base power and base digit
\$\endgroup\$
0
3
\$\begingroup\$

CJam, 16 bytes

{1$b\1$,,f#W%.*}

An unnamed block that expects the base and the number on top of the stack (in that order) and replaces them with the digit list (including internal zeros, without leading zeros).

Test it here.

Explanation

1$  e# Copy base b.
b   e# Compute base-b digits of input number.
\   e# Swap digit list with other copy of b.
1$  e# Copy digit list.
,   e# Get number of digits M.
,   e# Turn into range [0 1 ... M-1].
f#  e# Map b^() over this range, computing all necessary powers of b.
W%  e# Reverse the list of powers.
.*  e# Multiply each digit by the corresponding power.
\$\endgroup\$
3
\$\begingroup\$

TSQL, 68 bytes

DECLARE @ INT=123456,@z INT=10
DECLARE @l INT=1WHILE
@>0BEGIN PRINT @%@z*@l SELECT @/=@z,@l*=@z END
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 46 bytes

DiagonalMatrix@IntegerDigits@##~FromDigits~#2&

Explanation:


In[1]:= IntegerDigits[123456,10]                                                

Out[1]= {1, 2, 3, 4, 5, 6}

In[2]:= DiagonalMatrix@IntegerDigits[123456,10] // MatrixForm                   

Out[2]//MatrixForm= 1   0   0   0   0   0

                    0   2   0   0   0   0

                    0   0   3   0   0   0

                    0   0   0   4   0   0

                    0   0   0   0   5   0

                    0   0   0   0   0   6

In[3]:= DiagonalMatrix@IntegerDigits[123456,10]~FromDigits~10                   

Out[3]= {100000, 20000, 3000, 400, 50, 6}
\$\endgroup\$
1
  • \$\begingroup\$ Very unexpected use of DiagonalMatrix. Kindly explain how it works in this case. \$\endgroup\$
    – DavidC
    Aug 20, 2016 at 16:15
3
\$\begingroup\$

Jelly, 8 bytes

bḅ²×¥@b×

Try it online!

²×¥@ seems too long for what it does. I hope there is a shorter way.

Explanation

b             Convert A (the input number) to base B (the input base).
 ḅ²×¥@        Convert from base A×B²
      b×      Convert to base A×B
\$\endgroup\$
3
\$\begingroup\$

Regex (ECMAScript), 76 bytes

(?=.*,(x(x*)))(?=.*?(((?=(?=\1*,)(x(x*))(?=\5*,)(?=\2+,)(\2\6*),)\7)*x),)\3+

Takes its input in unary, as the length of two string of xs delimited by a , (number first, then base). Returns its result as the list of matches (each is also a string of xs whose length is the value).

Try it online!

It's a good thing the challenge allows 0 to be excluded or included, because this solution excludes it, and it would not be possible to include it! (The only way to include it would be either to use .NET with the result returned via a capture's stack, or PCRE with a callout.)

The division algorithm is explained in my Division and remainder post.

# If this is the first match, tail = N = input number. Otherwise
# tail = N = current intermediate value, which is the input number
# after having the previous return values all subtracted from it.
(?=
    .*,(x(x*))             # \1 = number base; \2 = \1 - 1
)
(?=
    .*?                    # Decrease tail by the minimum necessary to satisfy
                           # the following assertion:
    # Assert tail is a power of \1; \3 = tail = the largest power of \1 that is
    # less than or equal to N.
    (                      # \3 = tail
        (
            (?=
                # Calculate \5 = tail / \1
                (?=\1*,)   # Assert tail is divisible by \1
                (x(x*))    # \5 = quotient - find the largest that matches the
                           #      following assertions; \6 = \5-1; tail -= \5
                (?=\5*,)   # assert tail is divisible by quotient
                (?=\2+,)   # assert tail is positive and divisible by divisor-1
                (\2\6*),   # assert tail-(divisor-1) is divisible by quotient-1;
                           # \7 = tool to make tail = \5
            )\7            # tail = \5
        )*                 # Iterate the above as many times as possible
        x                  # tail -= 1
    )
    ,                      # Assert tail == 0
)
\3+                        # Return value = M = tail - (tail % \3); tail -= M
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 12 bytes

I wonder whether Wolfram Research created this function after seeing the OP's challenge!

NumberExpand

This was introduced in version 11.0 (August, 2016).

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

Python 2, 44 bytes

lambda n,b:[n/b**i%b*b**i for i in range(n)]

Outputs from least significant to most, with many extra zeroes.

To output most significant to least:

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

Recurse, repeatedly taking digits off of n with divmod while scaling up the place value multiplier c.

\$\endgroup\$
2
  • \$\begingroup\$ For the second version, can't you do range(-n,1) instead of range(n,-1,-1)? \$\endgroup\$ Jul 18, 2016 at 18:49
  • \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Thanks, I didn't see that going in reverse was an option. It even suffices to just do range(n). \$\endgroup\$
    – xnor
    Jul 18, 2016 at 22:46
2
\$\begingroup\$

Ruby, 35 34 bytes

This is a port of xnor's Python answer, but it prints n times so the test case 727 20 prints 7, 320, 400, and 724 0s. Golfing suggestions welcome.

Edit: 1 byte thanks to Jordan.

->n,b{n.times{|i|p n/b**i%b*b**i}}
\$\endgroup\$
1
  • \$\begingroup\$ You can save a byte with n.times{|i|p ...}. \$\endgroup\$
    – Jordan
    Aug 20, 2016 at 16:08
2
\$\begingroup\$

Pip, 13 bytes

Wa-:Pa%oo*:b

Doing it the old-fashioned way turned out to be shorter than using the TB base-conversion operator. The code runs a while loop until a (the number) is 0. At each iteration, it prints a%o and subtracts it from a. o is preinitialized to 1 and gets multiplied by b (the base) each iteration. (This approach keeps all 0s and also adds a leading 0.)

Try it online!

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

Vyxal r, 7 bytes

τ:ẏṘ⁰e*

Try it Online!

A nice little answer. Takes value then base

Explained

τ:ẏṘ⁰e*
τ       # Convert value from base 10 to input base
 :ẏṘ    # Duplicate that and push the range [len(that) - 1, 0]
    ⁰e  # Raise base to the power of each item in that
      * # Multiply that by the list of digits of the converted value
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 44 bytes

b=>g=n=>n?[...g(~~(n/b)).map(i=>i*b),n%b]:[]

Try it online!

Takes curried input in the form function(base)(number).

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

Desmos, 57 bytes

k=b^{[floor(log_b(n+0^n))...0]}
f(n,b)=mod(floor(n/k),b)k

Try It On Desmos!

Try It On Desmos! - Prettified

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

BQN, 18 bytes

-⟜»⊢|˜⊣⋆1+·↕∘⌈⊣⋆⁼+

Tacit function; takes the base as left argument and the number as right argument. Try it at BQN online!

Explanation

Call the left argument b and the right argument n.

-⟜»⊢|˜⊣⋆1+·↕∘⌈⊣⋆⁼+
                ⋆⁼   Inverse exponential (i.e. logarithm)
               ⊣     with base b
                  +  of b + n
              ⌈       Round up to nearest integer
                     This number is at least as large as the number of base-b digits n has
            ↕∘       Range (0-based, exclusive)
         1+·         Add 1 to each
       ⊣⋆            Raise b to each of those exponents
    ⊢|˜              Take n mod each of those powers of b
   »                 Shift a copy of that list right, prepending a 0
-⟜                  and subtract it from the unshifted list

For example, with a base of 3 and a number of 17, we have

+       20
⊣⋆⁼     2.726833027860842
1+·↕∘⌈   ⟨ 1 2 3 ⟩
⊣⋆      ⟨ 3 9 27 ⟩
⊢|˜     ⟨ 2 8 17 ⟩
»       ⟨ 0 2 8 ⟩
-⟜     ⟨ 2 6 9 ⟩
\$\endgroup\$
1
\$\begingroup\$

Racket, 82 bytes

(define(d n b[a'()])(if(< n 1)a(d(/ n b)b(cons(*(modulo(floor n)b)(length a))a))))

I'm a winner (!)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ So many spaces... does <n 1 not work? (I don't know Racket at all) \$\endgroup\$
    – Leaky Nun
    May 1, 2016 at 4:37
  • 1
    \$\begingroup\$ No that wouldn't work -- identifiers are delimited only by whitespace, parentheses/braces/curly braces, and some other symbols, like '. It's a good question, though. \$\endgroup\$
    – Winny
    May 1, 2016 at 4:41
  • \$\begingroup\$ (And < is just a variable with a function bound to it) \$\endgroup\$
    – Winny
    May 1, 2016 at 4:41
1
\$\begingroup\$

JavaScript (ES7), 68 bytes

n=>b=>(c=[...n.toString(b)]).map(d=>b**--p*parseInt(d,b),p=c.length)

Test

Test uses Math.pow for browser compatibility.

f=n=>b=>(c=[...n.toString(b)]).map(d=>Math.pow(b,--p)*parseInt(d,b),p=c.length)
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(c[0])(c[1])).join`\n`)

\$\endgroup\$
3
  • \$\begingroup\$ ** isn't a valid JavaScript operator though right? \$\endgroup\$
    – ericw31415
    May 1, 2016 at 13:15
  • 1
    \$\begingroup\$ @ericw31415 It's the ES7 exponentiation operator. \$\endgroup\$
    – user81655
    May 1, 2016 at 13:21
  • \$\begingroup\$ Oh, it's experimental. That's why my browser does not support it. \$\endgroup\$
    – ericw31415
    May 1, 2016 at 13:50
1
\$\begingroup\$

JavaScript, 75 bytes

(a,b)=>[...a.toString(b)].reverse().map(($,_)=>Math.pow(b,_)*parseInt($,b))

Just for fun :) It could be golfed more, but I'm not too sure how.

ES7, 66 bytes

If ES7 is allowed then:

(a,b)=>[...a.toString(b)].reverse().map(($,_)=>b**_*parseInt($,b))
\$\endgroup\$
1
\$\begingroup\$

O, 17 bytes

jQb`S/l{#Qn^*p}d

Two notes:

  1. The third test case does not work due to a bug with base conversion. See phase/o#68.

  2. This does not work in the online interpreter. b hadn't been implemented yet.

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

><>, 28 bytes

:&\
&*>:{:}$%:n$}-:0=?;ao$&:

Expects the input values to be present on the stack at program start.

As ><> doesn't have list objects, the output is presented as a newline-separated list of values, with the 'units' on the first line. An example run:

Input: 
11 2

Ouput:
1
2
0
8

@OP, if this isn't an acceptable output format, let me know and I'll edit the answer accordingly.

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

PHP, 55 bytes

Uses Windows-1252 encoding.

for($n=$argv[1];$d+$n-=$d=$n%$argv[2]**++$i;)echo$d,~Ó;

Run like this (-d added for aesthetics only):

php -d error_reporting=30709 -r 'for($n=$argv[1];$d+$n-=$d=$n%$argv[2]**++$i;)echo$d,~Ó; echo"\n";' 123056 10
\$\endgroup\$
1
\$\begingroup\$

C#, 77 bytes

IEnumerable _(int n,int b){int m=1;while(n>0){yield return n%b*m;n/=b;m*=b;}}
\$\endgroup\$
1
\$\begingroup\$

C++, 82 Bytes

int*f(int n,int b){int*a,o[n]{b,n%b};for(a=o+1;*a=(n-=*a++)%(b*=*o););return o+1;}

The main loop is pretty trivial (keep taking modulos and subtracting the lower part). The main savings come from doing lots of calculations in-place and the loop condition being the actual assigned value (which will eventually become 0, after all meaningful output is written to the array)

I haven't been able to figure out why, but ideone throws a runtime error if I try to have the function return o instead of o+1, so I use the extra index to store the powers of b.

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

Actually, 17 bytes

;a¡;lrR(♀ⁿ@♂≈♀*;░

Try it online!

Explanation:

;a¡;lrR(♀ⁿ@♂≈♀*;░
                   initial stack: [b n] (b = base, n = number)
;                  dupe b
 a                 invert stack
  ¡                n as a base-b integer
   ;lrR            dupe, length, range, reverse
       (♀ⁿ         raise b to each power in range
          @♂≈      create list of integers from base-b string
             ♀*    pairwise multiplication
               ;░  filter out zeroes
\$\endgroup\$
1

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.