Ask Your Question
1

too many for loops

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

brennan gravatar image

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 gravatar imageJohn Palmieri ( 2020-09-29 17:39:54 +0100 )edit

3 Answers

Sort by ยป oldest newest most voted
2

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

tmonteil gravatar image

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 more
0

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

slelievre gravatar image

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

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 more
0

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

Florentin Jaffredo gravatar image

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

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 more

Comments

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

John Palmieri gravatar imageJohn Palmieri ( 2020-09-29 17:41:35 +0100 )edit
1

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

tmonteil gravatar imagetmonteil ( 2020-09-29 20:12:30 +0100 )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 gravatar imageFlorentin Jaffredo ( 2020-09-30 11:20:23 +0100 )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 gravatar imageJohn Palmieri ( 2020-09-30 18:21:00 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-09-29 10:24:15 +0100

Seen: 396 times

Last updated: Sep 29 '20