# Iterated partial sums

The partial sums of a list of integers [a1, a2, a3, ..., an] are

s1 = a1
s2 = a1 + a2
s3 = a1 + a2 + a3
...
sn = a1 + a2 + ... + an

We can then take the list of partial sums [s1, s2, s3, ..., sn] and compute its partial sums again to produce a new list, and so on.

Related: Iterated forward differences

Input:

• A non-empty list of integers
• A positive number of iterations,

Output: Print or return the list of integers that results from taking the partial sums that many times.

Fewest bytes wins. Built-ins are OK even if they outright solve the problem.

Test cases:

f([-3, 4, 7, -1, 15], 1) == [-3, 1, 8, 7, 22]
f([-3, 4, 7, -1, 15], 3) == [-3, -5, 1, 14, 49]


var QUESTION_ID=59192,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/61321/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• Do the arguments need to be in the same order, or can the number of iterations come before the list of numbers? – kirbyfan64sos Oct 22 '15 at 2:06
• @kirbyfan64sos Either order. – xnor Oct 22 '15 at 5:08

# J, 5 bytes

+/\^:


Try it online on J.js.

### How it works

• /\ is an adverb (function that takes a left argument) that cumulatively reduces by its argument.

• Thus +/\ is the cumulative sum verb.

• ^: is the power conjunction; (f ^: n) y applies f a total of n times to y.

• The verb-conjunction train +/\^: forms an adverb that repeats +/\ as many times as specified in its (left) argument.

x (+/\^:) y gets parsed as (x (+/\^:)) y, which is equivalent to executing (+/\^:x) y.

Thanks to @Zgarb for his help with the explanation.

# Mathematica, 19 bytes

Well, if built-ins are okay...

Accumulate~Nest~##&


Defines a function with the same signature as the examples in the challenge. I'm pretty sure, thanks to the long name Accumulate that this will be easily beaten by the golfing languages and the APL-family, though. :)

To elaborate on LegionMammal978's comment for those who don't Mathematica:

## represents a sequence of the function's parameters (which is like a list that automatically "splats" wherever it's inserted, if you're more familiar with that term from your language's of choice). The ~ are syntactic sugar for infix function invocation, so if we call the function with parameters list and n and expand everything, we get:

