A stairway consists of 100 steps which can be ascended by one step at a time, two steps, three steps or, by four steps.
Determine the total number of ways to ascend the staircase.
Allowing only 1s and 2s leads to the Fibonacci sequence. Including 3's gets to tribonacci. This puzzle leads to the tetranacci sequence. https://oeis.org/A000078
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)
because you can append a 1 to all the sums in the a(n-1), 2 to the a(n-2) etc.
The OEIS considers a(0)=a(1)=a(2)=0 and a(3)=1. Our first term is a(4)=1. With an offset of 3, the solution is a(103)=17943803336550012914104102513
|
|
Posted by Jer
on 2023-03-07 09:55:09 |
Solution
