ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 30 Sep 2020 18:21:00 +0200too many for loopshttps://ask.sagemath.org/question/53647/too-many-for-loops/ I am trying to solve a Diophantine system with more than 20 variables. I have been trying to use:
\\
for a in srange(1,100):
for b in srange(1,a+1):
.
.
.
if (a+b+...)^(1\2) in ZZ and if (a+b+...)^(1/3) in ZZ:
print(a,b,...)
The problem is I have more than 20 variables and hence more than 20 of these for loops and Python doesnt allow that. Any help on an easy workaround would be greatly appreciated! This is not for homework or anything, I am just trying to do some computational research on Diophantine systems and I am running into some trouble. Tue, 29 Sep 2020 10:24:15 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/Comment by John Palmieri for <p>I am trying to solve a Diophantine system with more than 20 variables. I have been trying to use:</p>
<p>\</p>
<pre><code> for a in srange(1,100):
for b in srange(1,a+1):
.
.
.
if (a+b+...)^(1\2) in ZZ and if (a+b+...)^(1/3) in ZZ:
print(a,b,...)
</code></pre>
<p>The problem is I have more than 20 variables and hence more than 20 of these for loops and Python doesnt allow that. Any help on an easy workaround would be greatly appreciated! This is not for homework or anything, I am just trying to do some computational research on Diophantine systems and I am running into some trouble. </p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53651#post-id-53651You could construct a polyhedron based on the ranges in your `for` loops, and then iterate over the integral points of that polyhedron. I don't know how fast or slow this is, though.Tue, 29 Sep 2020 17:39:54 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53651#post-id-53651Answer by tmonteil for <p>I am trying to solve a Diophantine system with more than 20 variables. I have been trying to use:</p>
<p>\</p>
<pre><code> for a in srange(1,100):
for b in srange(1,a+1):
.
.
.
if (a+b+...)^(1\2) in ZZ and if (a+b+...)^(1/3) in ZZ:
print(a,b,...)
</code></pre>
<p>The problem is I have more than 20 variables and hence more than 20 of these for loops and Python doesnt allow that. Any help on an easy workaround would be greatly appreciated! This is not for homework or anything, I am just trying to do some computational research on Diophantine systems and I am running into some trouble. </p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?answer=53656#post-id-53656You can use `IntegerListsLex` for such things.
If you want to iterate over 20 variables $A_0,...,A_{19}$ such that $1 \leq A_i \leq 100$ and $A_{i+1}\leq A_i$ for every $i$, you can do:
sage: for A in IntegerListsLex(length=20, min_part=1, max_part=100, min_slope=0):
....: do_what_tyou_need_with_A, you can use A[0], A[1], ...A[19], but also sum(A) or print(A)
That said, besides your question, you should also notice that the condition `if sum(A)^(1/2) in ZZ and sum(A)^(1/3) in ZZ` is valid for a very sparse set of integers, so you should first iterate over se possible sums, and them decompose those sums with IntegerListLex using the options `min_sum=s` and `max_sum=s`. As cubes are sparser than squares, you can iterate over an integer `c`, and set `s` as `c^3` and see if `if s^(1/2) in ZZ` and for such s, look `for A in IntegerListsLex(length=20, min_part=1, max_part=100, min_slope=0, min_sum=s, max_sum=s)` which will avoid a lot of useless tuples.
Tue, 29 Sep 2020 20:35:12 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?answer=53656#post-id-53656Answer by Florentin Jaffredo for <p>I am trying to solve a Diophantine system with more than 20 variables. I have been trying to use:</p>
<p>\</p>
<pre><code> for a in srange(1,100):
for b in srange(1,a+1):
.
.
.
if (a+b+...)^(1\2) in ZZ and if (a+b+...)^(1/3) in ZZ:
print(a,b,...)
</code></pre>
<p>The problem is I have more than 20 variables and hence more than 20 of these for loops and Python doesnt allow that. Any help on an easy workaround would be greatly appreciated! This is not for homework or anything, I am just trying to do some computational research on Diophantine systems and I am running into some trouble. </p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?answer=53648#post-id-53648You could try using `cartesian_product`:
for a, b, c in cartesian_product([srange(1,100), srange(1,100), srange(1,100)]):
if a<=b<=c:
do something
But I'm worried about computational cost...Tue, 29 Sep 2020 11:57:48 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?answer=53648#post-id-53648Comment by tmonteil for <p>You could try using <code>cartesian_product</code>:</p>
<pre><code>for a, b, c in cartesian_product([srange(1,100), srange(1,100), srange(1,100)]):
if a<=b<=c:
do something
</code></pre>
<p>But I'm worried about computational cost...</p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53655#post-id-53655The problem here is that you iterates over too many useless values, which costs a lot.Tue, 29 Sep 2020 20:12:30 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53655#post-id-53655Comment by John Palmieri for <p>You could try using <code>cartesian_product</code>:</p>
<pre><code>for a, b, c in cartesian_product([srange(1,100), srange(1,100), srange(1,100)]):
if a<=b<=c:
do something
</code></pre>
<p>But I'm worried about computational cost...</p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53652#post-id-53652You could use 15 `for` loops and then `cartesian_product` for the remainder, if performance is bad for `cartesian_product`.Tue, 29 Sep 2020 17:41:35 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53652#post-id-53652Comment by Florentin Jaffredo for <p>You could try using <code>cartesian_product</code>:</p>
<pre><code>for a, b, c in cartesian_product([srange(1,100), srange(1,100), srange(1,100)]):
if a<=b<=c:
do something
</code></pre>
<p>But I'm worried about computational cost...</p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53661#post-id-53661You are right, the complexity is O(n^20) in both cases, but the constant factor in front can be reduced by a factor of the order of $20! \simeq 2.10^{18}$.Wed, 30 Sep 2020 11:20:23 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53661#post-id-53661Comment by John Palmieri for <p>You could try using <code>cartesian_product</code>:</p>
<pre><code>for a, b, c in cartesian_product([srange(1,100), srange(1,100), srange(1,100)]):
if a<=b<=c:
do something
</code></pre>
<p>But I'm worried about computational cost...</p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53664#post-id-53664But if there are only 22 variables (for example), using a `for` loop for 19 of them and `cartesian_product` for the rest doesn't add too many useless values.Wed, 30 Sep 2020 18:21:00 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?comment=53664#post-id-53664Answer by slelievre for <p>I am trying to solve a Diophantine system with more than 20 variables. I have been trying to use:</p>
<p>\</p>
<pre><code> for a in srange(1,100):
for b in srange(1,a+1):
.
.
.
if (a+b+...)^(1\2) in ZZ and if (a+b+...)^(1/3) in ZZ:
print(a,b,...)
</code></pre>
<p>The problem is I have more than 20 variables and hence more than 20 of these for loops and Python doesnt allow that. Any help on an easy workaround would be greatly appreciated! This is not for homework or anything, I am just trying to do some computational research on Diophantine systems and I am running into some trouble. </p>
https://ask.sagemath.org/question/53647/too-many-for-loops/?answer=53659#post-id-53659Tips:
- use `itertools.product` for iterating over a cartesian product
- find ways to not iterate over the full cartesian product, using symmetries
- that might mean iterating over partitions for instance
- use `is_square()` rather than computing the square root and checking whether it is in `ZZ`
- use `is_perfect_power`
- compute squares and cubes modulo some numbers and use such lists for pre-checks
- use the fact that cubes that are also squares are in fact sixth powersTue, 29 Sep 2020 21:49:10 +0200https://ask.sagemath.org/question/53647/too-many-for-loops/?answer=53659#post-id-53659