A364057 Lexicographically earliest infinite sequence of positive integers such that every subsequence {a(j), a(j+k), a(j+2k)} (j, k >= 1) is unique.

1, 1, 1, 2, 3, 1, 2, 4, 5, 6, 7, 8, 5, 1, 2, 9, 3, 4, 6, 7, 1, 10, 11, 12, 13, 8, 14, 15, 16, 3, 17, 9, 18, 4, 7, 19, 5, 2, 11, 12, 20, 6, 1, 8, 21, 22, 9, 23, 24, 13, 14, 3, 10, 16, 17, 25, 26, 19, 27, 6, 28, 11, 15, 20, 22, 29, 12, 21, 16, 23, 30, 18, 31, 32

Offset: 1

Author

Samuel Harkness, Oct 19 2023

Keywords

• nonn

Comments

To find a(n), two criteria must be satisfied:

1. Every subsequence {a(n-2k), a(n-k) a(n)} created by a(n) must be unique.

2. a(n) cannot create the scenario where a future a(m) will create multiple {a(m-2k), a(m-k), a(m)} regardless of choice for a(m). The first time this is the sole reason a candidate is denied is at a(10), see Example below.

Will every subsequence of 3 positive integers appear in arithmetic progression in this sequence?

Will every positive integer occur infinitely many times?

For n >= 3, a(n) != a(n+1).

In the 74 initially published terms, numbers on average seem to reoccur at (very) roughly twice the index of their previous occurrence. This seems worthy of better quantification when further terms are established. - Peter Munn, Nov 03 2023

Examples

			For a(9), we first try 1. If a(9) were 1, {a(3), a(6), a(9)} would be {1, 1, 1}, but this already occurred at {a(1), a(2), a(3)}.
Next, try 2. If a(9) were 2, {a(3), a(6), a(9)} would be {1, 1, 2}, but this already occurred at {a(2), a(3), a(4)}.
Next, try 3. If a(9) were 3, {a(3), a(6), a(9)} would be {1, 1, 3}, but this already occurred at {a(1), a(3), a(5)}.
Next, try 4. If a(9) were 4, {a(1), a(5), a(9)} would be {1, 3, 4}, but this already occurred at {a(2), a(5), a(8)}.
Then, try 5. New subsequences at indices {a(1), a(5), a(9)} = {1, 3, 5}, {a(3), a(6), a(9)} = {1, 1, 5}, {a(5), a(7), a(9)} = {3, 2, 5}, and {a(7), a(8), a(9)} = {2, 4, 5} are formed, none of which have occurred at any {a(j), a(j+k), a(j+2k)} (for any j and k) previously. No 5 has occurred previously, so criteria (2) in Comments must be satisfied. Thus a(9) = 5.
a(10) is the first time a candidate is denied solely because it would create a guaranteed future duplicate. Note that no subsequences prevent a(10) from being 4.
n    = 1  2  3  4  5  6  7  8  9 10 11 12 13 14
a(n) = 1  1  1  2  3  1  2  4  5 [4]          X
                      |           |           |
          |                 |                 |
If a(10) were 4, {a(2), a(8), a(14)} = {a(6), a(10), a(14)} = {1, 4, X}, making a subsequence {a(j), a(j+k), a(j+2k)} which is not unique. Therefore a(10) != 4.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Samuel Harkness, MATLAB program
• Rémy Sigrist, C++ program

Crossrefs

Cf. A229037, A362816, A366493, A366624.

Programs

MATLAB

See Links section.
(C++) See Links section.