Reverse search with a decision tree

A programming exercise in tracing integer transformation rules backwards. The question, reasoning, tree, implementation, and recorded result follow in that order.

Question

For an odd integer, subtract one. For an even integer, divide by two. Say that you were given an integer, and you have processed it with the abovementioned rules for i times until it become 0.

What are the possible integers, if `i` was any given value?

Thinking

For a positive starting value that takes at least two steps to reach zero, the final two steps are 2 → 1 → 0. Assuming that i=5, I just need to START from “2” with 3 steps. Reverse the transformations to construct the preceding layer of the tree: The rules are:

if the value is a even number, then it create 2 new values by: +1 and *2.* (For example, if the value is 2, I will get 2 new values, 3 and 4)*
if the value is an odd number, then it create only 1 new value by: +1. (For example, if the value is 5, I will get 6)

The result should be like a decision tree with many layers:

1st layer: 2
2nd layer: 3 4
3rd layer: 6 5 8
4th layer: ????
.
.

Code

Create a function to generate new integers based on the reverse rules

generate_next_values <- function(value) {
  if (value %% 2 == 0) {
    return(c(value + 1, value * 2))
  } else {
    return(value * 2)
  }
}

Main code (assuming 10 rounds were required)

which means 10-2=8 rounds

round = 8         # How many round (start from 2)
start <- vector(mode='list', length=round+1)   # generate an empty list, with (round+1) layers (because the 1st layer is "2")


start[[1]] = c(2) # 1st layer: 2



# while and for loop
i = 1             
while (i <= round) {
  
  
        for (num in 1:length(start[[i]])) {
        start[[i+1]] =  c(start[[i+1]], generate_next_values(start[[i]][num]))
        }
  
      i = i+1
}

print(start)

The generate_next_values() function will process on each values (for looop) in the i layer (while loop). i will +1 on each run until i == round. After 8 rounds of process, the 9th layer looks like:

[[1]]
[1] 2

[[2]]
[1] 3 4

[[3]]
[1] 6 5 8

[[4]]
[1]  7 12 10  9 16

[[5]]
[1] 14 13 24 11 20 18 17 32

[[6]]
 [1] 15 28 26 25 48 22 21 40 19 36 34 33 64

[[7]]
 [1]  30  29  56  27  52  50  49  96  23  44  42  41  80  38  37  72  35  68  66  65 128

[[8]]
 [1]  31  60  58  57 112  54  53 104  51 100  98  97 192  46  45  88  43  84  82  81 160  39  76  74  73 144  70  69 136  67 132 130 129 256

[[9]]
 [1]  62  61 120  59 116 114 113 224  55 108 106 105 208 102 101 200  99 196 194 193 384  47  92  90  89 176  86  85 168  83 164 162 161 320
[35]  78  77 152  75 148 146 145 288  71 140 138 137 272 134 133 264 131 260 258 257 512

These are the possible integers that will become 0 after 10 rounds of process.

← Back to projects