Mixing
Finding all natural number solution(s) to linear Diophantine equation of three variables
$begingroup$
Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end.
For those curious, this puzzle comes from the game West of Loathing. It's simple to solve by brute force guess and check, so I have the solution, but I wanted to see if there was a more formal way to approach these types of problems.
The linear equation is $411x+295y+161z=3200$. The trivial solution I found was $x=4, y=2, z=6$.
The question is, can I systematically come up with all natural number solutions to this equation?
My thought was first to look at the extended Euclidean algorithm like I typically would do for two variables. I tweaked it a bit using the identity $gca(a,b,c) = gca(a, gca(b,c))$. Since they are all prime, I ended up with gca = 1 which 3200 is divisible by, so there is a solution.
Following the algorithm, and applying it first to 295 and 116, and then applying that to 161, I ended up with the expression $161+(-160)*(124*295-89*411) = 1$ which is a valid integer solution once you multiply both sides by 3200.
That's where I've been stuck. In previous such problems, to find the natural number solutions, I would parameterize it by some variable $t$, then all solutions can be found using $t$, including ones that meet some additional criteria like $x >0, y >= 0$. I feel something similar should be possible with this form as well so you can find expressions for $x$, $y$, and $z$ such that all solutions are included. However, I can't figure out how to parameterize the solution. Given the generalization before, my hunch would be that you would need two integer parameters, and the solution space would allow any integer values for those two parameters (basically allowing traversal of the plane). I would expect a solution (at least for the integer solutions) in the form of a set of vectors ${(x,y,z) in mathbb{Z}^3 mid x=f(j,k), y=g(j,k), y=h(j,k) forall j,k in mathbb{Z}} $.
Any help or suggestions on how to parameterize it to find the general solution would be helpful. Secondly, if finding the natural number solutions isn't as simple (like it is with two variables) as adding a single inequality and solving, then I would appreciate pointers on how to add that constraint as well.
integer-partitions integer-programming euclidean-algorithm
asked Jan 15 at 2:45
techdudetechdude
1265
$endgroup$
add a comment |
$begingroup$
Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end.
For those curious, this puzzle comes from the game West of Loathing. It's simple to solve by brute force guess and check, so I have the solution, but I wanted to see if there was a more formal way to approach these types of problems.
The linear equation is $411x+295y+161z=3200$. The trivial solution I found was $x=4, y=2, z=6$.
The question is, can I systematically come up with all natural number solutions to this equation?
My thought was first to look at the extended Euclidean algorithm like I typically would do for two variables. I tweaked it a bit using the identity $gca(a,b,c) = gca(a, gca(b,c))$. Since they are all prime, I ended up with gca = 1 which 3200 is divisible by, so there is a solution.
Following the algorithm, and applying it first to 295 and 116, and then applying that to 161, I ended up with the expression $161+(-160)*(124*295-89*411) = 1$ which is a valid integer solution once you multiply both sides by 3200.
That's where I've been stuck. In previous such problems, to find the natural number solutions, I would parameterize it by some variable $t$, then all solutions can be found using $t$, including ones that meet some additional criteria like $x >0, y >= 0$. I feel something similar should be possible with this form as well so you can find expressions for $x$, $y$, and $z$ such that all solutions are included. However, I can't figure out how to parameterize the solution. Given the generalization before, my hunch would be that you would need two integer parameters, and the solution space would allow any integer values for those two parameters (basically allowing traversal of the plane). I would expect a solution (at least for the integer solutions) in the form of a set of vectors ${(x,y,z) in mathbb{Z}^3 mid x=f(j,k), y=g(j,k), y=h(j,k) forall j,k in mathbb{Z}} $.
Any help or suggestions on how to parameterize it to find the general solution would be helpful. Secondly, if finding the natural number solutions isn't as simple (like it is with two variables) as adding a single inequality and solving, then I would appreciate pointers on how to add that constraint as well.
integer-partitions integer-programming euclidean-algorithm
asked Jan 15 at 2:45
techdudetechdude
1265
$endgroup$
$begingroup$
you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution.
$endgroup$
– Will Jagy
Jan 15 at 3:06
add a comment |
$begingroup$
Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end.
For those curious, this puzzle comes from the game West of Loathing. It's simple to solve by brute force guess and check, so I have the solution, but I wanted to see if there was a more formal way to approach these types of problems.
The linear equation is $411x+295y+161z=3200$. The trivial solution I found was $x=4, y=2, z=6$.
The question is, can I systematically come up with all natural number solutions to this equation?
My thought was first to look at the extended Euclidean algorithm like I typically would do for two variables. I tweaked it a bit using the identity $gca(a,b,c) = gca(a, gca(b,c))$. Since they are all prime, I ended up with gca = 1 which 3200 is divisible by, so there is a solution.
Following the algorithm, and applying it first to 295 and 116, and then applying that to 161, I ended up with the expression $161+(-160)*(124*295-89*411) = 1$ which is a valid integer solution once you multiply both sides by 3200.
That's where I've been stuck. In previous such problems, to find the natural number solutions, I would parameterize it by some variable $t$, then all solutions can be found using $t$, including ones that meet some additional criteria like $x >0, y >= 0$. I feel something similar should be possible with this form as well so you can find expressions for $x$, $y$, and $z$ such that all solutions are included. However, I can't figure out how to parameterize the solution. Given the generalization before, my hunch would be that you would need two integer parameters, and the solution space would allow any integer values for those two parameters (basically allowing traversal of the plane). I would expect a solution (at least for the integer solutions) in the form of a set of vectors ${(x,y,z) in mathbb{Z}^3 mid x=f(j,k), y=g(j,k), y=h(j,k) forall j,k in mathbb{Z}} $.
Any help or suggestions on how to parameterize it to find the general solution would be helpful. Secondly, if finding the natural number solutions isn't as simple (like it is with two variables) as adding a single inequality and solving, then I would appreciate pointers on how to add that constraint as well.
integer-partitions integer-programming euclidean-algorithm
asked Jan 15 at 2:45
techdudetechdude
1265
$endgroup$
Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end.
For those curious, this puzzle comes from the game West of Loathing. It's simple to solve by brute force guess and check, so I have the solution, but I wanted to see if there was a more formal way to approach these types of problems.
The linear equation is $411x+295y+161z=3200$. The trivial solution I found was $x=4, y=2, z=6$.
The question is, can I systematically come up with all natural number solutions to this equation?
My thought was first to look at the extended Euclidean algorithm like I typically would do for two variables. I tweaked it a bit using the identity $gca(a,b,c) = gca(a, gca(b,c))$. Since they are all prime, I ended up with gca = 1 which 3200 is divisible by, so there is a solution.
Following the algorithm, and applying it first to 295 and 116, and then applying that to 161, I ended up with the expression $161+(-160)*(124*295-89*411) = 1$ which is a valid integer solution once you multiply both sides by 3200.
That's where I've been stuck. In previous such problems, to find the natural number solutions, I would parameterize it by some variable $t$, then all solutions can be found using $t$, including ones that meet some additional criteria like $x >0, y >= 0$. I feel something similar should be possible with this form as well so you can find expressions for $x$, $y$, and $z$ such that all solutions are included. However, I can't figure out how to parameterize the solution. Given the generalization before, my hunch would be that you would need two integer parameters, and the solution space would allow any integer values for those two parameters (basically allowing traversal of the plane). I would expect a solution (at least for the integer solutions) in the form of a set of vectors ${(x,y,z) in mathbb{Z}^3 mid x=f(j,k), y=g(j,k), y=h(j,k) forall j,k in mathbb{Z}} $.
Any help or suggestions on how to parameterize it to find the general solution would be helpful. Secondly, if finding the natural number solutions isn't as simple (like it is with two variables) as adding a single inequality and solving, then I would appreciate pointers on how to add that constraint as well.
integer-partitions integer-programming euclidean-algorithm
integer-partitions integer-programming euclidean-algorithm
asked Jan 15 at 2:45
techdudetechdude
1265
asked Jan 15 at 2:45
techdudetechdude
1265
asked Jan 15 at 2:45
techdudetechdude
1265
asked Jan 15 at 2:45
techdudetechdude
1265
asked Jan 15 at 2:45
techdudetechdude
1265
1265
$begingroup$
you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution.
$endgroup$
– Will Jagy
Jan 15 at 3:06
add a comment |
$begingroup$
you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution.
$endgroup$
– Will Jagy
Jan 15 at 3:06
$begingroup$
you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution.
$endgroup$
– Will Jagy
Jan 15 at 3:06
$begingroup$
you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution.
$endgroup$
– Will Jagy
Jan 15 at 3:06
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is a reduced lattice basis, as two columns:
$$
left(
begin{array}{rrr}
411 & 295 & 161
end{array}
right)
left(
begin{array}{rr}
3 & -28 \
-8 & 21\
7 & 33 \
end{array}
right) =
left(
begin{array}{cc}
0& 0
end{array}
right)
$$
The Gram matrix for the basis is
$$
left(
begin{array}{rr}
122 & -21 \
-21 & 2314\
end{array}
right)
$$
and is just $B^T B,$ where $B$ is the 3 by 2 matrix with basis vectors as columns.
========================================================================
? row = [ 411, 295, 161]
%4 = [411, 295, 161]
? r1 = [ 1,0,0; 0,1,0; 0,-2,1]
%5 =
[1 0 0]
[0 1 0]
[0 -2 1]
? row * r1
%6 = [411, -27, 161]
? r2 = [ 1,0,0; 15,1,0; 0,0,1]
%7 =
[ 1 0 0]
[15 1 0]
[ 0 0 1]
? row * r1 *r2
%8 = [6, -27, 161]
? r3 = [ 1,0,-27; 15,1,0; 0,0,1]
%9 =
[ 1 0 -27]
[15 1 0]
[ 0 0 1]
? r3 = [ 1,0,-27; 0,1,0; 0,0,1]
%10 =
[1 0 -27]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3
%11 = [6, -27, -1]
? r4 = [ 0,0,1; 0,1,0; -1,0,0]
%12 =
[ 0 0 1]
[ 0 1 0]
[-1 0 0]
? row * r1 *r2 *r3 *r4
%13 = [1, -27, 6]
? r5 = [ 1,27,-6; 0,1,0; 0,0,1]
%14 =
[1 27 -6]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3 *r4 *r5
%15 = [1, 0, 0]
? r = r1 *r2 *r3 *r4 *r5
%16 =
[ 27 729 -161]
[ 405 10936 -2415]
[-811 -21899 4836]
? row * r
%17 = [1, 0, 0]
? pick = [ 0,0; 1,0;0,1]
%18 =
[0 0]
[1 0]
[0 1]
? r * pick
%19 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_col =r * pick
%20 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_row = mattranspose(basis_col)
%21 =
[ 729 10936 -21899]
[-161 -2415 4836]
? g = basis_row * basis_col
%22 =
[ 599693738 -132431373]
[-132431373 29245042]
? matdet(g)
%23 = 281867
? q
%24 = q
? q = qflll(basis_col)
%25 =
[ -53 441]
[-240 1997]
? red = basis_col * q
%26 =
[ 3 -28]
[-8 21]
[ 7 33]
? red_row = mattranspose(red)
%27 =
[ 3 -8 7]
[-28 21 33]
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
?
? row
%30 = [411, 295, 161]
? red
%31 =
[ 3 -28]
[-8 21]
[ 7 33]
? row * red
%32 = [0, 0]
?
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3074024%2ffinding-all-natural-number-solutions-to-linear-diophantine-equation-of-three-v%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is a reduced lattice basis, as two columns:
$$
left(
begin{array}{rrr}
411 & 295 & 161
end{array}
right)
left(
begin{array}{rr}
3 & -28 \
-8 & 21\
7 & 33 \
end{array}
right) =
left(
begin{array}{cc}
0& 0
end{array}
right)
$$
The Gram matrix for the basis is
$$
left(
begin{array}{rr}
122 & -21 \
-21 & 2314\
end{array}
right)
$$
and is just $B^T B,$ where $B$ is the 3 by 2 matrix with basis vectors as columns.
========================================================================
? row = [ 411, 295, 161]
%4 = [411, 295, 161]
? r1 = [ 1,0,0; 0,1,0; 0,-2,1]
%5 =
[1 0 0]
[0 1 0]
[0 -2 1]
? row * r1
%6 = [411, -27, 161]
? r2 = [ 1,0,0; 15,1,0; 0,0,1]
%7 =
[ 1 0 0]
[15 1 0]
[ 0 0 1]
? row * r1 *r2
%8 = [6, -27, 161]
? r3 = [ 1,0,-27; 15,1,0; 0,0,1]
%9 =
[ 1 0 -27]
[15 1 0]
[ 0 0 1]
? r3 = [ 1,0,-27; 0,1,0; 0,0,1]
%10 =
[1 0 -27]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3
%11 = [6, -27, -1]
? r4 = [ 0,0,1; 0,1,0; -1,0,0]
%12 =
[ 0 0 1]
[ 0 1 0]
[-1 0 0]
? row * r1 *r2 *r3 *r4
%13 = [1, -27, 6]
? r5 = [ 1,27,-6; 0,1,0; 0,0,1]
%14 =
[1 27 -6]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3 *r4 *r5
%15 = [1, 0, 0]
? r = r1 *r2 *r3 *r4 *r5
%16 =
[ 27 729 -161]
[ 405 10936 -2415]
[-811 -21899 4836]
? row * r
%17 = [1, 0, 0]
? pick = [ 0,0; 1,0;0,1]
%18 =
[0 0]
[1 0]
[0 1]
? r * pick
%19 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_col =r * pick
%20 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_row = mattranspose(basis_col)
%21 =
[ 729 10936 -21899]
[-161 -2415 4836]
? g = basis_row * basis_col
%22 =
[ 599693738 -132431373]
[-132431373 29245042]
? matdet(g)
%23 = 281867
? q
%24 = q
? q = qflll(basis_col)
%25 =
[ -53 441]
[-240 1997]
? red = basis_col * q
%26 =
[ 3 -28]
[-8 21]
[ 7 33]
? red_row = mattranspose(red)
%27 =
[ 3 -8 7]
[-28 21 33]
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
?
? row
%30 = [411, 295, 161]
? red
%31 =
[ 3 -28]
[-8 21]
[ 7 33]
? row * red
%32 = [0, 0]
?
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
$endgroup$
add a comment |
$begingroup$
Here is a reduced lattice basis, as two columns:
$$
left(
begin{array}{rrr}
411 & 295 & 161
end{array}
right)
left(
begin{array}{rr}
3 & -28 \
-8 & 21\
7 & 33 \
end{array}
right) =
left(
begin{array}{cc}
0& 0
end{array}
right)
$$
The Gram matrix for the basis is
$$
left(
begin{array}{rr}
122 & -21 \
-21 & 2314\
end{array}
right)
$$
and is just $B^T B,$ where $B$ is the 3 by 2 matrix with basis vectors as columns.
========================================================================
? row = [ 411, 295, 161]
%4 = [411, 295, 161]
? r1 = [ 1,0,0; 0,1,0; 0,-2,1]
%5 =
[1 0 0]
[0 1 0]
[0 -2 1]
? row * r1
%6 = [411, -27, 161]
? r2 = [ 1,0,0; 15,1,0; 0,0,1]
%7 =
[ 1 0 0]
[15 1 0]
[ 0 0 1]
? row * r1 *r2
%8 = [6, -27, 161]
? r3 = [ 1,0,-27; 15,1,0; 0,0,1]
%9 =
[ 1 0 -27]
[15 1 0]
[ 0 0 1]
? r3 = [ 1,0,-27; 0,1,0; 0,0,1]
%10 =
[1 0 -27]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3
%11 = [6, -27, -1]
? r4 = [ 0,0,1; 0,1,0; -1,0,0]
%12 =
[ 0 0 1]
[ 0 1 0]
[-1 0 0]
? row * r1 *r2 *r3 *r4
%13 = [1, -27, 6]
? r5 = [ 1,27,-6; 0,1,0; 0,0,1]
%14 =
[1 27 -6]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3 *r4 *r5
%15 = [1, 0, 0]
? r = r1 *r2 *r3 *r4 *r5
%16 =
[ 27 729 -161]
[ 405 10936 -2415]
[-811 -21899 4836]
? row * r
%17 = [1, 0, 0]
? pick = [ 0,0; 1,0;0,1]
%18 =
[0 0]
[1 0]
[0 1]
? r * pick
%19 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_col =r * pick
%20 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_row = mattranspose(basis_col)
%21 =
[ 729 10936 -21899]
[-161 -2415 4836]
? g = basis_row * basis_col
%22 =
[ 599693738 -132431373]
[-132431373 29245042]
? matdet(g)
%23 = 281867
? q
%24 = q
? q = qflll(basis_col)
%25 =
[ -53 441]
[-240 1997]
? red = basis_col * q
%26 =
[ 3 -28]
[-8 21]
[ 7 33]
? red_row = mattranspose(red)
%27 =
[ 3 -8 7]
[-28 21 33]
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
?
? row
%30 = [411, 295, 161]
? red
%31 =
[ 3 -28]
[-8 21]
[ 7 33]
? row * red
%32 = [0, 0]
?
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
$endgroup$
add a comment |
$begingroup$
Here is a reduced lattice basis, as two columns:
$$
left(
begin{array}{rrr}
411 & 295 & 161
end{array}
right)
left(
begin{array}{rr}
3 & -28 \
-8 & 21\
7 & 33 \
end{array}
right) =
left(
begin{array}{cc}
0& 0
end{array}
right)
$$
The Gram matrix for the basis is
$$
left(
begin{array}{rr}
122 & -21 \
-21 & 2314\
end{array}
right)
$$
and is just $B^T B,$ where $B$ is the 3 by 2 matrix with basis vectors as columns.
========================================================================
? row = [ 411, 295, 161]
%4 = [411, 295, 161]
? r1 = [ 1,0,0; 0,1,0; 0,-2,1]
%5 =
[1 0 0]
[0 1 0]
[0 -2 1]
? row * r1
%6 = [411, -27, 161]
? r2 = [ 1,0,0; 15,1,0; 0,0,1]
%7 =
[ 1 0 0]
[15 1 0]
[ 0 0 1]
? row * r1 *r2
%8 = [6, -27, 161]
? r3 = [ 1,0,-27; 15,1,0; 0,0,1]
%9 =
[ 1 0 -27]
[15 1 0]
[ 0 0 1]
? r3 = [ 1,0,-27; 0,1,0; 0,0,1]
%10 =
[1 0 -27]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3
%11 = [6, -27, -1]
? r4 = [ 0,0,1; 0,1,0; -1,0,0]
%12 =
[ 0 0 1]
[ 0 1 0]
[-1 0 0]
? row * r1 *r2 *r3 *r4
%13 = [1, -27, 6]
? r5 = [ 1,27,-6; 0,1,0; 0,0,1]
%14 =
[1 27 -6]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3 *r4 *r5
%15 = [1, 0, 0]
? r = r1 *r2 *r3 *r4 *r5
%16 =
[ 27 729 -161]
[ 405 10936 -2415]
[-811 -21899 4836]
? row * r
%17 = [1, 0, 0]
? pick = [ 0,0; 1,0;0,1]
%18 =
[0 0]
[1 0]
[0 1]
? r * pick
%19 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_col =r * pick
%20 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_row = mattranspose(basis_col)
%21 =
[ 729 10936 -21899]
[-161 -2415 4836]
? g = basis_row * basis_col
%22 =
[ 599693738 -132431373]
[-132431373 29245042]
? matdet(g)
%23 = 281867
? q
%24 = q
? q = qflll(basis_col)
%25 =
[ -53 441]
[-240 1997]
? red = basis_col * q
%26 =
[ 3 -28]
[-8 21]
[ 7 33]
? red_row = mattranspose(red)
%27 =
[ 3 -8 7]
[-28 21 33]
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
?
? row
%30 = [411, 295, 161]
? red
%31 =
[ 3 -28]
[-8 21]
[ 7 33]
? row * red
%32 = [0, 0]
?
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
$endgroup$
Here is a reduced lattice basis, as two columns:
$$
left(
begin{array}{rrr}
411 & 295 & 161
end{array}
right)
left(
begin{array}{rr}
3 & -28 \
-8 & 21\
7 & 33 \
end{array}
right) =
left(
begin{array}{cc}
0& 0
end{array}
right)
$$
The Gram matrix for the basis is
$$
left(
begin{array}{rr}
122 & -21 \
-21 & 2314\
end{array}
right)
$$
and is just $B^T B,$ where $B$ is the 3 by 2 matrix with basis vectors as columns.
========================================================================
? row = [ 411, 295, 161]
%4 = [411, 295, 161]
? r1 = [ 1,0,0; 0,1,0; 0,-2,1]
%5 =
[1 0 0]
[0 1 0]
[0 -2 1]
? row * r1
%6 = [411, -27, 161]
? r2 = [ 1,0,0; 15,1,0; 0,0,1]
%7 =
[ 1 0 0]
[15 1 0]
[ 0 0 1]
? row * r1 *r2
%8 = [6, -27, 161]
? r3 = [ 1,0,-27; 15,1,0; 0,0,1]
%9 =
[ 1 0 -27]
[15 1 0]
[ 0 0 1]
? r3 = [ 1,0,-27; 0,1,0; 0,0,1]
%10 =
[1 0 -27]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3
%11 = [6, -27, -1]
? r4 = [ 0,0,1; 0,1,0; -1,0,0]
%12 =
[ 0 0 1]
[ 0 1 0]
[-1 0 0]
? row * r1 *r2 *r3 *r4
%13 = [1, -27, 6]
? r5 = [ 1,27,-6; 0,1,0; 0,0,1]
%14 =
[1 27 -6]
[0 1 0]
[0 0 1]
? row * r1 *r2 *r3 *r4 *r5
%15 = [1, 0, 0]
? r = r1 *r2 *r3 *r4 *r5
%16 =
[ 27 729 -161]
[ 405 10936 -2415]
[-811 -21899 4836]
? row * r
%17 = [1, 0, 0]
? pick = [ 0,0; 1,0;0,1]
%18 =
[0 0]
[1 0]
[0 1]
? r * pick
%19 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_col =r * pick
%20 =
[ 729 -161]
[ 10936 -2415]
[-21899 4836]
? basis_row = mattranspose(basis_col)
%21 =
[ 729 10936 -21899]
[-161 -2415 4836]
? g = basis_row * basis_col
%22 =
[ 599693738 -132431373]
[-132431373 29245042]
? matdet(g)
%23 = 281867
? q
%24 = q
? q = qflll(basis_col)
%25 =
[ -53 441]
[-240 1997]
? red = basis_col * q
%26 =
[ 3 -28]
[-8 21]
[ 7 33]
? red_row = mattranspose(red)
%27 =
[ 3 -8 7]
[-28 21 33]
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
? h = red_row * red
%28 =
[122 -21]
[-21 2314]
? matdet(h)
%29 = 281867
?
?
? row
%30 = [411, 295, 161]
? red
%31 =
[ 3 -28]
[-8 21]
[ 7 33]
? row * red
%32 = [0, 0]
?
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
edited Jan 15 at 3:46
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
answered Jan 15 at 3:40
Will JagyWill Jagy
103k5102200
103k5102200
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3074024%2ffinding-all-natural-number-solutions-to-linear-diophantine-equation-of-three-v%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution.
$endgroup$
– Will Jagy
Jan 15 at 3:06