### 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)
(1 6 11 33 99)
#f```

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

Pages: 1 2

### 7 Responses to “Triple Or Add Five”

1. Rutger said

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

```def find3_5(n, calltree=[]):
if n < 1:
yield []
elif n == 1:
yield calltree+[1]
else:
# print(n)
if not n % 3:
yield from find3_5(n//3, calltree+[n])
if n > 5:
yield from find3_5(n-5, calltree+[n])

for n in range(1,100):
for result in sorted(list(find3_5(n)), key=len):
print(n, result)

# # Output
# 1 [1]
# 3 [3, 1]
# 6 [6, 1]
# 8 [8, 3, 1]
# 9 [9, 3, 1]
# 11 [11, 6, 1]
# 13 [13, 8, 3, 1]
# 14 [14, 9, 3, 1]
# 16 [16, 11, 6, 1]
# 18 [18, 6, 1]
# 18 [18, 13, 8, 3, 1]
# 19 [19, 14, 9, 3, 1]
# 21 [21, 16, 11, 6, 1]
# 23 [23, 18, 6, 1]
# 23 [23, 18, 13, 8, 3, 1]
# 24 [24, 8, 3, 1]
# 24 [24, 19, 14, 9, 3, 1]
# 26 [26, 21, 16, 11, 6, 1]
# 27 [27, 9, 3, 1]
# 28 [28, 23, 18, 6, 1]
# 28 [28, 23, 18, 13, 8, 3, 1]
# 29 [29, 24, 8, 3, 1]
# 29 [29, 24, 19, 14, 9, 3, 1]
# 31 [31, 26, 21, 16, 11, 6, 1]
# 32 [32, 27, 9, 3, 1]
# 33 [33, 11, 6, 1]
# 33 [33, 28, 23, 18, 6, 1]
# 33 [33, 28, 23, 18, 13, 8, 3, 1]
# 34 [34, 29, 24, 8, 3, 1]
# 34 [34, 29, 24, 19, 14, 9, 3, 1]
# 36 [36, 31, 26, 21, 16, 11, 6, 1]
# 37 [37, 32, 27, 9, 3, 1]
# 38 [38, 33, 11, 6, 1]
# 38 [38, 33, 28, 23, 18, 6, 1]
# 38 [38, 33, 28, 23, 18, 13, 8, 3, 1]
# 39 [39, 13, 8, 3, 1]
# 39 [39, 34, 29, 24, 8, 3, 1]
# 39 [39, 34, 29, 24, 19, 14, 9, 3, 1]
# 41 [41, 36, 31, 26, 21, 16, 11, 6, 1]
# 42 [42, 14, 9, 3, 1]
# 42 [42, 37, 32, 27, 9, 3, 1]
# 43 [43, 38, 33, 11, 6, 1]
# 43 [43, 38, 33, 28, 23, 18, 6, 1]
# 43 [43, 38, 33, 28, 23, 18, 13, 8, 3, 1]
# 44 [44, 39, 13, 8, 3, 1]
# 44 [44, 39, 34, 29, 24, 8, 3, 1]
# 44 [44, 39, 34, 29, 24, 19, 14, 9, 3, 1]
# 46 [46, 41, 36, 31, 26, 21, 16, 11, 6, 1]
# 47 [47, 42, 14, 9, 3, 1]
# 47 [47, 42, 37, 32, 27, 9, 3, 1]
# 48 [48, 16, 11, 6, 1]
# 48 [48, 43, 38, 33, 11, 6, 1]
# 48 [48, 43, 38, 33, 28, 23, 18, 6, 1]
# 48 [48, 43, 38, 33, 28, 23, 18, 13, 8, 3, 1]
# 49 [49, 44, 39, 13, 8, 3, 1]
# 49 [49, 44, 39, 34, 29, 24, 8, 3, 1]
# 49 [49, 44, 39, 34, 29, 24, 19, 14, 9, 3, 1]
# 51 [51, 46, 41, 36, 31, 26, 21, 16, 11, 6, 1]
# 52 [52, 47, 42, 14, 9, 3, 1]
# 52 [52, 47, 42, 37, 32, 27, 9, 3, 1]
# 53 [53, 48, 16, 11, 6, 1]
# 53 [53, 48, 43, 38, 33, 11, 6, 1]
# 53 [53, 48, 43, 38, 33, 28, 23, 18, 6, 1]
# 53 [53, 48, 43, 38, 33, 28, 23, 18, 13, 8, 3, 1]
# 54 [54, 18, 6, 1]
# 54 [54, 18, 13, 8, 3, 1]
# 54 [54, 49, 44, 39, 13, 8, 3, 1]
# 54 [54, 49, 44, 39, 34, 29, 24, 8, 3, 1]
# 54 [54, 49, 44, 39, 34, 29, 24, 19, 14, 9, 3, 1]
# 56 [56, 51, 46, 41, 36, 31, 26, 21, 16, 11, 6, 1]
```
2. matthew said
```#!/usr/bin/runghc
merge s [] = s
merge [] t = t
merge s0@((n,p):s) t0@((m,q):t)
| n < m = (n,p) : merge s t0
| n > m = (m,q) : merge s0 t
| otherwise = (n,p++q) : merge s t
app f (n,p) = (f n,map (n:) p)
s = (1,[[]]) : merge (map (app (*3)) s) (map (app (+5)) s)
main = mapM_ print (take 20 s)
```
```(1,[[]])
(3,[[1]])
(6,[[1]])
(8,[[3,1]])
(9,[[3,1]])
(11,[[6,1]])
(13,[[8,3,1]])
(14,[[9,3,1]])
(16,[[11,6,1]])
(18,[[6,1],[13,8,3,1]])
(19,[[14,9,3,1]])
(21,[[16,11,6,1]])
(23,[[18,6,1],[18,13,8,3,1]])
(24,[[8,3,1],[19,14,9,3,1]])
(26,[[21,16,11,6,1]])
(27,[[9,3,1]])
(28,[[23,18,6,1],[23,18,13,8,3,1]])
(29,[[24,8,3,1],[24,19,14,9,3,1]])
(31,[[26,21,16,11,6,1]])
(32,[[27,9,3,1]])
```
3. Daniel said

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:

```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)
19: (1, 3, 9, 14, 19)
21: (1, 6, 11, 16, 21)
23: (1, 6, 18, 23)
24: (1, 3, 8, 24)
10000000001: (1, 3, 8, 24, 72, ..., 1111111109, 3333333327, 3333333332, 9999999996, 10000000001)
10000000002: (1, 6, 18, 23, 69, ..., 1111111108, 3333333324, 3333333329, 3333333334, 10000000002)
10000000003: (1, 6, 11, 16, 21, ..., 3333333326, 3333333331, 9999999993, 9999999998, 10000000003)
10000000004: (1, 6, 11, 16, 21, ..., 1111111106, 1111111111, 3333333333, 9999999999, 10000000004)
10000000006: (1, 3, 8, 24, 72, ..., 3333333327, 3333333332, 9999999996, 10000000001, 10000000006)
10000000007: (1, 6, 18, 23, 69, ..., 3333333324, 3333333329, 3333333334, 10000000002, 10000000007)
10000000008: (1, 6, 11, 16, 21, ..., 370370369, 1111111107, 1111111112, 3333333336, 10000000008)
10000000009: (1, 6, 11, 16, 21, ..., 1111111111, 3333333333, 9999999999, 10000000004, 10000000009)
10000000011: (1, 3, 8, 24, 72, ..., 1111111109, 3333333327, 3333333332, 3333333337, 10000000011)
10000000012: (1, 6, 18, 23, 69, ..., 3333333329, 3333333334, 10000000002, 10000000007, 10000000012)
10000000013: (1, 6, 11, 16, 21, ..., 1111111107, 1111111112, 3333333336, 10000000008, 10000000013)
10000000014: (1, 6, 11, 16, 21, ..., 1111111106, 1111111111, 3333333333, 3333333338, 10000000014)
10000000016: (1, 3, 8, 24, 72, ..., 3333333327, 3333333332, 3333333337, 10000000011, 10000000016)
10000000017: (1, 6, 18, 23, 69, ..., 370370366, 370370371, 1111111113, 3333333339, 10000000017)
10000000018: (1, 6, 11, 16, 21, ..., 1111111112, 3333333336, 10000000008, 10000000013, 10000000018)
10000000019: (1, 6, 11, 16, 21, ..., 1111111111, 3333333333, 3333333338, 10000000014, 10000000019)
10000000021: (1, 3, 8, 24, 72, ..., 3333333332, 3333333337, 10000000011, 10000000016, 10000000021)
10000000022: (1, 6, 18, 23, 69, ..., 370370371, 1111111113, 3333333339, 10000000017, 10000000022)
10000000023: (1, 6, 11, 16, 21, ..., 1111111107, 1111111112, 3333333336, 3333333341, 10000000023)
10000000024: (1, 6, 11, 16, 21, ..., 3333333333, 3333333338, 10000000014, 10000000019, 10000000024)
```
4. Daniel said

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

