# 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, 2017 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, 2017 at 13:03
• @H.PWiz Thanks, I always forget about the *1 versions of scan and fold.
– user45941
Oct 6, 2017 at 13:05
• 35 bytes using iterate Oct 6, 2017 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, 2021 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, 2021 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, 2017 at 11:51
• Can ot∫ be G+? Oct 6, 2017 at 12:21
• @H.PWiz Hmm...the docs seem to be unclear on that (AFAIK "scan" means "reduce" not "cumulative reduce"). Oct 6, 2017 at 12:27
• F is reduce G is cumulative reduce Oct 6, 2017 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, 2017 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, 2017 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, 2017 at 12:10
• You don't need the [:], r is a tuple. Oct 6, 2017 at 12:13
• @EriktheOutgolfer, thanks, it's a leftover from when r was a list Oct 6, 2017 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, 2017 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, 2017 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, 2021 at 16:27 • You can use keys[] instead of range(length). Sep 10, 2021 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, 2017 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, 2017 at 16:34
• 1 is how Jelly displays the array [1]. I see no problem with that. Oct 6, 2017 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, 2017 at 16:38
• Both formats are ok.
– CG.
Oct 7, 2017 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!