How many ways are there to go up the n-step stairs when you decide to go up a prime number of steps, such as going up two steps, going up three steps, going up five steps?

Expectation: I thought I could use the Fibonacci sequence.For example, the way 11 steps are raised is the sum of the total number of steps 11-1, (11-2), (11-3), (11-5), (11-7), (11-9) and (11-11).

Actually: Function definition is prohibited, so I can't use it

Put the Fibonacci sequence aside and try to solve it with Dynamic Programming (DP).

## prime numbers
max_step, primes=50, [1,2]
for i in range (primes[-1]+1,max_step+1):
  for jin primes [1:] [:]:
    if i%j == 0:break
    if i<2*j:primes.append(i);break

# print (primes)

## sum all steps with DP
n = 11
steps = [i for i in prime if <=n]
dp = [1]+[0]*n
for i in range (1, n + 1):
  For pin steps:
    if(i-p>=0):
      dp[i]+=dp[i-p]

sum_steps=dp[n]
print(sum_steps)

#
652

I appreciate your reply.

I will not explain the above code.If you are interested in DP, please check it out.

As you notice, you can calculate how to climb a certain number of steps from how to climb a smaller number of steps.
Therefore, for the natural number x up to n, you can make a table of the number of stairs up in the x step in order from the smallest to the smallest.

Since the calculation requires a prime number, proceed with a list of prime numbers up to x at the same time.
Start with an empty list of prime numbers and add them if x is a prime number.

N=int(input("How many steps are there?"))

Ways=[0]*(N+1)#x stairway up (0 xx NN)
ways[0] = ways[1] = 1
primes = [ ]#i List of prime numbers or less

for i in range(2,N+1):
    if not any(i%p==0 for pin primes):
        primes.append(i)#i was a prime number
    ways[i] = sum (ways[i-p]) for pin primes + [1])

The print(f"{N} column goes up in {ways[N]} ways.")