# Compute the kangaroo sequence

### Backstory

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.

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 ; 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
• I downvoted because I don't like challenges where a complicated setup comes down to a straightforward formula to golf.
– xnor
Commented Oct 16, 2016 at 8:55
• While all answers so far have used the formula, I'm convinced that there are other ways to attack the problem. Commented Oct 16, 2016 at 16:13
• Is there a challenge to generate the ascii art output of this sequence? Commented Oct 16, 2016 at 18:01
• @miles Not sure. Kinda hard to search for. Commented Oct 16, 2016 at 18:04
• Wolfram Alpha could not find a shorter version, http://www.wolframalpha.com/input/?i=2%5E(n-1)*(n%5E2-1)%2B1 (Weird markup because a regular URL gets messed up) Commented Oct 18, 2016 at 13:59

# 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.

• Why does PPCG not have mathjax? Commented Oct 16, 2016 at 6:02
• @Jonathan We did, but it caused to many problems with dollar signs in code blocks. Commented Oct 16, 2016 at 6:03
• @JonathanAllan There were issues but it was nice for a while 1 2 3 Commented Oct 16, 2016 at 6:03
• Vanilla JS is two bytes shorter: n=>(n*n-1<<n-1)+1 Commented Oct 16, 2016 at 13:45
• Wait, MathJax doesn't work here? Or why is the equation an image? Commented Oct 17, 2016 at 19:20

# Jelly, 6 bytes

²’æ«’‘

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

## Explanation

²’æ«’‘  Input: n
²       Square n
’      Decrement
æ«    Bit shift left by
’     Decrement of n
‘  Increment
• Did you do it by hand, or auto-generate it? Commented Oct 18, 2016 at 13:11
• Found it using J and searching OEIS, then simplified it by hand Commented Oct 18, 2016 at 13:12
• I consider my own answer non-competing, so I have accepted this one. Commented Feb 12, 2017 at 16:33

# Java 7, 35 bytes

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

# Jelly, 4 bytes

ŒḄ¡S

### 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.
• Oh, so that's what bounce does. I wish I'd known that before adding that exact operation to Japt a few days ago :P Commented Nov 4, 2016 at 0:13

# Python 2, 25 23 bytes

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

Used miles's formula.

Thanks to Jonathan Allan for -2 bytes.

• You don't need ~-x. You can use x-1 as well (not any shorter), since subtraction has a higher precedence than shifting. Commented Oct 18, 2016 at 13:45
• @mbomb007 I know, but the code Jonathan Allan gave me used ~-x, so I decided to leave it unchanged. Well, it seems everyone prefers x-1, though (Dennis also said that exact thing). Commented Oct 18, 2016 at 13:49
• IMHO, It's more readable, and it looks more like the mathematical formula used. Commented Oct 18, 2016 at 14:00
• @mbomb007 Oh you mean the very recently added bounty? If so, I changed it. But, I might raise some arguments then... I could have also done -~(x*x-1<<~-x) for the record, but -1 still exists, so I don't like to blend code... Commented Oct 18, 2016 at 14:01
• I mean nothing about the bounty. The math formula used in this answer. We write "minus 1" as - 1. Commented Oct 18, 2016 at 14:21

# 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!

• Welcome to Programming Puzzles and Code Golf! Commented Oct 16, 2016 at 5:43
• s=tonumber(arg[1]) can be swapped out for s=... to save some bytes. ... stores the arg table unpacked, in this case, returns arg[1]. And lua's strings will act like numbers of they only contain a valid number constructor, which we can assume the input is in this case. Commented Oct 16, 2016 at 22:24

# 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)

# 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                []

# 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.
• Only if I didn't need ri... Commented Oct 16, 2016 at 7:18

## 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.

# C, 26 bytes

As a macro:

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

As a function (27):

f(x){return-~(x*x-1<<~-x);}
• The macro version will produce incorrect results if the parameter is an expression. Consider f(1+2). Commented Oct 16, 2016 at 22:30
• @kasperd The parameter will not be an expression. 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. Commented Oct 17, 2016 at 10:19
• Your quote says a full program or a function. But a macro is neither. Commented Oct 17, 2016 at 18:51
• @kasperd Basically, I think it's like a function, but without evaluation. Also, I have provided a "real" function below, if that's what you want. Commented Oct 17, 2016 at 19:38

# 05AB1E, 7 bytes

n<¹<o*>

Try it online!

Explanation

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

# 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
*/
}
}
}

## Batch, 30 bytes

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

Well, it beats Java anyway.

# 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

# 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
• Exponentiation in Dutch is machtsverheffing, that and lack of creativity. Also, a lot of operators haven't been implemented yet, due to lazyness and procrastination. Commented Oct 17, 2016 at 21:13

## 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)

# 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}

# Scala, 23 bytes

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

Uses bit shift as exponentiation

# 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

## R, 26 bytes

Shamelessly applying the formula

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

# 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

# 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]

# 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