# Recursively concatenated cumulative sums of [N] with M iterations

Take two positive integers N and M and create the concatenated cumulative sums of [N], with M iterations. Output the result of the last iteration.

Definition of the concatenated cumulative sum:

1. Start with a number N and define a sequence X = [N]
2. Append to X the cumulative sums of X
3. Repeat step 2 M times.

The cumulative sum of a vector, X = [x1, x2, x3, x4] is: [x1, x1+x2, x1+x2+x3, x1+x2+x3+x4].

Example with N = 1 and M = 4:

P = the cumulative sum function.

M = 0: [1]
M = 1: [1, 1]                    -  X = [1, P(1)] = [[1], [1]]
M = 2: [1, 1, 1, 2]              -  X = [X, P(X)] = [[1, 1], [1, 2]]
M = 3: [1, 1, 1, 2, 1, 2, 3, 5]  -  X = [X, P(X)] = [[1, 1, 1, 2], [1, 2, 3, 5]]
M = 4: [1, 1, 1, 2, 1, 2, 3, 5, 1, 2, 3, 5, 6, 8, 11, 16]


Note that the first X = [1] is not counted as an iteration. You may choose to take M = 5 for the above example (thus counting X = [1] as one iteration).

This is OEIS A107946

### Test cases:

N = 5, M = 1
5, 5

N = 2, M = 3
2, 2, 2, 4, 2, 4, 6, 10

N = 4, M = 6
4, 4, 4, 8, 4, 8, 12, 20, 4, 8, 12, 20, 24, 32, 44, 64, 4, 8, 12, 20, 24, 32, 44, 64, 68, 76, 88, 108, 132, 164, 208, 272, 4, 8, 12, 20, 24, 32, 44, 64, 68, 76, 88, 108, 132, 164, 208, 272, 276, 284, 296, 316, 340, 372, 416, 480, 548, 624, 712, 820, 952, 1116, 1324, 1596


This is , so shortest code wins. Optional input and output formats.

• It's a bit too late now, but does N really add anything to the problem? It's just a constant factor you multiply the result by. Oct 6 '17 at 11:36

n!m=iterate((++)<*>scanl1(+))[n]!!m


Try it online!

Thanks to H.PWiz for -18 bytes

• tail.scanl(+)0 can be scanl1(+) Oct 6 '17 at 13:03
• @H.PWiz Thanks, I always forget about the *1 versions of scan and fold.
– user45941
Oct 6 '17 at 13:05
• 35 bytes using iterate Oct 6 '17 at 13:16
• In modern Haskell (newer than on TIO) n!m=iterate(id<>scanl1(+))[n]!!m is valid. On TIO it needs import Data.Monoid because <> is not yet in the Prelude.
– Lynn
Sep 5 '21 at 11:11
• In older Haskells, f n=n:f(n++scanl1(+)n) followed by n!m=f[n]!!m saves a byte.
– Lynn
Sep 5 '21 at 11:11

# 05AB1E, 7 bytes

¸IFDηO«


Try it online!

Explanation

¸         # wrap input_1 in a list
IF       # input_2 times do:
D      # duplicate the list
η     # get prefixes of the list
O    # sum the prefixes
«   # concatenate to the current list


# Husk, 98 7 bytes

Thanks to H.PWiz for saving 1 byte.

!¡S+G+;


Try it online!

Uses 1-based M.

### Explanation

      ;     Wrap N in a list to get [N].
¡          Iterate the following function on this list and collect
the results in an infinite list.
S+        Concatenate the current value with...
G+      ...the cumulative sum. We're not using the cumsum built-in ∫
because it prepends a zero.
!           Use M as an index into the infinite list.

• Was my approach too, I'm not sure if it's golfable. Also, I've already suggested for cumsum not to return a leading 0 (something which would save 2 bytes in this case). Oct 6 '17 at 11:51
• Can ot∫ be G+? Oct 6 '17 at 12:21
• @H.PWiz Hmm...the docs seem to be unclear on that (AFAIK "scan" means "reduce" not "cumulative reduce"). Oct 6 '17 at 12:27
• F is reduce G is cumulative reduce Oct 6 '17 at 12:30

# MATL, 6 bytes

:"tYsh


Inputs are M, then N.

### Explanation

:"      % Implicitly input M. Do the following M times
t     %   Implicitly input N the first time. Duplicate
Ys    %   Cumulative sum
h     %   Concatenate horizontally
% Implicitly end loop. Implicitly display stack

