Repeat this GCD operation
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Problem A3 from the 2008 Putnam competition says:
Start with a finite sequence $a_1, a_2, dots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $gcd(a_j, a_k)$ and $textlcm(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made.
Your goal in this challenge is to take a finite sequence of positive integers as input, and output the result of repeating this process until no further progress is possible. (That is, until every number in the resulting sequence divides all the numbers that come after it.) You don't need to solve the Putnam problem.
This is code-golf: the shortest solution in every programming language wins.
Test cases
[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]
code-golf array-manipulation number-theory
add a comment |Â
up vote
4
down vote
favorite
Problem A3 from the 2008 Putnam competition says:
Start with a finite sequence $a_1, a_2, dots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $gcd(a_j, a_k)$ and $textlcm(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made.
Your goal in this challenge is to take a finite sequence of positive integers as input, and output the result of repeating this process until no further progress is possible. (That is, until every number in the resulting sequence divides all the numbers that come after it.) You don't need to solve the Putnam problem.
This is code-golf: the shortest solution in every programming language wins.
Test cases
[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]
code-golf array-manipulation number-theory
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Problem A3 from the 2008 Putnam competition says:
Start with a finite sequence $a_1, a_2, dots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $gcd(a_j, a_k)$ and $textlcm(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made.
Your goal in this challenge is to take a finite sequence of positive integers as input, and output the result of repeating this process until no further progress is possible. (That is, until every number in the resulting sequence divides all the numbers that come after it.) You don't need to solve the Putnam problem.
This is code-golf: the shortest solution in every programming language wins.
Test cases
[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]
code-golf array-manipulation number-theory
Problem A3 from the 2008 Putnam competition says:
Start with a finite sequence $a_1, a_2, dots, a_n$ of positive integers. If possible, choose two indices $j < k$ such that $a_j$ does not divide $a_k$, and replace $a_j$ and $a_k$ by $gcd(a_j, a_k)$ and $textlcm(a_j, a_k)$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made.
Your goal in this challenge is to take a finite sequence of positive integers as input, and output the result of repeating this process until no further progress is possible. (That is, until every number in the resulting sequence divides all the numbers that come after it.) You don't need to solve the Putnam problem.
This is code-golf: the shortest solution in every programming language wins.
Test cases
[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]
code-golf array-manipulation number-theory
code-golf array-manipulation number-theory
edited 47 mins ago
asked 56 mins ago
Misha Lavrov
3,696321
3,696321
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
5
down vote
Jelly, 9 bytes
ÃÂEz0á¹¢â¬ZÃÂẸ
Try it online!
How it works
ÃÂEz0á¹¢â¬ZÃÂẸ Main link. Argument: A (array)
ÃÂE For each n in A, compute the exponents of n's prime factorization.
E.g., 2000000 = 2â·3â°5ⶠgets mapped to [7, 0, 6].
z0 Zip 0; append 0's to shorter exponent arrays to pad them to the same
length, then read the resulting matrix by columns.
Ṣ⬠Sort the resulting arrays (exponents that correspond to the same prime).
Z Zip; read the resulting matrix by columns, re-grouping the exponents by
the integers they represent.
ÃÂẸ Unexponents; map the exponent arrays back to integers.
add a comment |Â
up vote
0
down vote
Retina, 65 bytes
d+
*
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
$2$4$5$#3*$5
_+
$.&
Try it online! Link includes the faster test cases. Explanation:
d+
*
Convert to unary.
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.
$2$4$5$#3*$5
$1
is the first number. $2
is the factor. Because regex is greedy this is the largest factor i.e the gcd. $4
is the part of the match between the original numbers. $5
is the second number. $#3
(in decimal rather than unary) is one less than $1
divided by $2
, since it doesn't include the original $2
. This means that to calculate the lcm we need to multiply $5
by one more than $#3
which is most succintly written as the sum of $5
and the product of $#3
and $5
.
_+
$.&
Convert to decimal.
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Jelly, 9 bytes
ÃÂEz0á¹¢â¬ZÃÂẸ
Try it online!
How it works
ÃÂEz0á¹¢â¬ZÃÂẸ Main link. Argument: A (array)
ÃÂE For each n in A, compute the exponents of n's prime factorization.
E.g., 2000000 = 2â·3â°5ⶠgets mapped to [7, 0, 6].
z0 Zip 0; append 0's to shorter exponent arrays to pad them to the same
length, then read the resulting matrix by columns.
Ṣ⬠Sort the resulting arrays (exponents that correspond to the same prime).
Z Zip; read the resulting matrix by columns, re-grouping the exponents by
the integers they represent.
ÃÂẸ Unexponents; map the exponent arrays back to integers.
add a comment |Â
up vote
5
down vote
Jelly, 9 bytes
ÃÂEz0á¹¢â¬ZÃÂẸ
Try it online!
How it works
ÃÂEz0á¹¢â¬ZÃÂẸ Main link. Argument: A (array)
ÃÂE For each n in A, compute the exponents of n's prime factorization.
E.g., 2000000 = 2â·3â°5ⶠgets mapped to [7, 0, 6].
z0 Zip 0; append 0's to shorter exponent arrays to pad them to the same
length, then read the resulting matrix by columns.
Ṣ⬠Sort the resulting arrays (exponents that correspond to the same prime).
Z Zip; read the resulting matrix by columns, re-grouping the exponents by
the integers they represent.
ÃÂẸ Unexponents; map the exponent arrays back to integers.
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Jelly, 9 bytes
ÃÂEz0á¹¢â¬ZÃÂẸ
Try it online!
How it works
ÃÂEz0á¹¢â¬ZÃÂẸ Main link. Argument: A (array)
ÃÂE For each n in A, compute the exponents of n's prime factorization.
E.g., 2000000 = 2â·3â°5ⶠgets mapped to [7, 0, 6].
z0 Zip 0; append 0's to shorter exponent arrays to pad them to the same
length, then read the resulting matrix by columns.
Ṣ⬠Sort the resulting arrays (exponents that correspond to the same prime).
Z Zip; read the resulting matrix by columns, re-grouping the exponents by
the integers they represent.
ÃÂẸ Unexponents; map the exponent arrays back to integers.
Jelly, 9 bytes
ÃÂEz0á¹¢â¬ZÃÂẸ
Try it online!
How it works
ÃÂEz0á¹¢â¬ZÃÂẸ Main link. Argument: A (array)
ÃÂE For each n in A, compute the exponents of n's prime factorization.
E.g., 2000000 = 2â·3â°5ⶠgets mapped to [7, 0, 6].
z0 Zip 0; append 0's to shorter exponent arrays to pad them to the same
length, then read the resulting matrix by columns.
Ṣ⬠Sort the resulting arrays (exponents that correspond to the same prime).
Z Zip; read the resulting matrix by columns, re-grouping the exponents by
the integers they represent.
ÃÂẸ Unexponents; map the exponent arrays back to integers.
edited 17 mins ago
answered 27 mins ago
Dennisâ¦
183k32293725
183k32293725
add a comment |Â
add a comment |Â
up vote
0
down vote
Retina, 65 bytes
d+
*
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
$2$4$5$#3*$5
_+
$.&
Try it online! Link includes the faster test cases. Explanation:
d+
*
Convert to unary.
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.
$2$4$5$#3*$5
$1
is the first number. $2
is the factor. Because regex is greedy this is the largest factor i.e the gcd. $4
is the part of the match between the original numbers. $5
is the second number. $#3
(in decimal rather than unary) is one less than $1
divided by $2
, since it doesn't include the original $2
. This means that to calculate the lcm we need to multiply $5
by one more than $#3
which is most succintly written as the sum of $5
and the product of $#3
and $5
.
_+
$.&
Convert to decimal.
add a comment |Â
up vote
0
down vote
Retina, 65 bytes
d+
*
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
$2$4$5$#3*$5
_+
$.&
Try it online! Link includes the faster test cases. Explanation:
d+
*
Convert to unary.
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.
$2$4$5$#3*$5
$1
is the first number. $2
is the factor. Because regex is greedy this is the largest factor i.e the gcd. $4
is the part of the match between the original numbers. $5
is the second number. $#3
(in decimal rather than unary) is one less than $1
divided by $2
, since it doesn't include the original $2
. This means that to calculate the lcm we need to multiply $5
by one more than $#3
which is most succintly written as the sum of $5
and the product of $#3
and $5
.
_+
$.&
Convert to decimal.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Retina, 65 bytes
d+
*
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
$2$4$5$#3*$5
_+
$.&
Try it online! Link includes the faster test cases. Explanation:
d+
*
Convert to unary.
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.
$2$4$5$#3*$5
$1
is the first number. $2
is the factor. Because regex is greedy this is the largest factor i.e the gcd. $4
is the part of the match between the original numbers. $5
is the second number. $#3
(in decimal rather than unary) is one less than $1
divided by $2
, since it doesn't include the original $2
. This means that to calculate the lcm we need to multiply $5
by one more than $#3
which is most succintly written as the sum of $5
and the product of $#3
and $5
.
_+
$.&
Convert to decimal.
Retina, 65 bytes
d+
*
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
$2$4$5$#3*$5
_+
$.&
Try it online! Link includes the faster test cases. Explanation:
d+
*
Convert to unary.
+`b((_+)(2)+)b(.*)b(?!1+b)(2+)b
Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.
$2$4$5$#3*$5
$1
is the first number. $2
is the factor. Because regex is greedy this is the largest factor i.e the gcd. $4
is the part of the match between the original numbers. $5
is the second number. $#3
(in decimal rather than unary) is one less than $1
divided by $2
, since it doesn't include the original $2
. This means that to calculate the lcm we need to multiply $5
by one more than $#3
which is most succintly written as the sum of $5
and the product of $#3
and $5
.
_+
$.&
Convert to decimal.
answered 5 mins ago
Neil
77.2k744174
77.2k744174
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175090%2frepeat-this-gcd-operation%23new-answer', 'question_page');
);
Post as a guest
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
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
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