## 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.

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

Here’s a solution in Python.

Output:

Here’s a modified version of my earlier solution. This simpler and faster version does not use a heap for its queue.

Output

Here’s my solution in Forth. It uses a fixed-size lookup table with pre-computed paths:

Output:

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)

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

Mumps/GT.M version