CODEWITHSUNDEEP
pythonalgorithm
directedition
directedition

Reputation: 11705

Efficiency when adding values from two lists

I'm trying to learn algorithms by writing a python application that tests out Fermat's last theorem. It iterates all combinations of a^n + b^n = c^n Where a/b hit a ceiling at 10000 and n hits a ceiling at 100. I realize I won't get any hits, but it's just a bit of fun. Anyway, the specifics don't really matter.

What it boils down to is a + b where a and b iterate all combinations 1 to 10000. But here's the problem: 4 + 5 is exactly the same as 5 + 4. So my program is doing twice the work it needs to do. How can I iterate these combinations while skipping over mirrored inputs?

base_ceiling = 10000 # max values for a and b
n_ceiling = 100 # max value for power of n

powers = []
for i in range(n_ceiling):
  jarr = []
  for j in range(base_ceiling):
    jarr.append(j ** i)
  powers.append(jarr)

for k in range(3, n_ceiling):
  for i in range(1, base_ceiling):
    for j in range(1, base_ceiling):
      pow_vals = powers[k]
      a = powers[k][i]
      b = powers[k][j]
      c = a + b
      try:
        idx = pow_vals.index(c)
        if idx > -1:
          print k, ": ", i, j, "=", idx, " results in ", a, b, "=", c
      except ValueError:
        continue

Upvotes: 0

Views: 53

Answers (1)

internet_user
internet_user

Reputation: 3279

It's as simple as using for j in range(i, base_ceiling). This works because it will start from i instead of 1, so it doesn't repeat anything less than i. You could use i + 1 instead, because i^n + i^n will never be a power of n.

Upvotes: 1

Related Questions