10
Challenge
Let's imagine an N
-tuple of integers between 0 and M
inclusive, and let's call it F
.
There are (M + 1) ** N
possible F
s in total.
How many such F
s satisfy all of the following inequalities (index is one-based)?
F[n] + F[n+1] <= M
for1 <= n < N
F[N] + F[1] <= M
Write a program or function that takes two positive integers N
and M
and outputs the answer in any convenient form.
Test Cases
(N,M) => Answer
(1,1) => 1
(2,1) => 3
(3,1) => 4
(4,1) => 7
(1,2) => 2
(2,2) => 6
(3,2) => 11
(4,2) => 26
(10,3) => 39175
(10,4) => 286555
(10,5) => 1508401
(25,3) => 303734663372
(25,4) => 43953707972058
(25,5) => 2794276977562073
(100,3) => 8510938110502117856062697655362747468175263710
(100,4) => 3732347514675901732382391725971022481763004479674972370
(100,5) => 60964611448369808046336702581873778457326750953325742021695001
Explanation
M (max value of element) = 1
F[1] + F[1] <= 1; F = [0]
(1,1) => 1
F[1] + F[2] <= 1; F = [0,0], [0,1], [1,0]
(2,1) => 3
F = [0,0,0], [0,0,1], [0,1,0], [1,0,0]
(3,1) => 4
F = [0,0,0,0], [0,0,0,1], [0,0,1,0], [0,1,0,0], [0,1,0,1], [1,0,0,0], [1,0,1,0]
(4,1) => 7
---
M = 2
F[1] + F[1] <= 2; F = [0], [1]
(1,2) => 2
F = [0,0], [0,1], [0,2], [1,0], [1,1], [2,0]
(2,2) => 6
F = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1],
[1,1,0], [1,1,1], [2,0,0]
(3,2) => 11
(4,2) => 26 (left as exercise for you)
Rules
- This is a restricted-complexity challenge. The time complexity of your code should be polynomial in
M
andN
(e.g. you can't generate all(M + 1) ** N
tuples and then check for the condition). Please explain your approach in your submission. - Standard code-golf rules apply. The shortest answer in bytes wins.
Using
mat(...,int)
does not seem to work for then=100
cases. The method is correct (using sympy to sum the powers of the roots of the characteristic polynomial does work, for example), but numpy goes wrong somewhere as the numbers increase (maybe it's the**
power operator?) – Jonathan Allan – 2018-05-08T02:14:51.240