Does this technique apply if the dimension of the null space of the linear transformation is greater than 1? In other words, if there is more than 1 free variable, can you still use the Smith normal form of the matrix to find a bijection from the integers to the solution set?
Edit: related follow up: any chance this technique is a good fit for enumeration of [Magic Squares][0] of a given order?
I could be wrong, but my impression of the post was that it is not meant to be a novel solution for a hard problem, but rather a demonstration of an interesting technique on a simple enough problem that the problem doesn’t distract from the technique itself.
You waste some CPU cycles, which doesn't matter all that much here, but with more combinations could matter a lot:
for m in range(100):
for w in range(101-m):
c = 100-m-w
if 3*m + 2*w +.5*c == 100:
print(m,w,c)
No need to specify 0 as starting range, and the ending boundary is not included, so it's 100 at the outer loop, because at first sight the solution can't be m=100 w=0 c=0, The inner loop has to use 101, because perhaps there is a solution with c=0.
There's no need for the 3rd loop! Once you have candidates for m and w, there's only one possible c satisfying the requirements. And so you also don't need to check for their sum being 100.
I think it's because OP does not want to hardcode the dimension `n=3`, but write only code that works for all possible matrix sizes just by changing `a` and `b`.
Does this technique apply if the dimension of the null space of the linear transformation is greater than 1? In other words, if there is more than 1 free variable, can you still use the Smith normal form of the matrix to find a bijection from the integers to the solution set?
Edit: related follow up: any chance this technique is a good fit for enumeration of [Magic Squares][0] of a given order?
[0]: https://en.wikipedia.org/wiki/Magic_square
Am I stupid or this is solvable with pen and paper?
The word problem directly translates to this system of diophantine equations:
Replacing z in (ii) using (i) yields: Which is solvable with the usual method.I could be wrong, but my impression of the post was that it is not meant to be a novel solution for a hard problem, but rather a demonstration of an interesting technique on a simple enough problem that the problem doesn’t distract from the technique itself.
The brute force method proposed in the article is so strangely obscure.
Here's a very simple alternative:
You waste some CPU cycles, which doesn't matter all that much here, but with more combinations could matter a lot:
No need to specify 0 as starting range, and the ending boundary is not included, so it's 100 at the outer loop, because at first sight the solution can't be m=100 w=0 c=0, The inner loop has to use 101, because perhaps there is a solution with c=0.There's no need for the 3rd loop! Once you have candidates for m and w, there's only one possible c satisfying the requirements. And so you also don't need to check for their sum being 100.
Some clues to make it faster: w is divisible by 5. 5m=100-3w.
So, w ∈ {5,10,15,20,25,30}, m = 20 - 3w/5, c=100-m-w.
It seems this gives all answers.
I think it's because OP does not want to hardcode the dimension `n=3`, but write only code that works for all possible matrix sizes just by changing `a` and `b`.