Rosetta Code

Talk:Recaman's sequence: Difference between revisions

Page Discussion

Talk:Recaman's sequence (view source)

Revision as of 00:15, 20 September 2019

119,903 bytes added ,  4 years ago
m
→‎a scatter plot of the first 173 numbers of the Recaman sequence: elided a word.
(Created page with "__TOC__ ==a histogram of the first 173 numbers in the Recaman sequence==")
 
 
(9 intermediate revisions by 2 users not shown)
Line 2:
 
==a histogram of the first 173 numbers in the Recaman sequence==
(Shown at &nbsp; '''<sup>1</sup>/<sub>4</sub>''' &nbsp; size.)
<pre style="font-size:25%>
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├─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────■
</pre>
 
== a scatter plot of the first 173 numbers of the Recaman sequence ==
(Shown at &nbsp; '''<sup>1</sup>/<sub>10</sub>''' &nbsp; size.)
<pre style="font-size:10%>
│495                                                                                                                                                                                                                                                                                                                                          █     █
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 █
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                                                                                                                                                                                                                                    █
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                                                                                                                                                                          █
│                                                                                                                                                                                                                                                                                                                                                █     █
│
│
│
│                                                                                                                                                                                                                                                                                                             █     █     █
│                                                                                                                                                                                                                                                                                                       █
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   █    █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                            █    █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                     █    █
│                                                                                                                                                                                                                                                                                                                                                                                                                                   █     █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                        █     █
│                                                                                                                                                                                                                                                                                                                                                                                                 █          █     █
│                                                                                                                                                                                                                                                                                                                                                                                                      █
│                                                                                                                                                                                                                                                                                                     █                                 █
│                                                                                                                                                                                                                                                                                                          █     █     █                                                        █
│                                                                                                                                                                                                                                                                                                                            █                                       █     █
│                                                                                                                                                                                                                                                                                                                                                        █     █
│
│
│
│
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                                                    █     █
│                                                                                                                                                                                                         █    █
│                                                                                                                                                                                                   █
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                                                                                                                            █     █
│                                                                                                                                                                                                                                                                                █     █
│                                                                                                                                                                                                                                                                     █     █
│                                                                                                                                                                                                █     █                                             █    █     █
│                                                                                                                                                                                                           █     █                      █     █
│                                                                                                                                                                                                                       █     █    █                                                                                                 █
│                                                                                                                                                                                                                                                                                                                               █
│
│
│
│
│
│                                                                                                                                                                                                                                                                                                                                                           █     █     █                      █
│                                                                                                                                                                                                                                                                                                                                                                             █    █     █
│                                                                                                                                                                                                                                                                                                                                                                                                         █
│                                                                                                                                                                                                                                                                                                                                                                                                               █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                           █    █
│                                                                                                                                                                                                                                                                                                                                                                                                                                      █     █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                       █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                   █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                              █     █
│                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          █     █
│                                                                                                          █                                                                                                                                                                                                                                                                                                                                                                                          █     █
│                                                                                                    █
│
│
│
│
│
│
│
│
│
│                                                                                                                                                                                       █     █
│                                                                                                                                                                            █    █
│                                                                                                                                                                █     █
│                                                                                                                                               █     █    █
│                                                                                                                                   █     █
│                                                                                                 █                      █     █
│                                                                                                       █    █     █
│                                                                                                                                                                                                                                █
│                                                                                                                                                                                                                                     █     █     █
│                                                                                                                                                                                                                                                       █    █
│                                                                                                                                                                                                                                                                  █     █
│                                                                                                                                                                                                                                                                              █    █
│                                                              █                                                                                                                                                                                                                          █     █
│                                                         █
│
│
│
│
│
│
│                                                                                              █
│                                                                                  █     █
│                                                      █    █     █     █     █
│                                                                                                               █                                                                                                                                                                                                                 █
│                                                                                                                     █     █
│                                                                                                                                 █    █
│                                                                                                                                            █     █
│                                                                                                                                                        █    █     █
│                                                                                                                                                                         █     █
│                                                                                                                                                                                    █     █
│                                             █     █
│                            █     █    █
│                      █
│                                                                    █     █
│                                                                                █    █
│                   █                                                                       █
│                         █     █    █
│                                          █     █
│           █    █
│                                                                                                                                                                                                                                                                                                                                                                                     █     █
│0       █    █                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 173
└──█──█────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
</pre>
 
== A funny optimization that affects half of the implementations of this task ==
 
Several implementations of this task are translations of the same algorithm ([[Recaman%27s_sequence#AWK|AWK]], [[Recaman%27s_sequence#Microsoft_Small_Basic|Microsoft Small Basic]], [[Recaman%27s_sequence#C|C]], [[Recaman%27s_sequence#C.2B.2B|C++]], [[Recaman%27s_sequence#C.23|C#]], [[Recaman%27s_sequence#Go|Go]], [[Recaman%27s_sequence#D|D]], [[Recaman%27s_sequence#Kotlin|Kotlin]], [[Recaman%27s_sequence#Java|Java]], [[Recaman%27s_sequence#Julia|Julia]], [[Recaman%27s_sequence#Lua|Lua]], [[Recaman%27s_sequence#Objeck|Objeck]], [[Recaman%27s_sequence#Phix|Phix]], [[Recaman%27s_sequence#PHP|PHP]], [[Recaman%27s_sequence#Visual_Basic_.NET|Visual Basic .NET]] and my own one ([[Recaman%27s_sequence#F.C5.8Drmul.C3.A6|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.
 
[[User:Laurence|Laurence]] ([[User talk:Laurence|talk]]) 19:10, 19 September 2019 (UTC)
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/284456...284466"