I am trying to generate primitive Pythogorean triples using Euclid’s parametrization. I basically want a list of pairs with ordered pairs $(m,n)$ such that $m$ and $n$ are coprime.

My first approach was

```
AbsoluteTiming(
list1 = Flatten(Table({m, n}, {m, 1, 20000, 2}, {n, 2, 20000, 2}), 1);
list2 = Select(list1, (GCD(#((1)), #((2))) == 1) &);)
(*{223.175, Null}*)
```

in which I first produce a list of pairs where $m$ is always odd and $n$ is always even. Then I use `Select`

to select the pairs where both coordinates are coprime. I quit and restarted a local kernel with a simple computation like `2+2`

to make sure there are no effects due to caching, garbage cleanup, or something like that. I then timed the whole thing and got 223 seconds.

My second approach was

```
AbsoluteTiming(
list1 = Flatten(
Table({m, n, GCD(m, n)}, {m, 1, 20000, 2}, {n, 2, 20000, 2}), 1);
list2 = Select(list1, #((3)) == 1 &);)
(*{161.464, Null}*)
```

in which I compute a third column inside the `Table`

which is the GCD of $m$ and $n$. Then I used `Select`

to simply pick the lists where the third coordinate is one. Restarting the kernel as before and timing it gives me only 161 seconds, which is almost 40% faster.

**Why is the first method slower?** I don’t care about the memory usage. Obviously storing the third column will take more memory.

My thoughts,

- I would expect both of them to take roughly the same amount of time. If anything, I would expect the second approach to be slower. We are flattening an array with more elements.
- They are both vectorized approaches.
- The kernel is doing all of the work (instead of the front-end) in both cases.
- The number of GDC operations is the same in both cases.
- The number of comparisons is the same in both cases.
- In the first case,
`Select`

is scanning row-by-row, computing the GCD, and comparing it to one.
- In the second case,
`Table`

is computing the GCD row-by-row and `Select`

is only scanning the third column and comparing it to one.

Which of these, if any, is wrong? The only thing I can think of is that in the first approach `Select`

is scanning both the first and the second column. In the second approach `Select`

is only concerned with the third column *ignoring the first two columns completely*. Is this true?

**What is going on here?** What are the lesson to be learned here, in the context of writing fast MMA code?