Accumulate~Nest~##
Nest[Accumulate, ##]
Nest[Accumulate, list, n]


Which happens to be exactly the argument order expected by Nest.

• That's interesting, using infix notation for 3 arguments using SlotSequence... – LegionMammal978 Oct 21 '15 at 1:13

(!!).iterate(scanl1(+))


This defines an anonymous function, invoked as follows:

> let f = (!!).iterate(scanl1(+)) in f [-3,4,7,-1,15] 3
[-3,-5,1,14,49]


Thanks to @nimi for saving 3 bytes.

## Explanation

(!!).                    -- Index by second argument from
iterate(         )  -- the infinite list obtained by iterating
scanl1(+)   -- the partial sums function (left scan by +) to first argument


# APL, 9 8 bytes

{+\⍣⍺⊢⍵}


This defines a dyadic function that accepts the iterations and list as left and right arguments.

Thanks to @NBZ for golfing off 1 byte!

Try it online on TryAPL.

### How it works

• ⍺ and ⍵ are the left and right arguments to the function.

• +\ is cumulative reduce by sum.

• ⍣⍺ repeats the preceding operator ⍺ times.

• ⊢⍵ applies the identity function to ⍵.

This is a shorter way of parsing the code as (+\⍣⍺)⍵ instead of +\⍣(⍺⍵).

In conjunction, we apply +\ a total of ⍺ times to ⍵

• @AlexA.: Then wouldn't +\⍣⎕⊢⎕ be acceptable? (⎕ is like Python input()). – marinus Oct 20 '15 at 21:23
• @marinus Does that actually print outside a REPL? The only desktop interpreters I have would require assigning to ⎕ afterwards. – Dennis Oct 20 '15 at 21:33

# Matlab, 41 bytes

function f(l,n);for i=1:n;l=cumsum(l);end


Quite straightforward. I still think it is quite annoying not having a built in way of making piecewise defined anonymous functions, or anchors in recursions.

Ungolfed:

function f(l,n);
for i=1:n;
l=cumsum(l);
end


# JavaScript (ES6) 38

Surprisingly small using .map recursively

f=(l,n,t=0)=>n?f(l.map(x=>t+=x),n-1):l

function test()
{
var n, v, i = I.value
v = i.match(/\-?\d+/g).map(x=>+x)
n = v.pop()
console.log(v,n)
O.innerHTML = I.value + ' -> ' + f(v,n) + '\n' + O.innerHTML;
}

test()
<input id=I value='[-3, 4, 7, -1, 15], 3'><button onclick="test()">-></button>
<pre id=O></pre>

# K, 7 3 bytes

{y+\/x}


Very similar to the J solution. +\ precisely performs a partial sum, and when / is provided with a monadic verb and an integer left argument it iterates a specified number of times, like a "for" loop. The rest is just wrapping it up neatly to suit the order of arguments.

  {y+\/x}[-3 4 7 -1 15;1]
-3 1 8 7 22
{y+\/x}[-3 4 7 -1 15;3]
-3 -5 1 14 49


Tested in Kona and oK.

## Edit:

If I'm allowed to reverse the arguments, as @kirbyfan64sos determined, I can dispense with the function wrapping entirely:

+\/


Invoked like:

+\/[3;-3 4 7 -1 15]


This works properly in both k2.8 and k5. It doesn't work in oK since that interpreter does not yet support curried (aka "projected") adverbs, and it doesn't appear to work properly in Kona for less clear reasons.

edit: As of a few days ago, the +\/ formulation also works in oK.

• The arguments can be reversed, so I think you may be able to shave a few bytes. – kirbyfan64sos Oct 22 '15 at 13:55
• 3 +\/ -3 4 7 -1 15 works just fine in Kona, but you can't assign it to a function. Weird... – Dennis Oct 22 '15 at 15:10
• Yeah, Kona is clearly not treating 3+\/-3 4 7 -1 15 the same as +\/[3;-3 4 7 -1 15]- makes me wonder if they handle the former as a special syntactic case. – JohnE Oct 22 '15 at 15:18

# Pyth, 9 bytes

usM._GvwQ


Try it online: Demonstration or Test Suite

### Explanation

usM._GvwQ  implicit: Q = input list
vw   input number
u       Q  repeat the following instruction ^ times to G = Q
._G        sequence of prefixes of G
sM           sum them up


# Julia, 29 bytes

f(x,y)=y>0?f(cumsum(x),y-1):x


This really doesn't need much explanation. It's a recursive function, if y==0 then just output x. Otherwise decrement y, perform a cumsum, and recurse. Probably not the most golfed possible Julia solution, I'm still working on it.

# Labyrinth, 73 bytes

;?
,"
;
#
#;}=
;  #
"#;(
_  ;={()"
#;; ( { "
; { !\(@
+=( =
" " "
":{:"


It's been a while since I answered something in Labyrinth, and this seemed doable. :)

Input format is a flat list with the number of iterations first (and then the list to apply the partial sums to). Delimiters don't matter all, as long as there is no character after the last integer, so you can use something readable like:

3 | -3, 4, 7, -1, 15


Output is newline-separated:

-3
-5
1
14
49


# R, 75 bytes

It's long but a different take...computing the desired sequence directly instead of cumulative sums:

function(x,n)sapply(1:length(x),function(i)sum(x[1:i]*choose(i:1+n-2,n-1)))


Noting that the coefficients of the terms of xi for cumsum^n(x) are diagonals of Pascal's triangle. i.e.

cumsum^3(x) = choose(2,2) * x1, choose(3,2) * x1 + choose(2,2) *x2, choose(4,2) * x1 + choose(3,2) * x2 + choose(2,2) * x3, ....


edit: to make a function

# Python 2, 67

This uses the same summation as Anthony Roitman, and the same recursion as Morgan Thrapp.

f=lambda l,n:f([sum(l[:i+1])for i in range(len(l))],n-1)if n else l


I developed this solution before I saw theirs, and then it just seemed easier to post it as an answer rather than a comment to either or both of them.

## Python, 1139389 76 bytes

def f(l,n):
for i in[0]*n:l=[sum(l[:j+1])for j in range(len(l))];
print(l)


It works for both of the test cases. Thanks to Status, Morgan Thrapp, and Ruth Franklin for helping me golf the program down to 93, 89, and 76 bytes respectively.

• You can cut out a number of bytes by changing the second loop into a list comprehension. That is, k=[sum(l[:j+1])for j in range(len(l))]. Then with ;k=l tacked on the end of that you can push this all onto one line with the for i loop. – Status Oct 21 '15 at 3:02
• You can move the k=[sum(l[:j+1])for j in range(len(l))];l=k onto the same line as the for loop to save 2 bytes and remove the space between f's arguments to save another byte. – Morgan Thrapp Oct 21 '15 at 14:47
• As you don't use the value of i, you can replace for i in range(n) with for i in[0]*n (because all you care about is the length not the elements of the list). And I think you can do it without using the auxiliary list k, just modifying the argument l. – Ruth Franklin Oct 21 '15 at 22:26

# Gol><> 0.3.10, 22 bytes

SI
C>rFlMF:}+
NRl<C}<;


The first integer is taken to be the iteration number and the rest make up the list. The final list is outputted newline-separated.

The language is still quite young and unstable, but since I'm pretty set on these operators I thought it'd be okay.

### Explanation

SI            Read integer, moving down on EOF (first line runs as loop)
r             Reverse stack, putting iteration number on top

[outer loop]
F             Do #(iterations) times

[inner loop]
lMF           Do #(length of stack - 1) times
:             Duplicate top of stack
}             Rotate stack rightward (top goes to bottom)
+             Add the top two elements of the stack
C             Continue inner loop, moving down from F when loop is over

}             Rotate once more
C             Continue outer loop, moving down from F when loop is over

lRN           Print stack as (num + newline)
;             Halt


To see why this works, let's try a small example [5 2 1]:

[5 2 1] -- : --> [5 2 1 1] -- } -->  [1 5 2 1]  -- + --> [1 5 3]
[1 5 3] -- : --> [1 5 3 3] -- } -->  [3 1 5 3]  -- + --> [3 1 8]

