Exercise 2.40 of SICP

Exercise 2.40: Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with latex path not specified.: 1\le j< i\le n[/latex]. Use unique-pairs to simplify the definition of prime-sum-pairs given above.

Using Miller-Rabin primality test as well as taking advantage of some lexical scoping here is the solution:

> (prime-sum-pairs 1)
()
> (prime-sum-pairs 2)
((2 1 3))
> (prime-sum-pairs 3)
((2 1 3) (3 2 5))
> (prime-sum-pairs 4)
((2 1 3) (3 2 5) (4 1 5) (4 3 7))
> (prime-sum-pairs 5)
((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7))

One thought on “Exercise 2.40 of SICP

  1. Prior to inserting a value to first hash table, check if it is already in the table. If so, check second table. If either of (a_w a_x, w) or (a_w a_x, x) is there, don’t insert anything (we’ve got a duplicate element). If neither of these pairs is in the second table, we’ve got positive answer.

Leave a Reply