1

We're given an exercise for a programming lesson. It goes like this:

Starts with an array, ranging from $1$ to $n$. At every iteration, add $2$ neighboring numbers together. Stop when the amount of numbers in the array reaches $1$.

Here's a visual representation:

1  2  3  4  5
 \/ \/ \/ \/
 3  5  7  9
  \/ \/ \/
  8  12 16
   \/  \/
   20  28
    \  /
     48

The problem is, doing this step by step took way too much time, especially when we have to deal with $n = 2018201820182018$. So, is there a way to calculate the final number without doing the addition?

EDIT: We're allowed to do a modulus of the answer with $10^9$, and I've found a formula for calculating the final number: $(n+1) * 2^{(n-2)}$, but the latter part still gives a very large result. Are there any other formulas?

Kurumi Gaming
  • 187
  • What if you put variables, $a_1,\ldots,a_5$ in that example in place of $1,\ldots,5$? – Angina Seng Aug 10 '18 at 16:13
  • what do you mean? i don't quite understand it, sorry – Kurumi Gaming Aug 10 '18 at 16:16
  • The good thing about modulus is that it behaves well under addition and multiplication. You can try iteratively multiplying by 2 and taking the modulus instead of calculating the immensely large power and then taking the modulus. – Sergey Guminov Aug 10 '18 at 16:32
  • 1
    I believe there is no need for another formula, $(n+1) \cdot 2^{n-2}$ is simple enough. To compute it in reasonable time, use https://en.wikipedia.org/wiki/Exponentiation_by_squaring, and to avoid dealing with large numbers, apply modulo $10^9$ to intermediate results. – buj Aug 10 '18 at 16:36
  • Thanks, will try it out later. – Kurumi Gaming Aug 11 '18 at 07:17
  • It works, thanks! :) – Kurumi Gaming Aug 11 '18 at 08:03

1 Answers1

1

This is more like a long comment than an answer.

If you take Lord Shark's advice and set $a_1=1$, $a_2=2$, $a_3=3$, $a_4=4$, and $a_5=5$, and then express every other number in your example in terms of $a_1$, $a_2$, $a_3$, $a_4$, and $a_5$, an interesting and familiar pattern emerges.

We start out pretty simply: \begin{align} 3&=a_1+a_2 \\ 5&=a_2+a_3 \\ 7&=a_3+a_4 \\ 9&=a_4+a_5 \end{align} The next step is where we start to see the pattern: \begin{align} 8&=(a_1+a_2)+(a_2+a_3)=\color{red}1a_1+\color{red}2a_2+\color{red}1a_3 \\ 12&=(a_2+a_3)+(a_3+a_4)=\color{red}1a_2+\color{red}2a_3+\color{red}1a_4 \\ 16&=(a_3+a_4)+(a_4+a_5)=\color{red}1a_3+\color{red}2a_4+\color{red}1a_5 \end{align} And it becomes even clearer in the last two steps: \begin{align} 20&=(a_1+2a_2+a_3)+(a_2+2a_3+a_4)=\color{red}1a_1+\color{red}3a_2+\color{red}3a_3+\color{red}1a_4 \\ 28&=(a_2+2a_3+a_4)+(a_3+2a_4+a_5)=\color{red}1a_2+\color{red}3a_3+\color{red}3a_4+\color{red}1a_5 \end{align} \begin{align} 48=(a_1+3a_2+3a_3+a_4)+(a_2+3a_3+3a_4+a_5)=\color{red}1a_1+\color{red}4a_2+\color{red}6a_3+\color{red}4a_4+\color{red}1a_5 \end{align} See those coefficients? I think the binomial theorem might come in handy.

Robert Howard
  • 2,753
  • 1
    Yeah I also noticed the similarity between this and Pascal's triangle, maybe I'll try it when my own formula doesn't work. – Kurumi Gaming Aug 11 '18 at 05:37