Traversing the Infinite Sidewalk
Imagine standing on the first square of an infinite sidewalk labelled 1,1,2,2,3,3… Whenever you are on a square labelled k, you may jump k squares in either direction to another square, as depicted above.
What is the minimal number of jumps required to reach the nth square?
The sequence begins 0,1,2,5,3,6,9,4… For example, the fourth term is 5, because to get to the fourth square (labelled “2”), the quickest way is to jump: forward, forward, forward, forward, backward!
One can prove that it’s possible to reach any square, so this sequence is well defined (but we’re interested in alternate proofs; do try to demonstrate that yourself if you please!)
The sequence seems rather chaotic: the amount of backtracking required is hard to predict! However, it starts becoming structured in strange ways. Here are the first 500 terms:
0, 1, 2, 5, 3, 6, 9, 4, 7, 10, 10, 5, 8, 8, 11, 11, 11, 6, 14, 9, 9, 12, 12, 12, 15, 12, 7, 18, 15, 10, 10, 10, 13, 13, 13, 13, 16, 16, 13, 16, 8, 19, 19, 16, 11, 11, 11, 11, 19, 14, 14, 14, 14, 14, 22, 17, 17, 17, 14, 17, 17, 9, 20, 20, 20, 17, 17, 12, 12, 12, 12, 12, 23, 20, 15, 15, 15, 15, 15, 15, 15, 26, 23, 18, 18, 18, 18, 18, 15, 18, 18, 18, 10, 21, 21, 21, 21, 21, 18, 18, 18, 13, 21, 13, 13, 24, 13, 13, 24, 24, 21, 21, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 27, 27, 24, 19, 19, 19, 19, 19, 19, 19, 19, 16, 19, 19, 19, 19, 30, 11, 22, 22, 22, 22, 22, 22, 22, 22, 19, 19, 19, 19, 14, 22, 22, 14, 14, 14, 25, 25, 14, 14, 25, 25, 25, 25, 22, 22, 22, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 28, 28, 28, 28, 25, 20, 25, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 17, 20, 20, 20, 20, 20, 20, 31, 31, 12, 28, 23, 23, 28, 23, 23, 23, 23, 23, 23, 23, 23, 23, 20, 20, 20, 20, 20, 23, 15, 23, 23, 23, 15, 34, 15, 15, 26, 26, 26, 31, 15, 15, 26, 26, 26, 26, 26, 26, 26, 23, 23, 23, 23, 18, 23, 18, 18, 18, 18, 18, 26, 18, 18, 18, 18, 18, 29, 18, 18, 34, 18, 18, 18, 18, 29, 29, 29, 29, 29, 29, 26, 26, 21, 26, 26, 21, 21, 21, 21, 21, 21, 21, 21, 29, 21, 21, 21, 21, 21, 21, 18, 21, 21, 21, 21, 21, 21, 21, 21, 21, 32, 32, 32, 13, 32, 29, 24, 24, 24, 29, 29, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 21, 24, 21, 21, 21, 21, 21, 24, 24, 16, 24, 24, 24, 24, 24, 16, 35, 35, 16, 16, 16, 27, 27, 27, 27, 32, 32, 16, 27, 16, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 24, 24, 27, 24, 24, 24, 19, 24, 24, 19, 19, 19, 19, 19, 27, 19, 27, 27, 19, 19, 38, 19, 19, 19, 19, 30, 30, 19, 19, 35, 35, 19, 19, 19, 19, 30, 19, 30, 30, 30, 30, 30, 30, 30, 30, 30, 27, 27, 27, 22, 27, 27, 27, 27, 22, 22, 27, 22, 22, 22, 22, 22, 22, 22, 22, 30, 30, 22, 22, 22, 22, 22, 22, 22, 22, 22, 19, 22, 22, 22, 38, 22, 22, 22, 22, 22, 22, 22, 22, 33, 22, 33, 33, 33, 33, 33, 14, 33, 33, 30, 25, 30, 25, 25, 30, 30, 30, 30, 25, 25, 30, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25.
Note the big streaks of repetition, and even more surprisingly, different patches “bleed into each other”, as in the subsequence “…27, 27, 27, 22, 22, 27, 22, 22, 22…”
Furthermore, despite adjacent numbers often requiring the same number of steps to reach, the corresponding shortest paths are often very different! Here are the shortest paths for 112 to 121 (note we zero-index here!), all requiring 16 steps:
112. 0, 1, 2, 4, 7, 11, 17, 26, 12, 19, 29, 44, 21, 32, 49, 74, 112
113. 0, 1, 2, 4, 7, 11, 17, 26, 12, 19, 29, 44, 67, 101, 152, 75, 113
114. 0, 1, 2, 4, 7, 11, 17, 26, 12, 19, 29, 44, 67, 101, 152, 229, 114
115. 0, 1, 2, 4, 7, 11, 17, 26, 12, 19, 29, 44, 67, 33, 50, 76, 115
116. 0, 1, 2, 4, 7, 11, 17, 26, 40, 61, 92, 45, 68, 103, 51, 77, 116
117. 0, 1, 2, 4, 7, 11, 17, 26, 40, 61, 92, 139, 209, 314, 156, 235, 117
118. 0, 1, 2, 4, 7, 11, 17, 26, 40, 61, 92, 139, 69, 104, 157, 78, 118
119. 0, 1, 2, 4, 7, 11, 17, 26, 12, 19, 9, 14, 22, 34, 52, 79, 119
120. 0, 1, 2, 4, 7, 11, 17, 26, 40, 61, 30, 46, 70, 106, 160, 241, 120
121. 0, 1, 2, 4, 7, 3, 5, 8, 13, 20, 31, 15, 23, 35, 53, 80, 121
Can you explain any of the above behaviors? How tightly can you bound this sequence above and below? Are there other interesting patterns you can find? How about interesting variants/modifications to the sequence?
Feel free to submit any thoughts to math-solutions@janestreet.com.