Talk:Recaman's sequence
a histogram of the first 173 numbers in the Recaman sequence
(Shown at 1/4 size.)
0│ 1├■ 3├──■ 6├─────■ 2├─■ 7├──────■ 13├────────────■ 20├───────────────────■ 12├───────────■ 21├────────────────────■ 11├──────────■ 22├─────────────────────■ 10├─────────■ 23├──────────────────────■ 9├────────■ 24├───────────────────────■ 8├───────■ 25├────────────────────────■ 43├──────────────────────────────────────────■ 62├─────────────────────────────────────────────────────────────■ 42├─────────────────────────────────────────■ 63├──────────────────────────────────────────────────────────────■ 41├────────────────────────────────────────■ 18├─────────────────■ 42├─────────────────────────────────────────■ 17├────────────────■ 43├──────────────────────────────────────────■ 16├───────────────■ 44├───────────────────────────────────────────■ 15├──────────────■ 45├────────────────────────────────────────────■ 14├─────────────■ 46├─────────────────────────────────────────────■ 79├──────────────────────────────────────────────────────────────────────────────■ 113├────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 78├─────────────────────────────────────────────────────────────────────────────■ 114├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 77├────────────────────────────────────────────────────────────────────────────■ 39├──────────────────────────────────────■ 78├─────────────────────────────────────────────────────────────────────────────■ 38├─────────────────────────────────────■ 79├──────────────────────────────────────────────────────────────────────────────■ 37├────────────────────────────────────■ 80├───────────────────────────────────────────────────────────────────────────────■ 36├───────────────────────────────────■ 81├────────────────────────────────────────────────────────────────────────────────■ 35├──────────────────────────────────■ 82├─────────────────────────────────────────────────────────────────────────────────■ 34├─────────────────────────────────■ 83├──────────────────────────────────────────────────────────────────────────────────■ 33├────────────────────────────────■ 84├───────────────────────────────────────────────────────────────────────────────────■ 32├───────────────────────────────■ 85├────────────────────────────────────────────────────────────────────────────────────■ 31├──────────────────────────────■ 86├─────────────────────────────────────────────────────────────────────────────────────■ 30├─────────────────────────────■ 87├──────────────────────────────────────────────────────────────────────────────────────■ 29├────────────────────────────■ 88├───────────────────────────────────────────────────────────────────────────────────────■ 28├───────────────────────────■ 89├────────────────────────────────────────────────────────────────────────────────────────■ 27├──────────────────────────■ 90├─────────────────────────────────────────────────────────────────────────────────────────■ 26├─────────────────────────■ 91├──────────────────────────────────────────────────────────────────────────────────────────■ 157├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 224├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 156├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 225├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 155├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 226├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 154├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 227├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 153├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 228├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 152├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 75├──────────────────────────────────────────────────────────────────────────■ 153├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 74├─────────────────────────────────────────────────────────────────────────■ 154├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 73├────────────────────────────────────────────────────────────────────────■ 155├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 72├───────────────────────────────────────────────────────────────────────■ 156├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 71├──────────────────────────────────────────────────────────────────────■ 157├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 70├─────────────────────────────────────────────────────────────────────■ 158├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 69├────────────────────────────────────────────────────────────────────■ 159├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 68├───────────────────────────────────────────────────────────────────■ 160├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 67├──────────────────────────────────────────────────────────────────■ 161├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 66├─────────────────────────────────────────────────────────────────■ 162├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 65├────────────────────────────────────────────────────────────────■ 163├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 64├───────────────────────────────────────────────────────────────■ 164├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 265├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 367├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 264├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 368├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 263├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 369├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 262├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 370├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 261├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 151├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 40├───────────────────────────────────────■ 152├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 265├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 379├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 494├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 378├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 495├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 377├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 258├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 138├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 259├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 137├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 260├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 136├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 261├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 135├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 262├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 134├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 5├────■ 135├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 4├───■ 136├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 269├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 403├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 268├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 132├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 269├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 131├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 270├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 130├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 271├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 129├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 272├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 128├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 273├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 127├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 274├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 126├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 275├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 125├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 276├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 124├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 277├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 123├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 278├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 122├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 279├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 121├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 280├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 120├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 281├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 119├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 282├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 118├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 283├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 117├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 284├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 116├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 285├────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 115├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 286├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■ 458├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■
a scatter plot of the first 173 numbers of the Recaman sequence
(Shown at 1/10 size.)
│495 █ █ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ █ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ █ │ │ │ │ │ │ │ │ │ │ █ │ █ █ │ │ │ │ █ █ █ │ █ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ █ █ █ │ █ █ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ █ │ █ █ █ │ █ │ █ █ │ █ █ █ █ │ █ █ █ │ █ █ │ │ │ │ │ │ │ │ │ │ │ │ │ │ █ █ │ █ █ │ █ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ █ █ │ █ █ │ █ █ │ █ █ █ █ █ │ █ █ █ █ │ █ █ █ █ │ █ │ │ │ │ │ │ █ █ █ █ │ █ █ █ │ █ │ █ █ │ █ █ │ █ █ █ │ █ █ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ │ │ │ │ │ │ │ │ │ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ █ │ █ █ █ │ █ █ █ │ █ │ █ █ █ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ │ │ │ │ │ │ │ █ │ █ █ │ █ █ █ █ █ │ █ █ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ │ █ █ │ █ █ │ █ █ │ █ █ █ │ █ █ │ █ █ │ █ █ │0 █ █ 173 └──█──█────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
A funny optimization that affects half of the implementations of this task
Several implementations of this task are translations of the same algorithm (AWK, Microsoft Small Basic, C, C++, C#, Go, D, Kotlin, Java, Julia, Lua, Objeck, Phix, PHP, Visual Basic .NET and my own one (Fōrmulæ), 16 at the moment of writing this comment). The reason is simple, the algorithm used is compact, fast and clear.
However, a further optimization can be done. In order to detect when the 0..1000 integers are generated, it uses a set or array (usually named "used1000", initially containing the zero element) in order to store the numbers <= 1000 that were already generated. It is unnecessary, the same can be performed with a scalar initialized as 1, and incremented every time a new integer is generated. It will never be added again (for the same integer), because it is prevented by the testing for the integer in a unique set or array (usually named "used").
Note that the "used1000" array (or set) is never used to retrieve an element in any position, or the existence of a given element. Instead, it is used solely to check its size.
This optimization affects the space, not the time performance, because it is better to have a scalar instead of an unused 1001-element set or array.