## Square Triple

### February 14, 2020

Our algorithm finds all pairs, then checks if the square root of the product is in the list:

(define (f xs) (list-of (list x y z) (x in xs) (y in xs) (< x y) (z2 is (* x y)) (z is (isqrt z2)) (= (* z z) z2) (member z xs)))

We eliminate duplicates by insisting that *x* < *y*. Here’s an example:

> (f (range 1 20)) ((1 4 2) (1 9 3) (1 16 4) (2 8 4) (2 18 6) (3 12 6) (4 9 6) (4 16 8) (8 18 12) (9 16 12))

That takes time O(*n*³); *n* * *n* to form the pairs and another factor of *n* to search the list. We could reduce that to O(*n*²) by first inserting the list items in a hash table and checking membership there. Another improvement is a quick exit if the product exceeds the maximum list item. We’ll leave those improvements as an exercise to the reader.

You can run the program at https://ideone.com/L7itmh.

Easiest way to make this o(n2) is to first compute an array of squares and use this to filter results… as usual in Perl…

Here’s an O(n²) solution that doesn’t require any auxiliary storage. Assumes input is sorted and all positive:

Here is my approach to the problem using Julia, as usual: https://pastebin.com/FjqkHhQ7

Although I iterate through the data points using a triple loop, not all combinations are examined since I take advantage of the fact that the integers are distinct (so there is one zero at most), simplifying the whole process. Cheers!

Here’s a O(n^2) solution in Python.

I’ve assumed x, y, z are distinct (e.g., no (x=1,y=1,z=1) nor (x=0, y=2, z=0)), which I think is suggested by the problem specifying a “list of distinct integers” for the input.

Output:

@programmingpraxis, I think that using square roots for this problem can be problematic, since as-is it won’t handle negative values for z.

(where “square roots” in my comment refers to the conventional function that returns a

singlenon-negative value)Klong version

The problem says to find ALL triples, but the model answer finds only half of them.

Nothing whatsoever in the problem says that the numbers are all positive or all non-negative.

In fact by using “integer” instead of “natural number” it suggests that negative numbers are allowed.

Given [-2,1,2,4], (1,4,2) and (1,4,-2) are both legal triples, but the model answer will not find the second.

I thought it might be interesting to explain some of the facilities of the Klong programming language. I like to learn this about other languages – they all seem to have their strengths – and Klong is one of the more unusual ones I’ve come upon.

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

[[1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10] [1 11] [1 12] [1 13] [1 14] [1 15] [1 16] [1 17] [1 18] [1 19] [1 20]]

[4 5 6]

[1 3 5 7 9 11 13 15 17 19]

[0]

[1 2 3]?4

[]

*/[2 3]

6

Richard noticed that the example solution did not find all solutions. Mine didn’t either. Here’s version 2 for Klong.

This is a common lisp solution. It assumes the input list is sorted in accending order.

Sample run:

Python Solution:

def find_triples(int_list):

triples = []

# Loop through all integers in list

for k in range(len(int_list)):

for i in range(len(int_list)):

for j in range(len(int_list)):

# Detect valid pair

if int_list[k] * int_list[i] == int_list[j] ** 2:

same = False

# Check each tuple to see if different permutation of pair is already present

for tup in triples:

if int_list[k] in tup and int_list[i] in tup and int_list[j] in tup:

same = True

break

if not same:

triples.append((int_list[k], int_list[i], int_list[j]))

else:

continue

return triples

print(find_triples(range(1, 15)))

OUTPUT:

[(1, 1, 1), (1, 4, 2), (1, 9, 3), (2, 8, 4), (3, 12, 6), (4, 9, 6), (5, 5, 5), (7, 7, 7), (10, 10, 10), (11, 11, 11), (13, 13, 13), (14, 14, 14)]