# 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
Oct 16 '16 at 8:55
• While all answers so far have used the formula, I'm convinced that there are other ways to attack the problem. Oct 16 '16 at 16:13
• Is there a challenge to generate the ascii art output of this sequence? Oct 16 '16 at 18:01
• @miles Not sure. Kinda hard to search for. Oct 16 '16 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) Oct 18 '16 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? Oct 16 '16 at 6:02
• @Jonathan We did, but it caused to many problems with dollar signs in code blocks. Oct 16 '16 at 6:03
• @JonathanAllan There were issues but it was nice for a while 1 2 3 Oct 16 '16 at 6:03
• Vanilla JS is two bytes shorter: n=>(n*n-1<<n-1)+1 Oct 16 '16 at 13:45
• Wait, MathJax doesn't work here? Or why is the equation an image? Oct 17 '16 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? Oct 18 '16 at 13:11
• Found it using J and searching OEIS, then simplified it by hand Oct 18 '16 at 13:12
• I consider my own answer non-competing, so I have accepted this one. Feb 12 '17 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 Nov 4 '16 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. Oct 18 '16 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). Oct 18 '16 at 13:49
• IMHO, It's more readable, and it looks more like the mathematical formula used. Oct 18 '16 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... Oct 18 '16 at 14:01
• I mean nothing about the bounty. The math formula used in this answer. We write "minus 1" as - 1. Oct 18 '16 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! Oct 16 '16 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. Oct 16 '16 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... Oct 16 '16 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). Oct 16 '16 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. Oct 17 '16 at 10:19
• Your quote says a full program or a function. But a macro is neither. Oct 17 '16 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. Oct 17 '16 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. Oct 17 '16 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