-- } --> [8 3 1]


## Python, 52 bytes

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l


A recursive function that recurses both on the list l and the number of iterations n. Let's break it down.

First, let's consider a recursive function g that iterated the partial sum just once.

g=lambda l:l and g(l[:-1])+[sum(l)]


For an empty list l, this returns l itself, the empty list. Otherwise, the last entry of the partial sums of l is the overall sum of l, which is appended to the recursive result for all but the last element of l.

Now, let's look at a function f that applies g for n iterations.

f=lambda l,n:n and f(g(l),n-1)or l


When n is 0, this returns the list l unchanged, and otherwise, applies g once, then calls f recursively with one fewer iteration remaining.

Now, let's look again at the actual code, which combines the two recursions into a single function. The idea is to treat g(l) as the special case f(l,1).

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l


We took f(g(l),n-1) from the previous definition, expanded g(l) into g(l[:-1])+[sum(l)], and then replaced g(_) with f(_,1) to confined the recursive calls to f.

For the base case, we want to return l whenever n==0 or l==[]. We combine these by noting that either one makes n*l be the empty list, which is Falsy. So, we recurse whenever n*l is non-empty, and return l otherwise.

Even though there are two recursive calls to f, this does not cause an exponential blow-up the recursive definition of the Fibonacci numbers, but remains quadratic.

