Hi again,
Thanks a lot to
Fernando del Rey and
jonmoore for their interest and very kind words, much appreciated. Re the
OEIS (On-Line Encyclopedia of Integer Sequences), I heartily recommend reading these PDF documents to all people new to it:
Now for a little
self-quoting:
I Wrote:[...] Generating the sequence is trivial [...]
1 3 6 3 8 4 2 1 8 4 2 1 12 6 3 16 8 4 2 1 18 9 28 14 7 30 15 44 22 ...
and there's a number of interesting things to explore in the sequence.
Indeed there is, and presently I'll mention a couple. First of all,
the sequence is conjectured to include all positive integers 1, 2, 3, ..., as elements, and we can investigate this alleged fact by using this
5-liner for the
HP-71B, which takes as input
K, the maximum number of elements to generate, and will output the pairs
(number, index) for up to the first 60 numbers
(1..60), where
index is the lowest one where
number first appears in the sequence.
It will also output how many numbers weren't found within the first
K elements (plus timing) and finally it will explicitly list all numbers not found:
10 DESTROY ALL @ INPUT K @ INTEGER D(K),M(50) @ N=1 @ P=1 @ SETTIME 0
20 FOR C=1 TO K @ IF N>K THEN STD ELSE IF NOT D(N) THEN D(N)=C
30 IF MOD(N,2) THEN P=FPRIM(P+1) @ N=N+P ELSE N=N DIV 2
40 NEXT C @ C=0 @ FOR I=1 TO MIN(K,60) @ IF D(I) THEN DISP (I,D(I)); ELSE C=C+1 @ M(C)=I
50 NEXT I @ DISP @ DISP "Not found:";C;TIME$ @ FOR I=1 TO C @ DISP M(I); @ NEXT I @ DISP
Let's make a sample run specifying a maximum of
100 elements:
>RUN ? 100
(1,1) (2,7) (3,2) (4,6) (5,71) .. (48,42) (51,58) (53,73) (55,88) (58,33)
Not found: 21 (timing)
13 17 19 25 26 27 32 33 34 36 38 41 47 49 50 52 54 56 57 59 60
This means that
1 first appears at index
1,
2 at index
7,
3 at index
2,
4 at index
6,
5 at index
71, and so on until
55 appears at index
88 and
58 at index
33. We also learn that as many as
21 numbers from
1..60 didn't appear among the first
100 elements of the sequence, the first of them being
13, 17, ... and the last ones being ...
, 59, 60.
Of course, increasing the maximum number of elements to explore will probably result in finally locating the first occurrence of some or all the numbers not found within the first 100 elements of the sequence. Indeed, running the above program for
100, 200, ...., 2000 elements we get these results:
#Elem # Not found
--------------------------------------------------------------------------
100 21 13 17 19 25 26 27 32 33 34 36 38 41 47 49 50 52 54 56 57 59 60
200 12 13 25 26 27 32 36 41 49 50 52 54 60
500 8 25 27 32 36 49 50 54 60
1000 6 25 27 36 50 54 60
2000 4 27 36 54 60
and in fact only 4 numbers from
1..60 failed to make an appearance within the first
2,000 elements, corroborating the conjecture that all positive integers will eventually appear in the sequence.
Now we can try to locate the first occurrence of the 4 missing numbers
(27, 36, 54, 60) in a faster way and using minimal memory by running this
4-line HP-71B program, which will accept the number to locate and will search for it among the first
1,000,000 elements (if not using a very fast emulator, you might want to reduce this upper limit to save time; generating a million elements requires primes up to
4,761,697):
10 DESTROY ALL @ STD @ INPUT K @ N=1 @ P=1 @ SETTIME 0
20 FOR C=1 TO 1000000 @ IF N=K THEN DISP N;C;TIME$ @ END
30 IF MOD(N,2) THEN P=FPRIM(P+1) @ N=N+P ELSE N=N DIV 2
40 NEXT C @ DISP "Not found: ";TIME$
Let's try a sample run with an easily found number,
25:
>RUN
? 25 -> 25 1154 (timing)
which quickly tells us that
25 appears in the sequence at index
1,154. Now let's consider the four numbers which weren't located earlier within the first 2,000 elements, namely
27, 36, 54 and 60, to try and locate their first occurrence in the sequence, if possible:
>RUN
? 27 -> 27 161336 (Emu71/Win @972x: 28", go71b @128x: 3'36", Physical: 7h 41')
? 60 -> 60 614667 (Emu71/Win @972x: 3'3", go71b @128x: 23'14", Physical: ~ 50h)
so
27 appears for the first time in the sequence at index
161,336 and
60 at index
614,667. As for
54, being twice
27, we don't need to search for it, its index will be
one less than the one for
27, namely
161,335.
Unfortunately, the search up to index
1,000,000 fails for
36 because its first occurrence in the sequence happens to be at index
77,534,485,877 !!. Even worse, if considering numbers up to
100 instead of up to
60, the number
97 first appears at index
17,282,073,747,557 !!!
Additionally,
a second conjecture is that every positive integer appears in the sequence not just once but an infinite number of times. We can check it out by finding multiple indexes for any given input number, simply delete the
END statement at
line 20 and reduce to
100,000 the maximum index to search up to. Line
20 will then look like this:
20 FOR C=1 TO 100000 @ IF N=K THEN DISP N;C;TIME$
Let's try a few selected numbers
(you may break execution before reaching index 100,000, to save time):
>RUN
? 1 -> 1 8 12 20 742 ... (the very next appearance is at index 513,152,128)
? 2 -> 7 11 19 741 ... (ditto at index 513,152,127)
? 3 -> 2 4 15 46 95 6355 ...
? 5 -> 71 4849 ... (no others up to index 1,000,000)
? 7 -> 25 114 123 446 7104 ...
? 13 -> 345 418 4621 ... (no others up to index 1,000,000)
? 25 -> 1154 1519 10359 13330 ... (no others up to index 1,000,000)
? 85 -> 140 3161 72349...
so it seems that indeed there might be infinite appearances of any positive integer but the distance from one appearance to the next increases at an extremely fast rate.
Additional Trivia:
● A few other nice appearances are
31416 at indexes
6,768 and
6,923,
11111 at
12,497,
55555 at
56,551,
100000 at
26,488 and last but not least,
2023 at
2,165. On the other hand,
1992 does
not appear within the first
1,000,000 elements.
● There's a number of solutions of
A(n) = n, i.e. numbers whose index in the sequence equals the number itself. They can be found very easily with a trivial modification of my second program above, and the first ones are
n =
1,
16,
787,
427447 and no others up to index
1,000,000.
Regards.
V.
![[Image: Wheel%20factorization%20size%2030.JPG]](https://primorial-sieve.com/Pic_sav/Wheel%20factorization%20size%2030.JPG)