14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Oct 6 '17 at 11:36

14 Answers 14

7
\$\begingroup\$

Haskell, 35 bytes

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

Try it online!

Thanks to H.PWiz for -18 bytes

\$\endgroup\$
  • \$\begingroup\$ tail.scanl(+)0 can be scanl1(+) \$\endgroup\$ – H.PWiz Oct 6 '17 at 13:03
  • \$\begingroup\$ @H.PWiz Thanks, I always forget about the *1 versions of scan and fold. \$\endgroup\$ – Mego Oct 6 '17 at 13:05
  • \$\begingroup\$ 45 bytes \$\endgroup\$ – H.PWiz Oct 6 '17 at 13:10
  • 1
    \$\begingroup\$ 35 bytes using iterate \$\endgroup\$ – H.PWiz Oct 6 '17 at 13:16
  • \$\begingroup\$ I'm just going to leave off the explanation - too much effort to change it every time :P \$\endgroup\$ – Mego Oct 6 '17 at 13:18
6
\$\begingroup\$

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

Husk, 9 8 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.
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Erik the Outgolfer Oct 6 '17 at 11:51
  • \$\begingroup\$ Can ot∫ be G+? \$\endgroup\$ – H.PWiz Oct 6 '17 at 12:21
  • \$\begingroup\$ @H.PWiz Hmm...the docs seem to be unclear on that (AFAIK "scan" means "reduce" not "cumulative reduce"). \$\endgroup\$ – Erik the Outgolfer Oct 6 '17 at 12:27
  • \$\begingroup\$ F is reduce G is cumulative reduce \$\endgroup\$ – H.PWiz Oct 6 '17 at 12:30
5
\$\begingroup\$

MATL, 6 bytes

:"tYsh

Inputs are M, then N.

Try it online! Or verify all test cases.

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
\$\endgroup\$
  • 3
    \$\begingroup\$ 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... \$\endgroup\$ – Stewie Griffin Oct 6 '17 at 12:11
  • 2
    \$\begingroup\$ 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! \$\endgroup\$ – Stewie Griffin Oct 6 '17 at 12:38
3
\$\begingroup\$

Mathematica, 34 bytes

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

Try it online!

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

Python 2, 83 78 75 71 65 63 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

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

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
\$\endgroup\$
  • \$\begingroup\$ Love the explanation. Very clear what's going on. Hard to understand APL otherwise :P \$\endgroup\$ – Emigna Oct 6 '17 at 12:26
2
\$\begingroup\$

Java (OpenJDK 8), 194 181 175 163 134 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!

\$\endgroup\$
  • 2
    \$\begingroup\$ 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;} \$\endgroup\$ – Nevay Oct 6 '17 at 13:53
1
\$\begingroup\$

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 (+\⍵)
}
\$\endgroup\$
1
\$\begingroup\$

R, 46 bytes

function(N,M){for(i in 1:M)N=c(N,cumsum(N))
N}

Try it online!

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

Pyth, 12 bytes

L+bsM._byF]E

Try it here.

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

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(', '))

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

Jelly, 5 bytes

;+\$¡

Try it online!

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

\$\endgroup\$
  • \$\begingroup\$ W and can be removed. \$\endgroup\$ – Dennis Oct 6 '17 at 16:32
  • \$\begingroup\$ @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. \$\endgroup\$ – Erik the Outgolfer Oct 6 '17 at 16:34
  • \$\begingroup\$ 1 is how Jelly displays the array [1]. I see no problem with that. \$\endgroup\$ – Dennis Oct 6 '17 at 16:36
  • \$\begingroup\$ @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"? \$\endgroup\$ – Erik the Outgolfer Oct 6 '17 at 16:38
  • \$\begingroup\$ Both formats are ok. \$\endgroup\$ – CG. Oct 7 '17 at 8:20
0
\$\begingroup\$

Clojure, 67 bytes

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

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.