Carry-less sum given a base b

Question

Given a list of positive integers \$\mathcal I=I_1,I_2,I_3,...,I_n\$ and a base \$b>1\$ return their "carry-less sum", i.e. represent \$\mathcal I\$ in base \$b\$ and sum digit-by-digit discarding carry.

Worked example:

I = 13, 2, 9; b = 3

In base 3:

   111
 +   2
 + 100
 -----
 = 210

and back to base 10:

desired output: 21

More test cases:

I=[1000, 576, 23, 1, 141], b=12 => 1573

I=[1000, 576, 23, 1, 141], b=2 => 307

I=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], b=4 => 11

I=[1, 2, 3, 5, 8, 13, 21, 34, 55], b=5 => 77

I=[900, 100], b=10 => 0

This is code-golf shortest function or program per language wins.

Standard rules and loopholes apply.

Answer 1

K (ngn/k), 11 bytes

{x/x!+/'x\}

Try it online!

First time writing a curried function in K...

Works exactly like coltim's answer, except for how the function is called. This one is a monadic function that takes the base and returns another monadic function that takes an array and returns the answer. You can call it like

(f 12) 1000 576 23 1 141
f[12][1000 576 23 1 141]

Answer 2

Python 3, 56 bytes

f=lambda I,b:sum(I)and sum(I)%b+b*f([x//b for x in I],b)

Try it online!

Answer 3

Pip, 18 bytes

R($+R*:SgTDa)%aFDa

Takes the base, followed by the integers, as command-line arguments. Try It Online!

Explanation

[This challenge is] a good example of why base-conversion builtins should be little-endian
- ais53

R($+R*:SgTDa)%aFDa
                    a is first command-line arg; g is list of args
       Sg           All but the first command-line argument
         TDa        Convert each to a list of integers representing base-a digits
    R*:             Reverse each list of digits
  $+                Add the lists of digits together itemwise
 (          )%a     Take each digit sum mod a
R                   Reverse again
               FDa  Convert from base-a digits to decimal

Answer 4

R, 42 bytes

`/`=\(I,b)`if`(s<-sum(I),I%/%b/b*b+s%%b,0)

Attempt This Online!

The same approach as other recursive answers.

Renaming the function to / makes I%/%b/b*b evaluate in the correct order (first %/%, then /, then *) and saves a byte compared to f(I%/%b,b)*b.

Answer 5

Jelly, 6 bytes

bUS%Uḅ

Try it online!

b         Convert each to base b
 U        reversed,
  S       sum corresponding digits,
   %      mod b,
    U     reverse back to big-endian,
     ḅ    convert from base b.

a good example of why base-conversion builtins should be little-endian

-- ais523

Incidentally, having to reverse twice only costs one byte due to dyadic chaining rules requiring something between % and ḅ anyways, but in cases like this I'd have to agree that

I like the monadic link rules, but not the dyadic link rules

-- ais523

Answer 6

Charcoal, 19 bytes

ＷΣθ«⊞υι≧÷ηθ»Ｉ↨⮌﹪υηη

Try it online! Link is to verbose version of code. Explanation:

ＷΣθ«

Repeat until the (sum of the) input list is zero.

⊞υι

Push the sum to the predefined empty list.

≧÷ηθ

Vectorised integer divide the input list by the input base in place.

»Ｉ↨⮌﹪υηη

Vectorised modulo the list of sums by the input base, then interpret that as a number in the input base, and output the result. (The Reverse is there because base conversion isn't little-endian as it "should" be...)

Answer 7

Vyxal, 8 bytes

τR∑Ṙ$%¹β

Try it Online!

Answer 8

J, 14 bytes

[#.[|[:+/#.inv

Try it online!

• #.inv base digits
• [:+/ sum elementwise
• [| mod by base
• [#. back to base 10

Answer 9

K (ngn/k), 12 bytes

{y/y!+/'y\x}

Try it online!

• y\x convert list input x to base-y
• +/' sum each "row" of the above
• y! mod the sums by y
• y/ convert back from base-y (to base-10)

Answer 10

JavaScript (ES6),  53  52 bytes

Expects (base)(list).

b=>g=a=>(a=a.map(n=>(s+=n,n/b|0),s=0),s&&s%b+b*g(a))

Try it online!

Or 51 bytes with BigInts:

b=>g=a=>(a=a.map(n=>(s+=n,n/b),s=0n),s&&s%b+b*g(a))

Try it online!

Commented version

b =>            // outer function taking the base b
g = a =>        // inner recursive function taking the list a[]
( a =           // update a[] (and compute the sum at the same time):
  a.map(n =>    //   for each entry n in a[]:
    ( s += n,   //     add n to the sum s
      n / b | 0 //     compute floor(n / b)
    ),          //
    s = 0       //     start with s = 0
  ),            //   end of map()
  s &&          // if the sum is not 0:
    s % b +     //   compute the sum modulo the base
    b * g(a)    //   add the product of the base and the result
)               //   of a recursive call with the updated list

Answer 11

PARI/GP, 34 bytes

b->g(a)=if(a,g(a\b)*b+vecsum(a)%b)

Attempt This Online!

A curried function that takes input as (base)(list).

Answer 12

Desmos, 77 bytes

k=[0...floor(max(log_bl))]
f(l,b)=total([mod(floor(l/b^i).total,b)fori=k]b^k)

Function \$f(l,b)\$ takes in a list of positive integers \$l\$ and a base \$b\$.

Not too sure what little endian big endian is all about so I just did it my own way.

Try It Online!

Try It Online! - Prettified

Answer 13

Wolfram Language (Mathematica), 52 bytes

Total@PadLeft@IntegerDigits@##~Mod~#2~FromDigits~#2&

Try it online!

Input [I, b].

Answer 14

Nibbles, 10 9 bytes (18 nibbles)

Edit: -2 nibbles thanks to bug-fix in nibbles compiler (thanks Darren Smith!) allowing `@ (convert from base) to work correctly on 2d lists

`@@.\`'.$\`@_$%+$_

       .                # Map over 
        $               # the elements of arg1
         \              # reversing
          `@ $          # the digits in base
            _           # arg2.
     `'                 # Now transpose this,
    \                   # reverse it,
   .                    # and map over each list
               +$       # sum
              %  _      # modulo arg2.
`@                      # Finally, convert from base
  @                     # arg2

Answer 15

Haskell, 54 51 bytes

b!l=sum[b^w*mod(sum$map(`div`b^w)l)b|w<-[0..sum l]]

Try it online!

Answer 16

C (gcc), ⁸⁸ 73 bytes

i;s;f(l,b,n)int*l;{for(s=i=0;i<n;l[i++]/=b)s+=l[i];s=s?s%b+b*f(l,b,n):0;}

Try it online!

Inputs a pointer to an array on integers, a base, and the length of the array (because pointer in C carry no length info).
Returns the carry-less sum.

Answer 17

05AB1E, 10 bytes

вí0ζOR¹%¹β

Inputs in the order \$b,\mathcal I\$.

Try it online or verify all test cases.

Explanation:

в          # Convert the values in the second (implicit) input-list to the base of the
           # first (implicit) input-integer as inner lists
 í         # Reverse each inner list
   ζ       # Zip/transpose; swapping rows/columns,
  0        # with 0 as trailing filler digit for unequal length lists
    O      # Sum each inner column-list
     R     # Reverse the list back
      ¹%   # Modulo each value by the first input-base
        ¹β # Convert this list from the first input-base to a base-10 integer
           # (which is output implicitly as result)

Answer 18

Perl 5, 52 bytes

sub f{$b=pop;&sum&&&sum%$b+$b*f((map$_/$b|0,@_),$b)}

Try it online!

sub f {
  $b = pop;                  #extract the base $b from the end of the param list
  &sum                       #&sum returns the sum of the input list @_
                             #since &sub without parens uses @_ as params 
                             #if sum > 0
  &&
  &sum % $b +                #then return last base $b digit of the sum plus
    $b *                     #$b times 
    f( (map$_/$b|0,@_), $b ) #the recursive result for the same list
                             #but with last digit removed from each list elem
                             #else return 0
}

Answer 19

PowerShell Core, 129 bytes

param($n,$b)$r=@{}
$n|%{do{$r[$i++]+=$_}while($_=[Math]::Floor($_/$b))$i=0}
$l=$r.Count
-join($r|% V*|%{"+$_%$b"+"*$b"*--$l})|iex

Try it online!

Answer 20

Prolog (SWI), 76 bytes

I+B+O:-sumlist(I,S),S>0,maplist([A,A//B]>>!,I,Q),Q+B+W,O is S mod B+B*W;O=0.

Try it online!

-3 thanks to Jo King

More interesting, without sumlist or maplist:

Prolog (SWI), 86 bytes

E+H-[H|T]-B-[H//B|Y]:-E-T-B-Y.
0-A-_-A.
I+B+O:-S-I-B-Q,S>0,Q+B+W,O is S mod B+B*W;O=0.

Try it online!

Answer 21

Julia, 35 bytes

i^b=any(i.>0)&&sum(i)%b+b*(i.÷b)^b

Try it online!

Answer 22

Retina 0.8.2, 161 bytes

\d+
$*
{`^([1,]+)(;1+)
$1$2;$1
T`,`_`;.*
^([1,]+;(1+);)\2*
$1
\G((?=.*?;((1)+))\2|1|(,))
$3$4
}`^,+;
;
{`\G(;1+;)|1(?<=(1+);1+)(?=1*;)
$1$2
}`^(;1+;1*);
$1
r`1\G

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

{`
}`

Repeat until all of the input numbers have been reduced to zero.

^([1,]+)(;1+)
$1$2;$1

Duplicate the input list.

T`,`_`;.*

Sum the duplicate copy.

^([1,]+;(1+);)\2*
$1

Reduce it modulo the base.

\G((?=.*?;((1)+))\2|1|(,))
$3$4

Integer divide the list by the base.

^,+;
;

Remove the list if it's zero.

{`\G(;1+;)|1(?<=(1+);1+)(?=1*;)
$1$2
}`^(;1+;1*);
$1

Convert the sums from the input base.

r`1\G

Convert to decimal.

Answer 23

Factor + math.unicode, 72 bytes

:: f ( I b -- n ) I Σ dup 0 > [ b mod I [ b /i ] map b f b * + ] when ;

Try it online!

• :: f ( I b -- n ) ... ; Define a word (function) named \$f\$ that takes two arguments from the data stack and returns one. The double :: as opposed to : enables lexical variables inside the definition.
• I Σ dup 0 > Is the sum of \$I\$ greater than zero?
• [ ... ] when If so, then call [ ... ].
• b mod Take the sum of \$I\$ (which is still on the data stack thanks to dup) modulo \$b\$.
• I [ b /i ] map Divide each number in \$I\$ by \$b\$ (integer results only) and place the result on the data stack.
• b f Call \$f\$ on the above list with the same original base, \$b\$.
• b * Multiply the result of the above call by \$b\$.
• + Add the sum of \$I\$ modulo \$b\$ which is still on the data stack.

Answer 24

Knight, 109 bytes

;=j!=bP;W=xP E++"=x"=j+1j"Ex";=r=m=s 1;Ws;=s=i 0;W<i j;=s+sE+"x"=i+1iE++++"=x"i"/x"i" b";=r+r*m%s b=m*m bO-rT

Try it online!

-1 byte thanks to Aiden Chow

Answer 25

APL (Dyalog Classic), 20 bytes

0{⍺⊥⍺|+/⍵⊤⍨⍺⍴⍨⌈⍺⍟⌈/⍵}

Try it online!

Usage:

      ncarry←{⍺⊥⍺|+/⍵⊤⍨⍺⍴⍨⌈⍺⍟⌈/⍵}
      3 ncarry 13 2 9
21
      12 ncarry 1000 576 23 1 141
1573
      2 ncarry 1000 576 23 1 141
307
      4 ncarry 1 2 3 4 5 6 7 8 9 10
11
      5 ncarry 1 2 3 5 8 13 21 34 55
77