too many for loops

asked 2020-09-29 10:24:15 +0200

brennan
109 ●3 ●5

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 flag offensive close merge delete

Comments

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.

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

add a comment

2

answered 2020-09-29 20:35:12 +0200

tmonteil
27323 ●31 ●202 ●514 http://wiki.sagemath.o...

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.

edit flag offensive delete link

add a comment

0

answered 2020-09-29 21:49:10 +0200

slelievre
17654 ●22 ●160 ●348 http://carva.org/samue...

updated 2020-09-29 21:52:07 +0200

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

edit flag offensive delete link

add a comment

0

answered 2020-09-29 11:57:48 +0200

Florentin Jaffredo
636 ●2 ●13 ●29

updated 2020-09-29 13:17:53 +0200

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

edit flag offensive delete link

Comments

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

John Palmieri ( 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.

tmonteil ( 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}$.

Florentin Jaffredo ( 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.

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

add a comment

too many for loops

Comments

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

too many for loops edit

Comments

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

too many for loops