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.

Advertisements

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

    
    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:

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: