19
\$\begingroup\$

Let's define fn(k) as the sum of the first k terms of the natural numbers [1, ∞) where each number is repeated n times.

k       | 0    1    2    3    4    5    6    7    8    9
--------+-------------------------------------------------
f_1(k)  | 0    1    3    6    10   15   21   28   36   45
deltas  |   +1   +2   +3   +4   +5   +6   +7   +8   +9
--------+-------------------------------------------------
f_2(k)  | 0    1    2    4    6    9    12   16   20   25
deltas  |   +1   +1   +2   +2   +3   +3   +4   +4   +5
--------+-------------------------------------------------
f_3(k)  | 0    1    2    3    5    7    9    12   15   18
deltas  |   +1   +1   +1   +2   +2   +2   +3   +3   +3

The anti-diagonals of this as a square array is similar to OEIS sequence A134546.

Challenge

Write a program/function that takes two non-negative integers n and k and outputs fn(k).

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • Your solution can either be 0-indexed or 1-indexed for n and/or k but please specify which.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

In these test cases, n is 1-indexed and k is 0-indexed.

n   k      fn(k)

1   2      3
2   11     36
11  14     17
14  21     28
21  24     27
24  31     38
31  0      0

In a few better formats:

1 2
2 11
11 14
14 21
21 24
24 31
31 0

1, 2
2, 11
11, 14
14, 21
21, 24
24, 31
31, 0

Reference implementation

This is written in Haskell.

f n k = sum $ take k $ replicate n =<< [1..]

Try it online!

This challenge was sandboxed.

\$\endgroup\$
  • \$\begingroup\$ Do you think that my edit improves formatting, or is it just on my browser? \$\endgroup\$ – user202729 Nov 28 '17 at 10:54
  • \$\begingroup\$ @user202729 Heh... it looks off on my browser but I doubt my formatting looked good on most browsers... I'll just keep it like that, it doesn't lose any meaning. Just looks weird. :P \$\endgroup\$ – totallyhuman Nov 28 '17 at 11:06
  • \$\begingroup\$ Do we need to handle the case f_n(0) = 0 for k 0-indexed? \$\endgroup\$ – Cinaski Nov 28 '17 at 12:41
  • 9
    \$\begingroup\$ "cool untitled sequence thingy" Lol, I'm not the only one having a hard time coming up with names for sequences I made up I see.. ;) \$\endgroup\$ – Kevin Cruijssen Nov 28 '17 at 13:17
  • 3
    \$\begingroup\$ @Fabian No, you only sum the first k terms from the list of repeated natural numbers, not the first n*k terms. \$\endgroup\$ – Martin Ender Nov 28 '17 at 18:53

31 Answers 31

12
\$\begingroup\$

Ruby, 32 28 23 bytes

->n,k{k.step(0,-n).sum}

Try it online!

Explanation

Let's visualize the sum as the area of a triangle, for example with n=3 and k=10:

*
*
*
**
**
**
***
***
***
****

Then we sum by column instead of row: the first column is k, then k-n, k-2n and so on.

\$\endgroup\$
8
\$\begingroup\$

Python 2, 34 28 bytes

lambda n,k:(k+k%n)*(k/n+1)/2

Try it online!

Thanks Martin Ender, Neil and Mr Xcoder for helping.

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't actually need the k/n anyway - k-(k/n)*n is just k%n. See my Batch answer. \$\endgroup\$ – Neil Nov 28 '17 at 12:49
  • \$\begingroup\$ 28 bytes \$\endgroup\$ – Mr. Xcoder Nov 28 '17 at 12:51
  • \$\begingroup\$ Thanks. I didn't think it could get so simple. \$\endgroup\$ – G B Nov 28 '17 at 12:59
8
\$\begingroup\$

Husk, 4 bytes

Σ↑ṘN

Try it online!

Explanation

This just ends up being a direct translation of the reference implementation in the challenge:

   N  Start from the infinite sequence of all natural numbers.
  Ṙ   Replicate each element n times.
 ↑    Take the first k values.
Σ     Sum them.
\$\endgroup\$
5
\$\begingroup\$

APL (Dyalog), 12 10 8 bytes

+/∘⌈÷⍨∘⍳

Try it online!

n on the left, k (0 indexed) on the right.

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 40 bytes

