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.
Programming Praxis 
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.
from heapq import heappop, heappush def find(n): if not (n % 5): return () queue = [(n,)] while queue: path = heappop(queue) x = path[0] if x == 1: return path if not (x % 3): heappush(queue, (x // 3,) + path) if x >= 6: heappush(queue, (x - 5,) + path) return () for n in range(25): path = find(n) if path: print("{}: {}".format(n, path)) for n in range(10 ** 10, 10 ** 10 + 25): path = find(n) if path: print("{}: {}".format(n, path))Output:
Here’s a modified version of my earlier solution. This simpler and faster version does not use a heap for its queue.
def find(n): if not (n % 5): return () queue = [(n,)] while queue: path = queue.pop() x = path[0] if x == 1: return path if x >= 6: queue.append((x - 5,) + path) if not (x % 3): queue.append((x // 3,) + path) return () for n in range(25): path = find(n) if path: print("{}: {}".format(n, path)) for n in range(10 ** 10, 10 ** 10 + 25): path = find(n) if path: print("{}: {}".format(n, path))Output
Here’s my solution in Forth. It uses a fixed-size lookup table with pre-computed paths:
CREATE TABLE 0 , 1 , 0 , 1 , 0 , 131067 CELLS ALLOT \ ~1MiB w/ 64bit cells : REACHABLE ( n) CELLS TABLE + @ ; : INIT 131072 5 DO I 3 MOD 0= I 3 / TUCK REACHABLE AND 0= IF DROP I 5 - DUP REACHABLE 0= IF DROP 0 THEN THEN I CELLS TABLE + ! LOOP ; : .PATH ( n) BEGIN DUP 1 <> WHILE DUP . REACHABLE REPEAT . ; : CHECK ( n) DUP REACHABLE IF .PATH ELSE DROP ." NO" THEN ; : DEMO 24 1 DO CR I 4 .R ." : " I CHECK LOOP ; INITOutput:
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
vista@steve-VirtualBox:~/EHR/r$ cat tripleaddfive.m tripleaddfive ; q ; go(n) ; n arr,cnt,path s path=1 d go2(.arr,n,path) i $d(arr) d . d wrt(.arr) q ; go2(arr,n,path) ; n i,num,path2,sum s sum=$$sum(path) i sum>n d . d nextorlower(.arr,n,path) e d . i sum=n d . . s path2=path . . f i=2:1:$l(path,",") d . . . s num=$p(path,",",i) . . . i num=3 d . . . . s $p(path2,",",i)=$p(path2,",",i-1)*3 . . . e d . . . . s $p(path2,",",i)=$p(path2,",",i-1)+5 . . s num=$l(path2,",") . . s arr(n,num,$i(num),path2)="" . . d nextorlower(.arr,n,path) . e d . . d go2(.arr,n,path_",3") q ; nextorlower(arr,n,path) ; n len,path2 q:$l(path,",")=1 s len=$l(path,",") s path2=$p(path,",",1,len-1) i $p(path,",",len)=3 d . d go2(.arr,n,path2_",5") e d . d nextorlower(.arr,n,path2) q ; sum(path) ; n i,sum s sum=1 f i=2:1:$l(path,",") d . i $p(path,",",i)=3 s sum=sum*3 . e s sum=sum+5 q sum ; wrt(arr) ; n glo s glo="arr" f s glo=$q(@glo) q:glo="" d . w !,$qs(glo,1),": ",$qs(glo,4) q Examples: GTM>f i=1:1:56 d go^tripleaddfive(i) 1: 1 3: 1,3 6: 1,6 8: 1,3,8 9: 1,3,9 11: 1,6,11 13: 1,3,8,13 14: 1,3,9,14 16: 1,6,11,16 18: 1,6,18 18: 1,3,8,13,18 19: 1,3,9,14,19 21: 1,6,11,16,21 23: 1,6,18,23 23: 1,3,8,13,18,23 24: 1,3,8,24 24: 1,3,9,14,19,24 26: 1,6,11,16,21,26 27: 1,3,9,27 28: 1,6,18,23,28 28: 1,3,8,13,18,23,28 29: 1,3,8,24,29 29: 1,3,9,14,19,24,29 31: 1,6,11,16,21,26,31 32: 1,3,9,27,32 33: 1,6,11,33 33: 1,6,18,23,28,33 33: 1,3,8,13,18,23,28,33 34: 1,3,8,24,29,34 34: 1,3,9,14,19,24,29,34 36: 1,6,11,16,21,26,31,36 37: 1,3,9,27,32,37 38: 1,6,11,33,38 38: 1,6,18,23,28,33,38 38: 1,3,8,13,18,23,28,33,38 39: 1,3,8,13,39 39: 1,3,8,24,29,34,39 39: 1,3,9,14,19,24,29,34,39 41: 1,6,11,16,21,26,31,36,41 42: 1,3,9,14,42 42: 1,3,9,27,32,37,42 43: 1,6,11,33,38,43 43: 1,6,18,23,28,33,38,43 43: 1,3,8,13,18,23,28,33,38,43 44: 1,3,8,13,39,44 44: 1,3,8,24,29,34,39,44 44: 1,3,9,14,19,24,29,34,39,44 46: 1,6,11,16,21,26,31,36,41,46 47: 1,3,9,14,42,47 47: 1,3,9,27,32,37,42,47 48: 1,6,11,16,48 48: 1,6,11,33,38,43,48 48: 1,6,18,23,28,33,38,43,48 48: 1,3,8,13,18,23,28,33,38,43,48 49: 1,3,8,13,39,44,49 49: 1,3,8,24,29,34,39,44,49 49: 1,3,9,14,19,24,29,34,39,44,49 51: 1,6,11,16,21,26,31,36,41,46,51 52: 1,3,9,14,42,47,52 52: 1,3,9,27,32,37,42,47,52 53: 1,6,11,16,48,53 53: 1,6,11,33,38,43,48,53 53: 1,6,18,23,28,33,38,43,48,53 53: 1,3,8,13,18,23,28,33,38,43,48,53 54: 1,6,18,54 54: 1,3,8,13,18,54 54: 1,3,8,13,39,44,49,54 54: 1,3,8,24,29,34,39,44,49,54 54: 1,3,9,14,19,24,29,34,39,44,49,54 56: 1,6,11,16,21,26,31,36,41,46,51,56