# C++ (61 + 17 = 78 bytes)

#include<numeric>
void f(int*a,int*e,int n){for(;n--;)std::partial_sum(a,e,a);}


Test case:

#include <iostream>
#include <iterator>

int main() {
int a[] { -3, 4, 7, -1, 15 };
f(a, std::end(a), 3);
for (auto i : a)
std::cout << i << " ";
}


This takes a slight liberty with the specification: it uses a C-style array, passing pointers to the beginning and end of the array. Internally, as you can see, it's only an extremely thin wrapper around the std::partial_sum in the standard library. Rather than actually return the resulting value, it just modifies the array that's passed in.

If we don't mind pushing definitions of things to the limit (and, arguably, a bit beyond) we can define a "function" in a lambda expression:

#include<numeric>
#include <iostream>
#include <iterator>

int main() {
int a[] { -3, 4, 7, -1, 15 };
int *e = std::end(a);
int n=3;

auto f=[&]{for(;n--;)std::partial_sum(a,e,a);};

f();
for (auto i : a)
std::cout << i << " ";
}


This reduces the definition of the function(-like object) to this piece:

[&]{for(;n--;)std::partial_sum(a,e,a);};


...for 40 bytes (+17 for the #include).

• Wau, I didn't expect of STL to have alg for counting partial sums. – Zereges Oct 23 '15 at 8:52
• @Zereges: Nobody expects the Spanish Inquisit....oh, wait, we're doing C++, not Python. My apologies. – Jerry Coffin Oct 23 '15 at 12:52

# Jelly, 3 bytes

SƤ¡


Try it online!

This is my (Mr Xcoder's) method.

# Jelly, 3 bytes

+\¡


Try it online!

This is caird coinheringaahing's solution.

# Jelly, 2 bytes

Ä¡


Try it online!

### Method #1

SƤ¡  - Full program, dyadic.

¡  - Apply repeatedly, N times.
Ƥ   - Map the preceding link over the prefixes of the list.
S    - Sum.
- Output implicitly


### Method #2

+\¡  - Full program, dyadic.

¡  - Apply repeatedly, N times.
\   - Cumulative reduce by:


### Method #3

Ä¡  - Full program, dyadic.

¡  - Apply repeatedly, N times.
Ä   - Cumulative sums.


# CJam, 13 bytes

q~{{1$+}*]}*p  Test it here. ## Haskell, 52 47 bytes First ever code golf 'attempt', and I'm very much a Haskell beginner, so comments are gladly welcomed! It was not clear in the question as to any necessary format of the function call, or whether it was taken by an argument to the program, so I used the exclamation mark as the function identifier to save a couple of spaces. 0!a=a i!a=(i-1)![sum$take j a|j<-[1..length a]]


Usage (GHCi):

$ghci partialsums.hs GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( partialsums.hs, interpreted ) Ok, modules loaded: Main. *Main> 1![-3, 4 ,7 ,-1 ,15] [-3,1,8,7,22] *Main> 3![-3, 4 ,7 ,-1 ,15] [-3,-5,1,14,49]  • Welcome to code golf! It's usually shorter to pattern match than to use guards, like 0!a=a i!a=.... – xnor Oct 20 '15 at 20:41 • Thanks @xnor - I had previously used 'xs' when building the initial code and must have missed it out when I modified the code in the post. Edited. – Jake Oct 20 '15 at 20:41 • For sum(take j a), you can avoid parens by doing sum$take j a, using the high precedence of $. – xnor Oct 20 '15 at 20:46 • Thank you for your help! I was, for some reason, under the impression that $ would take precedence over syntax (and try to evaluate the rest of the line as it stands). Of course, that wouldn't even make sense. – Jake Oct 20 '15 at 20:49

## R, 41 bytes

function(x,n){for(i in 1:n)x=cumsum(x);x}


# C#, 52 + 85 = 148 137 bytes

using E=System.Collections.Generic.IEnumerable<int>;


and

E I(E s,int i){int t=0;return i<1?s:I(System.Linq.Enumerable.Select(s,v=>t+=v),i-1);}


It uses unorthodox practices (v=>t+=v), but this is PPCG. Also note the stack depth constraint.

# Python 3, 73

Could probably be golfed down a bit further.

def f(n,i):
p=0;c=[]
for m in n:p+=m;c+=[p]
f(c,i-1)if i else print(n)


This version uses numpy, which feels a little like cheating, but here it is:

# Python 3 (with numpy), 72

from numpy import*
def f(n,i):
if i:c=cumsum(n);f(c,i-1)
else:print(n)


# C++14, 102103 94 + 17 (include) = 111 bytes

#include<vector>
auto f(std::vector<int>a,int n){for(;n--;)for(int i=0;i<a.size()-1;++i)a[i+1]+=a[i];return a;}


Ungolfed, with test case

#include <vector>
#include <iostream>

auto f(std::vector<int> a, int n)
{
for (; n--;)
for (int i = 0; i < a.size() - 1; ++i)
a[i + 1] += a[i];
return a;
}

int main()
{
auto t = f({-3, 4, 7, -1, 15}, 3);
for (int i : t)
std::cout << i << " ";
}


Relies on order of evaluation. Not sure if it is UB or not, but works It's compiler dependent, so I changed it.

• Instead of counting j up from 0 to n, count n down to 0. Gives 97 bytes by my count. – Jerry Coffin Oct 23 '15 at 3:56
• @JerryCoffin Thanks.. – Zereges Oct 23 '15 at 8:49

# Octave, 24 bytes

@(l,n)l*triu(0*l'*l+1)^n


## Burlesque, 10 bytes

{q++pa}jE!


it's not very efficient in general but it does the trick.

blsq ) {-3 4 7 -1 15} 1 {q++pa}jE!
{-3 1 8 7 22}
blsq ) {-3 4 7 -1 15} 3 {q++pa}jE!
{-3 -5 1 14 49}


