Triple Or Add Five

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.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
7 Comments »

7 Responses to “Triple Or Add Five”

  1. Rutger said
    July 27, 2018 at 11:00 AM

    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
    July 27, 2018 at 3:47 PM 
    #!/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
    July 27, 2018 at 7:48 PM

    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
    July 29, 2018 at 1:44 PM

    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
    August 8, 2018 at 8:05 PM

    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
    August 13, 2018 at 2:53 PM

    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
    August 14, 2018 at 3:30 PM

    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

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: