Compute the kangaroo sequence

Question

Backstory

^{Disclaimer: May contain made up information about kangaroos.}

Kangaroos traverse several stages of development. As they grow older and stronger, they can jump higher and longer, and they can jump more times before they get hungry.

In stage 1, the kangaroo is very little and cannot jump at all. Despite this, is constantly requires nourishment. We can represent a stage 1 kangaroo's activity pattern like this.

o

In stage 2, the kangaroo can make small jumps, but not more than 2 before it gets hungry. We can represent a stage 2 kangaroo's activity pattern like this.

 o o
o o o

After stage 2 the kangaroo improves quickly. In each subsequent stage, the kangaroo can jump a bit higher (1 unit in the graphical representation) and twice as many times. For example, a stage 3 kangaroo's activity pattern looks like this.

  o   o   o   o
 o o o o o o o o
o   o   o   o   o

All that jumping requires energy, so the kangaroo requires nourishment after completing each activity pattern. The exact amount required can be calculated as follows.

1. Assign each o in the activity pattern of a stage n kangaroo its height, i.e., a number from 1 to n, where 1 corresponds to the ground and n to the highest position.

2. Compute the sum of all heights in the activity pattern.

For example, a stage 3 kangaroo's activity pattern includes the following heights.

  3   3   3   3
 2 2 2 2 2 2 2 2
1   1   1   1   1

We have five 1's, eight 2's, and four 3's; the sum is 5·1 + 8·2 + 4·3 = 33.

Task

Write a full program or a function that takes a positive integer n as input and prints or returns the nutritional requirements per activity of a stage n kangaroo.

This is code-golf; may the shortest answer in bytes win!

Examples

 1 ->     1
 2 ->     7
 3 ->    33
 4 ->   121
 5 ->   385
 6 ->  1121
 7 ->  3073
 8 ->  8065
 9 -> 20481
10 -> 50689

Answer 1

Coffeescript, 19 bytes

(n)->(n*n-1<<n-1)+1

Edit: Thanks to Dennis for chopping off 6 bytes!

The formula for generating Kangaroo numbers is this:

Explanation of formula:

The number of 1's in K(n)'s final sum is 2^(n - 1) + 1.

The number of n's in K(n)'s final sum is 2^(n - 1), so the sum of all the n's is n * 2^(n - 1).

The number of any other number (d) in K(n)'s final sum is 2^n, so the sum of all the d's would be d * 2^n.

• Thus, the sum of all the other numbers = (T(n) - (n + 1)) * 2^n, where T(n) is the triangle number function (which has the formula T(n) = (n^2 + 1) / 2).

  Substituting that in, we get the final sum

    (((n^2 + 1) / 2) - (n + 1)) * 2^n
  = (((n + 1) * n / 2) - (n + 1)) * 2^n
  = ((n + 1) * (n - 2) / 2) * 2^n
  = 2^(n - 1) * (n + 1) * (n - 2)
  

When we add together all the sums, we get K(n), which equals

  (2^(n - 1) * (n + 1) * (n - 2)) + (2^(n - 1) + 1) + (n * 2^(n - 1))
= 2^(n - 1) * ((n + 1) * (n - 2) + n + 1) + 1
= 2^(n - 1) * ((n^2 - n - 2) + n + 1) + 1
= 2^(n - 1) * (n^2 - 1) + 1

... which is equal to the formula above.

Answer 2

Jelly, 6 bytes

²’æ«’‘

Uses the formula (n² - 1) 2^{n - 1} + 1 to compute each value. @Qwerp-Derp's was kind enough to provide a proof.

Try it online! or Verify all test cases.

Explanation

²’æ«’‘  Input: n
²       Square n
 ’      Decrement
  æ«    Bit shift left by
    ’     Decrement of n
     ‘  Increment

Answer 3

Java 7, 35 bytes

int c(int n){return(n*n-1<<n-1)+1;}

Answer 4

Jelly, 4 bytes

ŒḄ¡S

Try it online! or verify all test cases.

How it works

ŒḄ¡S  Main link. Argument: n (integer)

ŒḄ    Bounce; turn the list [a, b, ..., y, z] into [a, b, ..., y, z, y, ..., b, a].
      This casts to range, so the first array to be bounced is [1, ..., n].
      For example, 3 gets mapped to [1, 2, 3, 2, 1].
  ¡   Call the preceding atom n times.
      3 -> [1, 2, 3, 2, 1]
        -> [1, 2, 3, 2, 1, 2, 3, 2, 1]
        -> [1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1]
   S  Compute the sum.

Answer 5

Python 2, 25 23 bytes

lambda x:(x*x-1<<x-1)+1

Used miles's formula.

Thanks to Jonathan Allan for -2 bytes.

Answer 6

Lua, 105 bytes

s=tonumber(arg[1])e=1 for i=1,s>1 and 2^(s-1)or 0 do e=e+1 for j=2,s-1 do e=e+j*2 end e=e+s end print(e)

De-golfed:

stage = tonumber(arg[1])
energy = 1
for i = 1, stage > 1 and 2 ^ (stage - 1) or 0 do
    energy = energy + 1
    for j = 2, stage - 1 do
        energy = energy + j * 2
    end
    energy = energy + stage
end
print(energy)

Entertaining problem!

Answer 7

Actually, 8 bytes

;²D@D╙*u

Try it online!

Explanation:

This simply computes the formula (n**2 - 1)*(2**(n-1)) + 1.

;²D@D╙*u
;         duplicate n
 ²        square (n**2)
  D       decrement (n**2 - 1)
   @      swap (n)
    D     decrement (n-1)
     ╙    2**(n-1)
      *   product ((n**2 - 1)*(2**(n-1)))
       u  increment ((n**2 - 1)*(2**(n-1))+1)

Answer 8

GolfScript, 11 bytes

~.2?(2@(?*)

Try it online!

Thanks Martin Ender (8478) for removing 4 bytes.

Explanation:

            Implicit input                 ["A"]
~           Eval                           [A]
 .          Duplicate                      [A A]
  2         Push 2                         [A A 2]
   ?        Power                          [A A^2]
    (       Decrement                      [A A^2-1]
     2      Push 2                         [A A^2-1 2]
      @     Rotate three top elements left [A^2-1 2 A]
       (    Decrement                      [A^2-1 2 A-1]
        ?   Power                          [A^2-1 2^(A-1)]
         *  Multiply                       [(A^2-1)*2^(A-1)]
          ) Increment                      [(A^2-1)*2^(A-1)+1]
            Implicit output                []

Answer 9

CJam, 11 bytes

ri_2#(\(m<)

Try it Online.

Explanation:

r           e# Get token.       ["A"]
 i          e# Integer.         [A]
  _         e# Duplicate.       [A A]
   2#       e# Square.          [A A^2]
     (      e# Decrement.       [A A^2-1]
      \     e# Swap.            [A^2-1 A]
       (    e# Decrement.       [A^2-1 A-1]
        m<  e# Left bitshift.   [(A^2-1)*2^(A-1)]
          ) e# Increment.       [(A^2-1)*2^(A-1)+1]
            e# Implicit output.

Answer 10

Mathematica, 15 bytes

(#*#-1)2^#/2+1&

There is no bitshift operator, so we need to do the actual exponentiation, but then it's shorter to divide by 2 instead of decrementing the exponent.

Answer 11

C, 26 bytes

As a macro:

#define f(x)-~(x*x-1<<~-x)

As a function (27):

f(x){return-~(x*x-1<<~-x);}

Answer 12

05AB1E, 7 bytes

n<¹<o*>

Try it online!

Explanation

n<        # n^2
     *    # *
  ¹<o     # 2^(n-1)
      >   # + 1

Answer 13

C#, 18 bytes

n=>(n*n-1<<n-1)+1;

Anonymous function based on Qwerp-Derp's excellent mathematical analysis.

Full program with test cases:

using System;

namespace KangarooSequence
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int,int>f= n=>(n*n-1<<n-1)+1;

            //test cases:
            for (int i = 1; i <= 10; i++)
                Console.WriteLine(i + " -> " + f(i));
            /* will display:
            1 -> 1
            2 -> 7
            3 -> 33
            4 -> 121
            5 -> 385
            6 -> 1121
            7 -> 3073
            8 -> 8065
            9 -> 20481
            10 -> 50689
            */
        }
    }
}

Answer 14

Batch, 30 bytes

@cmd/cset/a"(%1*%1-1<<%1-1)+1"

Well, it beats Java anyway.

Answer 15

MATL, 7 bytes

UqGqW*Q

Uses the formula from other answers.

Try it online!

U    % Implicit input. Square
q    % Decrement by 1
G    % Push input again
q    % Decrement by 1
W    % 2 raised to that
*    % Multiply
Q    % Increment by 1. Implicit display 

Answer 16

Oasis, 9 bytes

2n<mn²<*>

I'm surprised there isn't a built-in for 2^n.

Try it online!

Explanation:

2n<m        # 2^(n-1) (why is m exponentiation?)
    n²<     # n^2-1
       *    # (2^(n-1))*(n^2-1)
        >   # (2^(n-1))*(n^2-1)+1

Answer 17

Racket 33 bytes

Using formula explained by @Qwerp-Derp

(+(*(expt 2(- n 1))(-(* n n)1))1)

Ungolfed:

(define (f n)
  (+ (*(expt 2
            (- n 1))
      (-(* n n)
        1))
    1))

Testing:

(for/list((i(range 1 11)))(f i))

Output:

'(1 7 33 121 385 1121 3073 8065 20481 50689)

Answer 18

Ruby, 21 bytes

@Qwerp-Derp basically did the heavy lifting.

Because of the precedence in ruby, it seems we need some parens:

->(n){(n*n-1<<n-1)+1}

Answer 19

Scala, 23 bytes

(n:Int)=>(n*n-1<<n-1)+1

Uses bit shift as exponentiation

Answer 20

Pyth, 8 bytes

h.<t*QQt

pyth.herokuapp.com

Explanation:

     Q   Input
      Q  Input
    *    Multiply
   t     Decrement
       t Decrement the input
 .<      Left bitshift
h        Increment

Answer 21

R, 26 bytes

Shamelessly applying the formula

n=scan();2^(n-1)*(n^2-1)+1

Answer 22

J, 11 bytes

1-<:2&*1-*:

Based on the same formula found earlier.

Try it online!

Explanation

1-<:2&*1-*:  Input: integer n
         *:  Square n
       1-    Subtract it from 1
  <:         Decrement n
    2&*      Multiply the value 1-n^2 by two n-1 times
1-           Subtract it from 1 and return

Answer 23

Groovy (22 Bytes)

{(it--**2-1)*2**it+1}​

Does not preserve n, but uses the same formula as all others in this competition. Saved 1 byte with decrements, due to needed parenthesis.

Test

(1..10).collect{(it--**2-1)*2**it+1}​

[1, 7, 33, 121, 385, 1121, 3073, 8065, 20481, 50689]

Answer 24

JS-Forth, 32 bytes

Not super short, but it's shorter than Java. This function pushes the result onto the stack. This requires JS-Forth because I use <<.

: f dup dup * 1- over 1- << 1+ ;

Try it online