# C++14, 67 bytes

As unnamed lambda modifying its input, requiring c as a random-access-container like vector<int>.

[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}


# 05AB1E, 4 bytes (Probably non-competing)

F.pO

F    # Implicitly take first input and loop n times.
.p  # Generate prefixes of input.
O # Sum all prefixes (implicitly vectorized).


Try it online!

# Husk, 4 3 bytes

Saved 1 byte thanks to Dominic Van Essen

!¡∫


Try it online!

!¡∫
¡   Repeatedly apply the following function to the first argument, making an infinite list
∫  Cumulative sum (one cycle)
!    Index into this list with the second argument

• 3 bytes... – Dominic van Essen Jan 23 at 0:15
• @DominicvanEssen Nice! Husk seems to have a function for everything. – Redwolf Programs Jan 23 at 0:16
• You spelt Mathematica wrong – Razetime Jan 23 at 4:24
• @Razetime Sorry, is "Husk seems to have a function for Mathematica" better? – Redwolf Programs Jan 23 at 21:33

# Lua (67 bytes)

function x(t,n)return load("return "..table.concat(t,"+",1,n))()end


Explanation:

table.concat(t,"+",1,n) gives the string formed by concatenation of elements of t from 1 to n using + as connector, i.e. t[1]+...+t[n].

load(<string>)(), as its name suggests, loads a string to be executed as a function. In this case, a function with zero arguments given by table.concat.

Axiom 213 47 bytes

m(a,b)==(for i in 1..b repeat a:=scan(+,a,0);a)


ungolf and some example

 (3) -> [m([-3,4,7,-1,15],1), m([-3,4,7,-1,15],3)]
Compiling function l with type List Integer -> List Integer
Compiling function m with type (List Integer,Integer) -> List
Integer

(3)  [[- 3,1,8,7,22],[- 3,- 5,1,14,49]]
Type: List List Integer