19
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Ssndbox \$\endgroup\$
    – loopy walt
    Aug 23 at 15:48
  • 1
    \$\begingroup\$ base-conversion and arithmetic tag perhaps \$\endgroup\$
    – Steffan
    Aug 24 at 0:23
  • 1
    \$\begingroup\$ Perhaps number or integer. \$\endgroup\$
    – alephalpha
    Aug 24 at 1:30
  • \$\begingroup\$ May I assume \$n>1\$? \$\endgroup\$
    – tsh
    Aug 24 at 3:39
  • 2
    \$\begingroup\$ Fun fact / example: bitwise XOR is carryless sum in base 2 (binary). Many modern CPUs have instructions for carryless multiply (in binary), which is generates partial products as usual (shifting), but adds then with XOR instead of normal add. e.g. x86 pclmulqdq. Useful for some Galois Field stuff. \$\endgroup\$ Aug 24 at 18:28

25 Answers 25

7
\$\begingroup\$

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]
\$\endgroup\$
2
  • \$\begingroup\$ How do you like K compared with J/APL/BQN? \$\endgroup\$
    – Jonah
    Aug 23 at 23:11
  • 1
    \$\begingroup\$ @Jonah Imo, K is just a different language with a small set of array-y built-ins (and a dict type). I like its relative simplicity, but sometimes the very simplicity (scoping rules, limited function size and number of locals...) trips me up in more complex programs. \$\endgroup\$
    – Bubbler
    Aug 24 at 0:14
5
\$\begingroup\$

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!

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

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
\$\endgroup\$
3
\$\begingroup\$

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.

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

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ "a good example of why base-conversion builtins should be little-endian" - it's not 100% necessary, as we just want the digits to be aligned. Little-endian is just one way to do it. Another is to pad all the results to the same length like in APL/J/K. \$\endgroup\$
    – Bubbler
    Aug 23 at 22:47
  • 1
    \$\begingroup\$ @Bubbler Indeed. And a third option could be for vectorizing operations on uneven lists to align them from the end instead of the start. \$\endgroup\$ Aug 23 at 22:53
2
\$\begingroup\$

Charcoal, 19 bytes

WΣθ«⊞υι≧÷ηθ»I↨⮌﹪υηη

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

WΣθ«

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.

»I↨⮌﹪υηη

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...)

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

Vyxal, 8 bytes

τR∑Ṙ$%¹β

Try it Online!

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

J, 14 bytes

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

Try it online!

  • #.inv base digits
  • [:+/ sum elementwise
  • [| mod by base
  • [#. back to base 10
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 51 bytes: g=(a,b)=>b&&g(a.map(n=>(a=~~a+n,n/b|0)),a&&b)*b+a%b \$\endgroup\$
    – tsh
    Aug 24 at 3:40
  • \$\begingroup\$ @tsh That's a nice refactoring but it would fail when the input list is a singleton. \$\endgroup\$
    – Arnauld
    Aug 24 at 18:12
2
\$\begingroup\$

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).

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

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Little endian and big endian are just whether it's ordered in reverse or not, basically, or where the most significant bit is. en.wikipedia.org/wiki/Endianness \$\endgroup\$
    – Steffan
    Aug 24 at 2:23
2
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

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

Try it online!

Input [I, b].

\$\endgroup\$
3
  • \$\begingroup\$ 43 bytes \$\endgroup\$
    – alephalpha
    Aug 24 at 6:34
  • 2
    \$\begingroup\$ Or 41 bytes with currying \$\endgroup\$
    – alephalpha
    Aug 24 at 6:34
  • \$\begingroup\$ @alephalpha you should post that as your own answer \$\endgroup\$
    – att
    Aug 24 at 7:09
2
\$\begingroup\$

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

enter image description here

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

Haskell, 54 51 bytes

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

Try it online!

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

C (gcc), 88 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.

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

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)
\$\endgroup\$
2
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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!

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

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!

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

Julia, 35 bytes

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

Try it online!

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

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.

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

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.
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ ;=bP;=jF -> ;=j!=bP for -1 bytes. \$\endgroup\$
    – Aiden Chow
    Aug 24 at 2:13
1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ {⍺⊥⍺|+/⍺⊥⍣¯1⊢⍵} (and can further shorten to 12 bytes tacit) \$\endgroup\$
    – att
    Aug 24 at 21:07
  • \$\begingroup\$ @att how can it be shortened to 12 bytes? (⊣⊥⊣|+/⊣⊥⍣¯1) throws an error and is 13 bytes, though this could just be attributed to my massive lack of experience with tacit functions \$\endgroup\$
    – atpx8
    Aug 24 at 23:47
  • \$\begingroup\$ ⊣⊥⊣|(+/⊥⍣¯1) or ⊣⊥⊣⊤1⊥∘⍉⊥⍣¯1 \$\endgroup\$
    – att
    Aug 24 at 23:51

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.