using PureFun
using PureFun: Pairing

Taxicab numbers are numbers that can be expressed as the sum of cubes in two different ways. In this exercise we'll create an iterator over taxicab numbers less than k. We do this by generating pairs of integers and ordering them by the sum of their cubes, and then iterate through them in order looking for adjacent pairs with the same sum of cubes. We use a custom ordering to order a heap by the sum of cubes.

sum_of_cubes(x,y) = x^3 + y^3
sum_of_cubes(pair) = sum_of_cubes(pair[1], pair[2]);

function taxi(k)
    all_pairs = distinct_pairs(k)
    ordered_pairs = Pairing.Heap(all_pairs,
                                 Base.Order.By(sum_of_cubes))
    consecutive_matches(ordered_pairs)
end

taxi (generic function with 1 method)

We still need to implement the underlying iterators distinct_pairs, which generates pairs of integers, and consecutive matches, which scans an iterator that's already ordered for pairs of duplicates:

distinct_pairs(k) = ((p,q) for (p,q) in Iterators.product(1:k, 1:k) if p < q)
adjacent_pairs(it) = zip(it, Iterators.drop(it, 1));

function consecutive_matches(pair_stream)
    (
     (pair1,pair2) for (pair1,pair2) in adjacent_pairs(pair_stream)
     if sum_of_cubes(pair1) == sum_of_cubes(pair2)
    )
end

consecutive_matches (generic function with 1 method)

The results:

for t in taxi(75)
    println(sum_of_cubes(t[1]), ": ", t[1], " ", t[2], " :", sum_of_cubes(t[2]))
end

1729: (1, 12) (9, 10) :1729
4104: (2, 16) (9, 15) :4104
13832: (2, 24) (18, 20) :13832
20683: (10, 27) (19, 24) :20683
32832: (4, 32) (18, 30) :32832
39312: (2, 34) (15, 33) :39312
40033: (9, 34) (16, 33) :40033
46683: (3, 36) (27, 30) :46683
64232: (17, 39) (26, 36) :64232
65728: (31, 33) (12, 40) :65728
110656: (4, 48) (36, 40) :110656
110808: (6, 48) (27, 45) :110808
134379: (12, 51) (38, 43) :134379
149389: (8, 53) (29, 50) :149389
165464: (20, 54) (38, 48) :165464
171288: (24, 54) (17, 55) :171288
195841: (22, 57) (9, 58) :195841
216027: (3, 60) (22, 59) :216027
216125: (5, 60) (45, 50) :216125
262656: (8, 64) (36, 60) :262656
314496: (30, 66) (4, 68) :314496
320264: (18, 68) (32, 66) :320264
327763: (30, 67) (51, 58) :327763
373464: (54, 60) (6, 72) :373464
402597: (42, 69) (56, 61) :402597

This page was generated using Literate.jl.