For Gavin L.

Hello Gavin,

It’s time to face some serious challenges!-)

The idea

—> We ask a bunch of kids to paint in red all the pairs of successive digits they can find in the seq S — but only if this pair is made of contiguous digits of opposite parity (like 1,4 or 7,2 or 0, 9); 

—> the digits may belong to two different integers (after painting red the digits of the segment … 480, 133, 54, … the black remaining digits will form 48., .33, ..); 

—> once a pair is painted red, the kids do NOT iterate from there: the above segment [… 480, 133, 54, …] does not become [… 480, 133, 54, …] and this one doesn’t become fully red at the « next step » [… 480, 133, 54, …] as there are no successive such steps.

—> the kids work SIMULTANEOUSLY, they start to paint S where they want — no one expects the result of someone else to proceed with the painting.

That’s it!

When the kids are finished, they make a step back and look at the seq: surprise, the black remaining digits, concatenated, form exactly the concatenation of the initial integers of S!

Our secret

In designing the seq it was decided:
—> S must be the lexicographically earliest seq of distinct integers > 0 such that, obeying all rules expressed here, the two concatenations are the same;
—> kids will never hesitate when they hold their red brush: they will never encounter an integer like 123 as 123 contains (with overlap) two pairs of digits of opposite parity: « Do I paint in red the pair 12 of 123 or the pair 23? » No. Similarly, this ambiguity will not strike them when they encounter two successive integers — like in 112, 357 where the 2 belongs to two pairs of digits of opposite parity, producing the overlap [123].

Last remark

As, in the end, we concatenate all black digits, we keep all black « leading zeros » when they appear: 1008 will leave 08 in black, NOT a solitary 8 — we must see 08 as a string of symbols, not an integer.

The algorithm

Start S with a(1) = 1
Always extend S with the smallest integer not present in S that doesn’t lead to an immediate contradiction.

Example explained

S = 1, ...
S = 1,2, ...

S = 1,2, ...

We now extend S with 4 as 3 would be ambiguous — producing two red overlapping pairs [123];

S = 1,2,4, ...
S = 1,2,4,3, ...

S = 1,2,4,3,5,6,8,7,9, ...

Now what? If we extend S with 10 we will have:

S = 1,2,4,3,5,6,8,7,9,10, ...

... and 9 will never be painted red (10 will, but without affecting 9 whatsoever). Remember that keeping 9 is forbidden, as 9 doesn’t open S, but 1 does [a(1) = 1].

This means that we must immediately form a red pair including the said 9. We must thus extend S not with 10 but with 20 — the smallest available integer beginning with an even digit:

S = 1,2,4,3,5,6,8,7,9,20, ... S = 1,2,4,3,5,6,8,7,9,20, ...

The smallest unused integer so far is 10 — but 10 is forbidden after 20, as we would have again two overlapping red pairs [010]; we try 11 instead of 10:

S = 1,2,4,3,5,6,8,7,9,20,11, ...

S = 1,2,4,3,5,6,8,7,9,20,11, ...

Good, we try now to extend S with 10 again, as this is the smallest unused integer so far:

S = 1,2,4,3,5,6,8,7,9,20,11,10, ...
S = 1,2,4,3,5,6,8,7,9,20,11,10, ...

—> Ah ah! Seems we might have a hit! The last digit of 11 will stay forever in black — and this is precisely what we were looking for [as a(1) = 1]!

[Our next such « forever black digit » will be a 2 — because a(2) = 2]

We cannot go on extending with 12 — as this 12 would produce the two overlapping red pairs [012].

This means that the next integer cannot start with a 1 (or any other odd digit); we try 21 instead of 12 (as 20 is already present in S):

S = 1,2,4,3,5,6,8,7,9,20,11,10,21, ...
S = 1,2,4,3,5,6,8,7,9,20,11,10,21, ...

21 turns red, no problem — and we go on extending now with 12, the smallest available... etc.

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12, ...

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12, ...

12 turns red, we try to go on with 13:

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,13, ...

No, impossible, we have two overlapping red pairs due to 13 [121].

The next integer cannot start with a 1; we try 22 instead of 13 (as 22 is the smallest available integer not leading to an immediate contradiction):

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,22, ...

—> Ah ah! We have another hit! The first digit of 22 will stay forever in black, no matter the next term — and this is precisely what we were looking for!

[Our next such « forever black digit » will be a 4 — because a(3) = 4]

We extend S with 13 now — the smallest... etc. This is ok:

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,22,13, ...
S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,22,13, ...

We cannot extend S now with an integer that starts with an odd digit — as this would leave the 3 of 13 in black, which is not what we are looking for (as said above, we want a « forever » black 4 now); we try 23, the smallest... etc. 

 

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,22,13,23, ...

But this 23 produces the red overlap [323]; we try 24 instead of 23; which is better: 

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,22,13,24, ...

S = 1,2,4,3,5,6,8,7,9,20,11,10,21,12,22,13,24, ...

etc.  

Here is S, computed so far by me (and by hand — caveat!), it looks like this:

S = 1, 2, 4, 3, 5, 6, 8, 7, 9, 20, 11, 10, 21, 12, 22, 13, 24, 15, 26, 17, 28, 19, 40, 31, 42, 33, 44, 23 (third hit, we'll keep forever in black the last 4 of 44), 14, 25, 16, 27, 18, 29, 30, 41, 32, 43, 34, 45, 35, 36 (fourth and fifth hit, we'll keep forever in black the string 35), 47, 38, 49, 50, 60, 37 (sixth hit, we'll keep forever in black the 6 of 60), 46, 39, 48, 51, 62, 53, 64, 55, 66, 57, 68, 59, ...

Hits are in "aqua" below – and the no-hits are in red; we see that the aqua digits slowly reproduce the concatenation of S's terms – which is what we're fighting for !-).

S = 1, 2, 4, 3, 5, 6, 8, 7, 9, 20, 11, 10, 21, 12, 22, 13, 24, 15, 26, 17, 28, 19, 40, 31, 42, 33, 44, 23, 14, 25, 16, 27, 18, 29, 30, 41, 32, 43, 34, 45, 35, 36, 47, 38, 49, 50, 60, 37, 46, 39, 48, 51, 62, 53, 64, 55, 66, 57, 68, 59, ...

What do you think, Gavin?

[I don't expect the graph to be particularly original, unfortunately]

Best,

É.