```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)
19: (1, 3, 9, 14, 19)
21: (1, 6, 11, 16, 21)
23: (1, 6, 18, 23)
24: (1, 3, 8, 24)
10000000001: (1, 3, 8, 24, 72, ..., 1111111109, 3333333327, 3333333332, 9999999996, 10000000001)
10000000002: (1, 6, 18, 23, 69, ..., 1111111108, 3333333324, 3333333329, 3333333334, 10000000002)
10000000003: (1, 6, 11, 16, 21, ..., 3333333326, 3333333331, 9999999993, 9999999998, 10000000003)
10000000004: (1, 6, 11, 16, 21, ..., 1111111106, 1111111111, 3333333333, 9999999999, 10000000004)
10000000006: (1, 3, 8, 24, 72, ..., 3333333327, 3333333332, 9999999996, 10000000001, 10000000006)
10000000007: (1, 6, 18, 23, 69, ..., 3333333324, 3333333329, 3333333334, 10000000002, 10000000007)
10000000008: (1, 6, 11, 16, 21, ..., 370370369, 1111111107, 1111111112, 3333333336, 10000000008)
10000000009: (1, 6, 11, 16, 21, ..., 1111111111, 3333333333, 9999999999, 10000000004, 10000000009)
10000000011: (1, 3, 8, 24, 72, ..., 1111111109, 3333333327, 3333333332, 3333333337, 10000000011)
10000000012: (1, 6, 18, 23, 69, ..., 3333333329, 3333333334, 10000000002, 10000000007, 10000000012)
10000000013: (1, 6, 11, 16, 21, ..., 1111111107, 1111111112, 3333333336, 10000000008, 10000000013)
10000000014: (1, 6, 11, 16, 21, ..., 1111111106, 1111111111, 3333333333, 3333333338, 10000000014)
10000000016: (1, 3, 8, 24, 72, ..., 3333333327, 3333333332, 3333333337, 10000000011, 10000000016)
10000000017: (1, 6, 18, 23, 69, ..., 370370366, 370370371, 1111111113, 3333333339, 10000000017)
10000000018: (1, 6, 11, 16, 21, ..., 1111111112, 3333333336, 10000000008, 10000000013, 10000000018)
10000000019: (1, 6, 11, 16, 21, ..., 1111111111, 3333333333, 3333333338, 10000000014, 10000000019)
10000000021: (1, 3, 8, 24, 72, ..., 3333333332, 3333333337, 10000000011, 10000000016, 10000000021)
10000000022: (1, 6, 18, 23, 69, ..., 370370371, 1111111113, 3333333339, 10000000017, 10000000022)
10000000023: (1, 6, 11, 16, 21, ..., 1111111107, 1111111112, 3333333336, 3333333341, 10000000023)
10000000024: (1, 6, 11, 16, 21, ..., 3333333333, 3333333338, 10000000014, 10000000019, 10000000024)
```
5. bavier said

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  ;
INIT
```

Output:

```\$ gforth triple-or-add-five.fs -e "DEMO"
1: 1
2: NO
3: 3 1
4: NO
5: NO
6: 6 1
7: NO
8: 8 3 1
9: 9 3 1
10: NO
11: 11 6 1
12: NO
13: 13 8 3 1
14: 14 9 3 1
15: NO
16: 16 11 6 1
17: NO
18: 18 6 1
19: 19 14 9 3 1
20: NO
21: 21 16 11 6 1
22: NO
23: 23 18 6 1
```
6. Zack said

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)

``````    if z == z_rounded
if ReachableBy3or5(z_rounded); println(x); return true; end
end

if ReachableBy3or5(x - 5); println(x); return true; end
end

return false
``````

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

7. Steve said

Mumps/GT.M version

```
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:

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
```