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\$
1
  • 1
    \$\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\$ Oct 6, 2017 at 11:36

16 Answers 16

7
\$\begingroup\$

Haskell, 35 bytes

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

Try it online!

Thanks to H.PWiz for -18 bytes

\$\endgroup\$
7
  • \$\begingroup\$ tail.scanl(+)0 can be scanl1(+) \$\endgroup\$
    – H.PWiz
    Oct 6, 2017 at 13:03
  • \$\begingroup\$ @H.PWiz Thanks, I always forget about the *1 versions of scan and fold. \$\endgroup\$
    – user45941
    Oct 6, 2017 at 13:05
  • 1
    \$\begingroup\$ 35 bytes using iterate \$\endgroup\$
    – H.PWiz
    Oct 6, 2017 at 13:16
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Lynn
    Sep 5, 2021 at 11:11
  • 1
    \$\begingroup\$ In older Haskells, f n=n:f(n++scanl1(+)n) followed by n!m=f[n]!!m saves a byte. \$\endgroup\$
    – Lynn
    Sep 5, 2021 at 11:11
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\$
4
  • \$\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\$ Oct 6, 2017 at 11:51
  • \$\begingroup\$ Can ot∫ be G+? \$\endgroup\$
    – H.PWiz
    Oct 6, 2017 at 12:21
  • \$\begingroup\$ @H.PWiz Hmm...the docs seem to be unclear on that (AFAIK "scan" means "reduce" not "cumulative reduce"). \$\endgroup\$ Oct 6, 2017 at 12:27
  • \$\begingroup\$ F is reduce G is cumulative reduce \$\endgroup\$
    – H.PWiz
    Oct 6, 2017 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\$
2
  • 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\$ Oct 6, 2017 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\$ Oct 6, 2017 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\$
3
  • \$\begingroup\$ @Rod More thanks :D \$\endgroup\$
    – TFeld
    Oct 6, 2017 at 12:10
  • \$\begingroup\$ You don't need the [:], r is a tuple. \$\endgroup\$ Oct 6, 2017 at 12:13
  • \$\begingroup\$ @EriktheOutgolfer, thanks, it's a leftover from when r was a list \$\endgroup\$
    – TFeld
    Oct 6, 2017 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\$
1
  • \$\begingroup\$ Love the explanation. Very clear what's going on. Hard to understand APL otherwise :P \$\endgroup\$
    – Emigna
    Oct 6, 2017 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\$
1
  • 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, 2017 at 13:53
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 58 bytes by using slicing and add to calculate the prefix sums \$\endgroup\$
    – ovs
    Sep 4, 2021 at 16:27
  • \$\begingroup\$ You can use keys[] instead of range(length). \$\endgroup\$ Sep 10, 2021 at 21:58
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\$
5
  • \$\begingroup\$ W and can be removed. \$\endgroup\$
    – Dennis
    Oct 6, 2017 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\$ Oct 6, 2017 at 16:34
  • \$\begingroup\$ 1 is how Jelly displays the array [1]. I see no problem with that. \$\endgroup\$
    – Dennis
    Oct 6, 2017 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\$ Oct 6, 2017 at 16:38
  • \$\begingroup\$ Both formats are ok. \$\endgroup\$
    – CG.
    Oct 7, 2017 at 8:20
0
\$\begingroup\$

Clojure, 67 bytes

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

Julia 1.5, 31 bytes

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

Try it online!

\$\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.