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

• xnor: I downvoted because I don't like challenges where a complicated setup comes down to a straightforward formula to golf.
• Dennis: While all answers so far have used the formula, I'm convinced that there are other ways to attack the problem.
• miles: Is there a challenge to generate the ascii art output of this sequence?
• Dennis: @miles Not sure. Kinda hard to search for.
• Konijn: 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)

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:

enter image description here

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.

• Jonathan Allan: Why does PPCG not have mathjax?
• Dennis: @Jonathan We did, but it caused to many problems with dollar signs in code blocks.
• miles: @JonathanAllan There were issues but it was nice for a while 1 2 3
• ETHproductions: Vanilla JS is two bytes shorter: n=>(n*n-1<<n-1)+1
• user60199: Wait, MathJax doesn't work here? Or why is the equation an image?

Answer 2

Jelly, 6 bytes

2’æ«’‘

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

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

• Erik the Outgolfer: Did you do it by hand, or auto-generate it?
• miles: Found it using J and searching OEIS, then simplified it by hand
• Dennis: I consider my own answer non-competing, so I have accepted this one.

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.

• ETHproductions: 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

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.

• mbomb007: You don't need ~-x. You can use x-1 as well (not any shorter), since subtraction has a higher precedence than shifting.
• Erik the Outgolfer: @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).
• mbomb007: IMHO, It's more readable, and it looks more like the mathematical formula used.
• Erik the Outgolfer: @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...
• mbomb007: I mean nothing about the bounty. The math formula used in this answer. We write "minus 1" as - 1.

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!

• Erik the Outgolfer: Welcome to Programming Puzzles and Code Golf!
• ATaco: 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.

Answer 7

Actually, 8 bytes

;2D@D╙*u

Try it online!

Explanation:

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

;2D@D╙*u
; duplicate n
 2 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.

• Erik the Outgolfer: Only if I didn't need ri...

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);}

• kasperd: The macro version will produce incorrect results if the parameter is an expression. Consider f(1+2).
• Erik the Outgolfer: @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.
• kasperd: Your quote says a full program or a function. But a macro is neither.
• Erik the Outgolfer: @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.

Answer 12

05AB1E, 7 bytes

n<1<o*>

Try it online!

Explanation

n< # n^2
 * # *
 1<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<mn2<*>

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?)
 n2< # n^2-1
 * # (2^(n-1))*(n^2-1)
 > # (2^(n-1))*(n^2-1)+1

• Adnan: 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.

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