## Triple Or Add Five

### July 27, 2018

We begin with a function that determines if a number *n* is reachable by tripling or adding five, starting from one:

(define (reachable? n) (if (< n 1) #f (or (= n 1) (and (zero? (modulo n 3)) (reachable? (/ n 3))) (reachable? (- n 5)))))

That works, but doesn’t give the sequence of triplings and increments. My favorite trick for keeping track of a recursive backtracking task uses a queue:

(define (triple-or-add-five n) (let loop ((queue (enqueue (make-queue) (list n)))) (if (empty? queue) #f (let ((seq (head queue)) (queue (tail queue))) (if (= (car seq) 1) seq (if (< (car seq) 1) (loop queue) (let ((queue (enqueue queue (cons (- (car seq) 5) seq)))) (if (zero? (modulo (car seq) 3)) (loop (enqueue queue (cons (/ (car seq) 3) seq))) (loop queue)))))))))

Let’s look at that slowly. A sequence of triplings and five-additions can be specified by the numbers that result at each step; for instance, two sequences that reach 24 are [1 3 8 24] and [1 3 9 14 19 24]. The queue initially contains the partial sequence [24], and always contains one or more items unless it is exhausted with a number that can’t be reached. From an initial queue of {[24]}, we pop the head of the queue, add a new sequence that subtracts 5, and, since 24 is divisible by 3, add another new sequence that divides by 3; at that point, the queue is {[19 24], [8 24]}. Now we pop [19 24] and push [14 19 24], giving the queue {[8 24], [14 19 24]}. Two more pops and pushes of five-additions give us the queue {[3 8 24], [9 14 19 24]}. Now the 3 at the beginning of the first partial sequence is divisible by 3, so we pop one and push two, giving {[9 14 19 24], [-2 3 8 24], [1 3 8 24]}, and the 9 at the beginning of the first partial sequence is divisible by 3, so we again pop one and push two, giving {[-2 3 8 24], [1 3 8 24], [4 9 14 19 24], [3 9 14 19 24]}. The first partial sequence underflows, so we pop it, and the next partial sequence, [1 3 8 24], starts with 1, so we have a solution. In effect, we perform breadth-first search on the triple-or-add-five graph as we build it on the fly; since it works breadth-first, it always finds the shortest sequence if there is more than one. Here are some examples:

> (triple-or-add-five 24) (1 3 8 24) > (triple-or-add-five 99) (1 6 11 33 99) > (triple-or-add-five 15) #f

You can run the program at https://ideone.com/SqaA2U, where you will also see the queue functions from a previous exercise.

He is a solution in Python, it prints all possible reductions for a number. I.e, n=54 already has 5 solutions.

Here’s a solution in Python.

Output:

Here’s a modified version of my earlier solution. This simpler and faster version does not use a heap for its queue.

Output

Here’s my solution in Forth. It uses a fixed-size lookup table with pre-computed paths:

Output:

Here is my take on this intriguing problem, using Julia (ver. 1.0):

function ReachableBy3or5(x::Integer)

if x == 1

println(1)

return true

elseif x < 1

return false

else

z = x / 3

z_rounded = round(Int64, z)

end

Not the most elegant piece of code, but it does the job. Examples:

julia> ReachableBy3or5(24)

1

3

8

24

true

julia> ReachableBy3or5(25)

false

Mumps/GT.M version