Talk:Recaman's sequence

From Rosetta Code

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.

Laurence (talk) 19:10, 19 September 2019 (UTC)