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.

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: