# 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.

edit retag close merge delete

You 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.

( 2020-09-29 17:39:54 +0200 )edit

Sort by » oldest newest most voted

You 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.

more

Tips:

• 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 powers
more

You 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...

more

You could use 15 for loops and then cartesian_product for the remainder, if performance is bad for cartesian_product.

( 2020-09-29 17:41:35 +0200 )edit
1

The problem here is that you iterates over too many useless values, which costs a lot.

( 2020-09-29 20:12:30 +0200 )edit

You 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}$.

( 2020-09-30 11:20:23 +0200 )edit

But 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.

( 2020-09-30 18:21:00 +0200 )edit