### July 27, 2018

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be generated. For instance, starting from 1, you can triple to get 3, then add five to get 8, and finally triple to get 24, so 24 is reachable. On the other hand, 15 is not reachable, as a little thought will show.

Your task is to write a program that determines if a number n is reachable by tripling or adding five, and if the number is reachable to give the sequence of operations by which it can be reached. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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