I have a relationship:
4000k + 2500j + 400g = n, k >= 0, 0 <= j <= k, 0 <= g <= j
I have to, given n, verify that a solution exists. I will implement this as a validator on a website, so computer-based solutions are fine.
So far, I've been able to write the validator as a series of three nested loops, but I'm looking for a better-performing option, even if it is as simple as removing one of the loops.
I've also tried WolframAlpha, but it couldn't do much for me besides simplifying some of the expressions a little.
First of all, obviously, you need to check whether $n$ is divisible by $100$, if it is, let's say $m=n/100$, and we are left with
$$40k+25j+4g=m\\0\le g\le j\le k$$
Now, let $j=g+j_g$, where $j_g\ge 0$ due to the above inequality, and $k=j+k_g=g+j_g+k_j$, where $k_j\ge 0$. Substituting that we get:
$$69g+65j_g+40k_j=m\\g,j_g,k_j\ge 0$$
From then on it's a simple dynamic or otherwise recursion with memoization.
There is also an even more efficient approach to this than dynamic: we could rewrite question from "is there a solution" to "how many solutions are there" and obtain the following recurrent relation:
$$F_m=\left\{\begin{array}{lr}0&m<0\\1&m=0\\F_{m-69}+F_{m-65}+F_{m-40}&m>0\end{array}\right.$$
Which, as a linear recurrence with constant coefficients, can be calculated in closed form.