• Whaaaaat? I'm sure I've tried that 100 times. I even tried going over to Suever's site to make sure it wasn't some strange error on TIO... I don't understand this at all... Oct 6 '17 at 12:11
• I can't stop thinking about this... I'm absolutely sure I've written those exact characters again and again and tried to run it on two different sites, without success. Since that can't be the case, the only explanation left is that I'm going crazy... This really messes with my head! Oct 6 '17 at 12:38

# Mathematica, 34 bytes

Nest[#~Join~Accumulate@#&,{#},#2]&


Try it online!

# Python 2, 837875716563 60 bytes

def f(n,m):r=n,;exec"s=0\nfor c in r:s+=c;r+=s,\n"*m;print r


Try it online!

Saved 6 8 bytes thanks to Rod
Saved 3 bytes thanks to Erik

• @Rod More thanks :D Oct 6 '17 at 12:10
• You don't need the [:], r is a tuple. Oct 6 '17 at 12:13
• @EriktheOutgolfer, thanks, it's a leftover from when r was a list Oct 6 '17 at 12:15

# Dyalog APL, 12 bytes

{(⊢,+\)⍣⍺⊢⍵}


Takes N on the right side and M on the left. TryAPL here!

Explanation:

{(⊢,+\)⍣⍺⊢⍵}
{          } an anonymous function
(⊢,+\)      a train for a single iteration:
⊢           the right argument
,          concatenated with
+\        the cumulative sum
⍣     repeated
⍺     left argument times
⊢⍵  on the right argument

• Love the explanation. Very clear what's going on. Hard to understand APL otherwise :P Oct 6 '17 at 12:26

# Java (OpenJDK 8), 194181175163134 110 bytes

(n,m)->{int a[]=new int[1<<m],c=1,i;for(a[0]=n;m-->0;)for(n=0;2*n<c;c++)for(i=++n;i-->0;a[c]+=a[i]);return a;}


Try it online!

• 110 bytes: (n,m)->{int a[]=new int[1<<m],c=1,i;for(a[0]=n;m-->0;)for(n=0;2*n<c;c++)for(i=++n;i-->0;a[c]+=a[i]);return a;} Oct 6 '17 at 13:53

# jq, 51 bytes

reduce range(.[1])as$j([.[0]];.+[.[:keys[]+1]|add])  Try it online! done with some help from the #jq IRC channel at libera.chat. returns a nice JSON array. -1 byte from ovs. -7 bytes from Michael Chatiskatzi. • 58 bytes by using slicing and add to calculate the prefix sums – ovs Sep 4 '21 at 16:27 • You can use keys[] instead of range(length). Sep 10 '21 at 21:58 # Dyalog APL, 19 bytes {0=⍺:⍵⋄(⍺-1)∇⍵,+\⍵}  Try it online! Dyadic function, with N on the right and M on the left. { 0=⍺: ⍵ ⍝ if a = 0 return (⍺-1) ∇ ⍵,+\⍵ ⍝ recurse with the array ⍝ joined with its cumsum (+\⍵) }  # R, 46 bytes function(N,M){for(i in 1:M)N=c(N,cumsum(N)) N}  Try it online! # Pyth, 12 bytes L+bsM._byF]E  Try it here. # JavaScript (ES6), 55 54 bytes Takes input in currying syntax (m)(n). m=>g=a=>m--?g([...a=+a?[a]:a,...a.map(x=>s+=x,s=0)]):a  ### Test cases let f = m=>g=a=>m--?g([...a=+a?[a]:a,...a.map(x=>s+=x,s=0)]):a console.log(f(1)(5).join(', ')) console.log(f(3)(2).join(', ')) console.log(f(6)(4).join(', ')) # Jelly, 5 bytes ;+\$¡


Try it online!

Suggested version by Dennis (returns n instead of [n] for singleton arrays).

• W and ⁹ can be removed. Oct 6 '17 at 16:32
• @Dennis I'm afraid the output won't be right then? I thought of it but if I get inputs 1 and 0 I'm afraid I'll be returning 1 instead of [1] if I remove those, and I can't use a full program instead, since its output would still be like that. Oct 6 '17 at 16:34
• 1 is how Jelly displays the array [1]. I see no problem with that. Oct 6 '17 at 16:36
• @Dennis Hmm...a little suspicious to that (as I said on the last part of my comment above)...is there any consensus allowing it, or would it count as "standard loophole abusing datatypes"? Oct 6 '17 at 16:38
• Both formats are ok.
– CG.
Oct 7 '17 at 8:20

## Clojure, 67 bytes

#(loop[c[%]i %2](if(= i 0)c(recur(into c(reductions + c))(dec i))))


# Julia 1.5, 31 bytes

n>m=m<1 ? n : [n;cumsum(n)]>m-1


Try it online!