Compute the kangaroo sequence
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
, whereT(n)
is the triangle number function (which has the formulaT(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.
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.
Try it online! or Verify all test cases.
Explanation
²’æ«’‘ Input: n
² Square n
’ Decrement
æ« Bit shift left by
’ Decrement of n
‘ Increment
Java 7, 35 bytes
int c(int n){return(n*n-1<<n-1)+1;}