Tr@Sort[Join@@Range@#2~Table~#][[;;#2]]&

Try it online!

Tr[Range@(s=⌊#2/#⌋)]#+#2~Mod~#(s+1)&

Try it online!

Mathematica, 18 bytes

by Martin Ender

Tr@Range[#2,0,-#]&

Try it online!

n~Sum~{n,#2,0,-#}&

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Tr@Range[#2,0,-#]& or n~Sum~{n,#2,0,-#}& using the trick from G B's Ruby answer. \$\endgroup\$ – Martin Ender Nov 28 '17 at 12:11
5
\$\begingroup\$

MATL, 12 11 bytes

:iY"Ys0h1G)

Try it online!

k is 0-indexed. Takes input in reverse order.

Saved 1 byte thanks to @Giuseppe

\$\endgroup\$
5
\$\begingroup\$

Jelly, 5 bytes

Rxḣ³S

One more byte than @Mr.Xcoder's Jelly solution but this is my first ever submission in Jelly and I'm still confused about how the tacitness of Jelly chooses operands so I'm still satisfied. Note the order of the inputs are k then n.

Explanation

Rxḣ³S
R           Range: [1,2,...,k]
 x          Times: repeat each element n times: [1,1,1,2,2,2,...,n,n,n]
  ḣ³        Head: take the first k elements. ³ returns the first argument.
    S       Sum

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 4 bytes

1-indexed

Ḷ:‘S

Try it online! or see a test suite.

\$\endgroup\$
  • \$\begingroup\$ You can do 0 indexing so I think Ḷ:S also works \$\endgroup\$ – dylnan Nov 28 '17 at 18:15
  • \$\begingroup\$ @dylnan Actually I don’t think that’s what 0-indexed means here. I rolled back, and we’ll see \$\endgroup\$ – Mr. Xcoder Nov 28 '17 at 18:23
  • \$\begingroup\$ @dylnan Division by zero is an error. \$\endgroup\$ – Erik the Outgolfer Nov 28 '17 at 19:35
4
\$\begingroup\$

JavaScript (ES6),  24  21 bytes

Takes input in currying syntax (n)(k). Returns false instead of 0.

n=>g=k=>k>0&&k+g(k-n)

Test cases

let f =

n=>g=k=>k>0&&k+g(k-n)

console.log(f(1 )(2 )) // 3
console.log(f(2 )(11)) // 36
console.log(f(11)(14)) // 17
console.log(f(14)(21)) // 28
console.log(f(21)(24)) // 27
console.log(f(24)(31)) // 38

How?

n =>             // main unamed function taking n
  g = k =>       // g = recursive function taking k
    k > 0 &&     // if k is strictly positive:
      k +        //   add k to the final result
      g(k - n)   //   subtract n from k and do a recursive call

This is similar to @GB's Ruby answer.

The challenge describes how to build the 'staircase' from left to right, whereas this recursive function builds it from bottom to top. With n = 2 and k = 11:

staircase

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

Batch, 34 bytes

@cmd/cset/a(%2+%2%%%1)*(%2/%1+1)/2

A closed-form formula that I found. First argument n is 1-indexed, second argument k is 0-indexed.

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

Python 2, 29 bytes

lambda n,k:sum(range(k,0,-n))

Try it online!

Thanks to totallyhuman for -3 bytes!


Python 2, 30 bytes

f=lambda n,k:k>0and k+f(n,k-n)

Try it online!

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

Haskell, 28 bytes

n#k|m<-k`mod`n=sum[m,m+n..k]

Try it online!

An approach I found just by screwing around with some range parameters. Most definitely not the shortest but it's pretty cool how there's so many different approaches.

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

C, 38 34 bytes

Recursive definition.

-4 bytes thanks to Steadybox.

f(n,k){return k--?1+f(n,k)+k/n:0;}

Try it online!


32 bytes by Mr. Xcoder, G B

f(n,k){return(k+k%n)*(k/n+1)/2;}

Try it online!

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

R, 37 33 31 bytes

-6 bytes thanks to Giuseppe

function(n,k)sum(rep(1:k,,k,n))

Try it online!

Nothing fancy. The [0:k] handles the case when k=0.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can get rid of the braces here. If you use the in-order arguments for rep.default, you can get rid of [0:k] by using rep(1:k,,k,n) but then your answer is basically rturnbull's but with base R rather than R + pryr \$\endgroup\$ – Giuseppe Dec 19 '17 at 21:22
  • 1
    \$\begingroup\$ You can still get rid of the braces! {} \$\endgroup\$ – Giuseppe Dec 19 '17 at 23:17
  • \$\begingroup\$ the [0:k] substitution got me and I forgot about the braces :) \$\endgroup\$ – NofP Dec 19 '17 at 23:23
2
\$\begingroup\$

C++, 53 bytes

Just use the formula. n is 1-indexed and k is 0-indexed.

[](int n,int k){return k/n*(k/n+1)/2*n+k%n*(k/n+1);};

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Save a couple of bytes by abusing the ~ operator. [](int n,int k){return-k/n*~(k/n)/2*n-k%n*~(k/n);}; \$\endgroup\$ – ceilingcat Dec 1 '17 at 19:08
2
\$\begingroup\$

J, 13 bytes

1#.]{.(#1+i.)

How it works:

The left argument is n, the right is k.

i. generates a list 0..k-1

1+ adds one to each number of the list, yealding 1,2,...,k

# forms a hook with the above, so n copies of each elements of the list are copied.

]{. take the first n of them

1#. find their sum by base conversion.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I like the hook. \$\endgroup\$ – cole Nov 28 '17 at 18:07
2
\$\begingroup\$

Retina, 29 26 bytes

\d+
$*
(?=.*?(1+)$)\1
$'
1

Try it online! Link includes test cases and header to reformat them to its preferred input (0-indexed k first, 1-indexed n second). I was inspired by @GB's Ruby answer. Explanation:

\d+
$*

Convert to unary.

(?=.*?(1+)$)\1
$'

Match every string of n within k, and replace the match with everything after the match. This is k-n, k-2n, k-3n, but n is also after the match, so you get k, k-n, k-2n etc. This also matches n, which is simply deleted (it's no longer needed).

1

Sum the results and convert back to decimal.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 5 bytes

s%_ES

Try it here!

Port of G B's Ruby answer. A port of my Jelly one would be 6 bytes: +s/Rvz

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 39 bytes

->\n,\k{(0,{|($_+1 xx n)}...*)[^k].sum}

Test it

n and k are both 1 based

Expanded:

-> \n, \k { # pointy block lambda with two parameters 「n」 and 「k」

  ( # generate the sequence

    0,         # seed the sequence (this is why 「k」 is 1-based)

    {          # bare block lambda with implicit parameter 「$_」
      |(       # slip this into outer sequence
        $_ + 1 # the next number
        xx n   # repeated 「n」 times (this is why 「n」 is 1-based)
      )
    }

    ...        # keep doing that until

    *          # never stop

  )[ ^k ]      # get the first 「k」 values from the sequence
  .sum         # sum them
}
\$\endgroup\$
2
\$\begingroup\$

Kotlin, 40 bytes

{n:Int,k:Int->Array(k,{i->i/n+1}).sum()}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Java (OpenJDK 8), 23 bytes

n->k->(k+k%n)*(k/n+1)/2

Try it online!

Port of G B's Python 2 answer.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 9 bytes

FL`}){I£O

Try it online!

Explanation

F           # n times do
 L`         # pop top of stack (initially k), push 1 ... topOfStack
   }        # end loop
    )       # wrap stack in a list
     {      # sort the list
      I£    # take the first k elements
        O   # sum
\$\endgroup\$
1
\$\begingroup\$

Python 2, 44 bytes

f=lambda n,k:sum(sorted(range(1,k+1)*n)[:k])

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2, 38 bytes

lambda n,k:sum(i/n+1for i in range(k))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Clojure, 54 bytes

#(nth(reductions +(for[i(rest(range))j(range %)]i))%2)

2nd argument k is 0-indexed, so (f 14 20) is 28.

\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 13 bytes

+/⎕↑(⍳n)/⍳n←⎕

Prompts for screen input for n and then for k. Index origin = 1.

\$\endgroup\$
1
\$\begingroup\$

Brain-Flak, 78 bytes

(({}<>)<{<>(({})<>){({}[()]<(({}))>)}{}({}[()])}{}<>{}>)({<({}[()])><>{}<>}{})

Try it online!

I'm certain this can be done better, but it's a start.

\$\endgroup\$
1
\$\begingroup\$

Japt, 7 6 bytes

Originally inspired by GB's solution and evolved to a port!

Takes k as the first input and n as the second.

õ1Vn)x

Try it


Explanation

Implicit input of integers U=k & V=n. Generate an array of integers (õ) from 1 to U with a step of V negated (n) and reduce it by addition (x).

\$\endgroup\$
1
\$\begingroup\$

R, 27 bytes

Anonymous function that takes k and n in that order. Creates a list of length k (third argument to rep) that is composed of 1 through k (first argument to rep), repeating each element n times (fourth argument to rep). Then takes the sum of that list.

n is 1-indexed and k is 0-indexed. Returns an error for n<1.

pryr::f(sum(rep(1:k,,k,n)))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Befunge, 27 Bytes

&::00p&:10p%+00g10g/1+*2/.@

Try It Online

Takes k then n as input. Uses G B's answer as its mathematical basis.

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