A key/value nightmare sequence

[Loutcho Glotuk]

Hi to all,

Let us play with an associative array T. At generation j = 0, T is initialized with one entry,
T[1] = 1.

The evolution rule to get the T of the next generation is:
    for each key-value pair (k, v) in T, cumulate (v, k) in T.

In order to avoid the ambiguities inherent to in-place modifications and to the meaning of "cumulate", let's reformulate. Let T(j) denote the T of generation j. The evolution rule is:
T(j+1) is T(j) cloned and modified by:
for each key-value pair (k,v) in T(j),
    if v is a key in T(j+1),
    then T(j+1)[v] := T(j+1)[v] + k      (an update),
    else T(j+1)[v] := k        (an insertion).

We can make an integer sequence from that problem, that I would dream to add to the OEIS:
>> what is the set of the numbers that eventually become keys in T?
Comes to the same:
>> what is the set of the numbers that eventually become values in T?

1, 2, 4, 6, 8, 10, 12, 16, 20, 24, 26, 28, 30, 32, 34, 44, ...

But I can't prove that the first few terms above are accurate! Because I want the set to be complete and sorted in ascending order, some terms might already be missing.

What tells I pursued the calculations to a sufficient j to get all those <= 44?

May be we can prove a few things:
- 3 is not in the sequence
- 1 is the only odd number in the sequence
But how can we prove, for instance, that we'll never get 14?
Is there a rigorous algorithm that generates the sequence?

Regards,
Luc

Illustrated:

caption

- lines = keys

- columns = generations (j)

- cell contents = values

- colors = { green-> creation of new key with a value which is not new, blue -> update with a value which is new, turquoise -> creation of new key with a value which is new, yellow -> update with a value which is not new, grey-> no update }

Sans virus.www.avg.com

[Jonas Karlsson]

Fun!

Using a defaultdict(int) in Python we can just do T[v] += k, right? I.e. something like

Tnew = copy.deepcopy(T)

for (k, v) in T.items():

     Tnew[v] += k

T = Tnew

Does that capture your intention? 

Jonas

[Loutcho Glotuk]

Absolutely

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/d19bfb62-cfab-43c0-b605-a3ac75b056c1n%40googlegroups.com.

[Ruud H.G. van Tol]

On 2025-11-23 15:27, Loutcho Glotuk wrote:
> [...] Let T(j) denote the T of generation j. The evolution rule is:

> T(j+1) is T(j) cloned and modified by:
> for each key-value pair (k,v) in T(j),

>     if v is a key in T(j+1), [...]

Be aware that this checks in the new map, so a freshly inserted entry
can get already updated.

-- Ruud

[Ruud H.G. van Tol]

\\ (PARI)
lista( g= 40 )= {
  my( m= Map( Mat([1, 1]) ) );
  for( j= 0, g
  , my( t= m );  \\ clone
    foreach( t, e
    , my( [k, v]= e[1], z );
      mapput( ~m, v
      , if( mapisdefined( m, v, &z ), z+k, k)
      )
    )
  );
  Vec(m)[ 1 .. min(#m, g) ]
}

? lista(40)
%1 = [1, 2, 4, 6, 8, 10, 12, 16, 20, 24, 26, 28, 30, 32, 34, 44, 46, 52,
54, 60, 62, 64, 66, 68, 72, 80, 82, 88, 90, 100, 104, ...]

-- Ruud

[Loutcho Glotuk]

Ruud, thank you for your proposition of a program.

But it does not catch the essence of my question.

Your program computes successive versions of T but does not guarantee that the first few terms it outputs are the first and contiguous ones in the A-sequence (... of the numbers that ultimately become a key in T) .

For example, 6 is in the A sequence, but one has to wait j = 10 before 6 actually becomes a key in T, given the way we do the computations (I have a program similar to yours).

If we use the program to compute, say, lista(8)[4], we get 8, not 6. As we know that the A-sequence starts with 1, 2, 4, 6, or with even smaller numbers than that, lista(8) can't be the start of the sought A sequence.

I am convinced that this program is useful for experimentations, but it shouldn't be named lista(). I named it evolve(ntimes).

Luc

PS: by the way, to compute g successive versions of T with your program (not g + 1), I think that j should be initialized 1, not 0, in the for loop.

Otherwise a ±1 offset is introduced in the indices compared to my definition. I was surprised to see lista(9)[4] answer 6, where evolve(9)[4] was still answering 8.

Sans virus.www.avg.com

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/1194f53c-116f-40c4-b3e9-0aa4633c8aac%40isolution.nl.

[M F Hasler]

On Sun, Nov 23, 2025 at 6:03 PM Loutcho Glotuk <luc.ro...@gmail.com> wrote:

Ruud, thank you for your proposition of a program.

But it does not catch the essence of my question.

Yes, obviously it's trivial to program it, e.g. in Python:

T={1:1}

for generation in range(50):

   for k,v in tuple(T.items()): T[v] = T.get(v,0)+k

sorted(T)[:30]

[1, 2, 4, 6, 8, 10, 12, 16, 20, 24, 26, 28, 30, 32, 34, 44, 46, 52, 54, 60, 62, 64, 66, 68, 72, 80, 82, 88, 90, 100, 104]

but it doesn't provide an answer to the questions.

However, we can indeed prove that 1 is the only odd key that will ever appear.

More specifically, we can prove that ("at" means "at the end of"):

(a) - key k = 1 has value  v = 2^j at generation g = 2j and g = 2j-1 (for j>0).

(b) - the value v = 1 occurs only for keys k = 2^j,

  and only at generation g = 2j we have the (key, value) pair (2^j , 1),

(Proof by induction: The statement is true up to j=1, i.e., at generation 2j-1 = 1 and at generation 2j = 2.

Assume it's true up to some j, and let's consider what happens for j+1.

* At generation g = 2(j+1)-1 = 2j+1, the respective (key,value) pairs lead to following updates:

(k,v) = (1, 2^j) => T[ 2^j ] with previous value 1 becomes T[ 2^j ] = 1 + k = 2,

  so there is no more any even value in the dictionary.

(k,v) = (2^j, 1) => T[ 1 ] with previous value 2^j becomes T[ 1 ] = 2^j + 2^j = 2^(j+1).

* At generation g = 2(j+1),

(k,v) = (1, 2^(j+1)) => T[ 2^(j+1) ] is created, with value T[ 2^(j+1) ] = 1.

No odd entry can be created (and T[1] can't change), since there's no odd value in the (old) dictionary.

The only point where the above proof is slightly incomplete is that it remains to be proved that the value 2^j can not arise earlier elsewhere than as T[1] at generation g = 2j.

Some entries T[k]  (e.g., for k = 4, 2, 28, 24, 30, 88, 128, 64, 132, 416, 268, 1920, ...) end up having values larger than T[1]

(and if I'm not mistaken, all these will roughly double at each generation once they passed T[k] > T[1], in contrast to T[1] which doubles only every other generation),

but all of them differ sufficiently from a power of 2 and "decouple" from the smaller values, so that they (conjecturally) won't ever become equal to a power of 2. Showing that rigorously will probably be quite tedious, but I think it could be done for example considering the pattern of their binary representations.

-M.

[M F Hasler]

PS: A few minor corrections and complements:

- in the induction hypothesis, I didn't repeat "there is no odd key other than 1", I hope it was clear that this is part of the hypothesis

- In the proof, "at generation g = 2(j+1)-1 = 2j+1" , I wrote  "there is no more any even value in the dictionary", 

but of course I meant "odd", not "even" !

I think several OEIS sequences could be derived from this idea:

- the sequence of keys in the order they are created:

1, 2, 4, 8, 10, 16, 12, 24, 32, 20, 46, 6, 44, 80, 64, 88, 160, 208, 320, 128, 416, 616, 28, 896, 1222, 34, 256, 1792, 2444, 3712, ...

  (This could be a table with a (possibly empty) row for each generation.

  I think only in generations 1, 3 and 5 the row is empty, i.e., no new keys arise.)

- the sequence of associated (initial) values

1;; 1;; 1;; 1, 4; 1,4; 4; 1, 2, 4, 12; 2, 4; 1,2,4; 2,4; 1,2,4,10; 2,4, 28; 1,2,4; ...

- the number of elements in the dictionary at the n-th generation

1,1, 2,2, 3,3, 5, 7, 8, 12, 14, 17, 19, ...

- the largest value in the dictionary at the n-th generation

1,2, 2, 4, 4, 8, 10, 16, 24, ...

- the set of all numbers ever occurring :

1, 2, 4, 6, 8, 10, 12, 16, 20, 24, 26, 28, 30, 32, 34, 44, 46, 52, 54, 60, 62, 64, 66, 68, 72, 80, 82, 88, 90, 100, 104, ...

(here we still have to give a good criterion to know up to where it is complete)

- the "late birds" : keys such that no smaller key is added later to the dict:

1, 2, 4, 6, 26, 52, 54, 66, 68, 72, 116, 232, 464, ...

-M.

On Mon, Nov 24, 2025 at 10:16 AM M F Hasler <mha...@dsi972.fr> wrote:

On Sun, Nov 23, 2025 at 6:03 PM Loutcho Glotuk <luc.ro...@gmail.com> wrote:

Ruud, thank you for your proposition of a program.

But it does not catch the essence of my question.

Yes, obviously it's trivial to program it, e.g. in Python:

T={1:1}

for generation in range(50):

   for k,v in tuple(T.items()): T[v] = T.get(v,0)+k

sorted(T)[:30]

[1, 2, 4, 6, 8, 10, 12, 16, 20, 24, 26, 28, 30, 32, 34, 44, 46, 52, 54, 60, 62, 64, 66, 68, 72, 80, 82, 88, 90, 100, 104]

but it doesn't provide an answer to the questions.

However, we can indeed prove that 1 is the only odd key that will ever appear.

More specifically, we can prove that ("at" means "at the end of"):

(a) - key k = 1 has value  v = 2^j at generation g = 2j and g = 2j-1 (for j>0).

(b) - the value v = 1 occurs only for keys k = 2^j,

  and only at generation g = 2j we have the (key, value) pair (2^j , 1),

(Proof by induction: The statement is true up to j=1, i.e., at generation 2j-1 = 1 and at generation 2j = 2.

Assume it's true up to some j, and let's consider what happens for j+1.

* At generation g = 2(j+1)-1 = 2j+1, the respective (key,value) pairs lead to following updates:

(k,v) = (1, 2^j) => T[ 2^j ] with previous value 1 becomes T[ 2^j ] = 1 + k = 2,

  so there is no more any *odd* value in the dictionary.

(k,v) = (2^j, 1) => T[ 1 ] with previous value 2^j becomes T[ 1 ] = 2^j + 2^j = 2^(j+1).

[Gareth McCaughan]

I am close to having a complete description of what is in T at any given
point after ~80 iterations. I'm still filling in the details. Here's the
brief summary: there's a smallish set S of smallish numbers such that
every entry in T has either key or value in S; mapping _from_ things in
S gives values that (in some cases exactly, in some cases approximately)
double each iteration; the maps _to_ things in S come from the
historical values of those, so mostly things that are increasing exactly
or approximately 2x each iteration (but there are also relics of earlier
stages of the process before everything settled down). The exact
structure alternates between two closely related things on successive
iterations.

(Once you have the fully-detailed version of this description, it's
routine but tedious to verify that iterating does the right thing. At
least I think it is; again, I haven't filled in all the details yet.
Because, as mentioned above, they are tedious :-).)

So the numbers that eventually become keys or values in T consist of
some "sporadic" things arising early on, along with the union of a
modest number of geometric progressions and a modest number of sums of
two geometric progressions.

(Perhaps M F Hasler, whose recent emails give a similar description of
what's going on, will get there before I do, but I don't get the
impression that he's trying to fill in all the painful details.)

--
g

[M F Hasler]

On Mon, Nov 24, 2025 at 9:54 PM Gareth McCaughan <gareth.m...@pobox.com> wrote:

I am close to having a complete description of what is in T at any given
point after ~80 iterations. I'm still filling in the details. Here's the
brief summary: there's a smallish set S of smallish numbers such that
every entry in T has either key or value in S; mapping _from_ things in
S gives values that (in some cases exactly, in some cases approximately)
double each iteration; the maps _to_ things in S come from the
historical values of those, so mostly things that are increasing exactly
or approximately 2x each iteration (but there are also relics of earlier

stages of the process before everything settled down).(...)

(Perhaps M F Hasler, whose recent emails give a similar description of
what's going on, will get there before I do, but I don't get the
impression that he's trying to fill in all the painful details.)

Yes, I have indeed drafted some of the related sequences:

https://oeis.org/draft/A390939 : list of keys in the order they are inserted , can also be read as irregular table where row n lists keys added at iteration n (again in order they are inserted)

https://oeis.org/draft/A390938 : row lengths = number of keys inserted at iteration n (where n=0 is the initialization step)

https://oeis.org/draft/A390937 : number of entries in T after iteration n (cumulative sums of A390938)

https://oeis.org/draft/A390942 : value of T[2] after iteration n 

https://oeis.org/draft/A390944 : value of T[4] after iteration n

For the last two, I have a conjectured formula for all n ; in particular indeed, T[4] doubles at each step for n > 15,

T[2] eventually doubles at each step n > 18 and gets an additional +2^(n/2-1) for even n.

I'm not sure whether I should add more individual sequences like those 

(cf. the list I posted earlier : 28, 24, 30, 88, 128, 64, 132, 416, 268, 1920, ...:

I think together with {1, 4, 2} that's what Gareth refers to as the set S.)

The other entries become constant from a given iteration on,

with a limit value among those more interesting keys (i.e., S \ {1}).

Concerning A390939, for the order of terms in row n (i.e., keys inserted at iteration n),

it matters in which order the (key, value) pairs are treated.

I use the order in which they appear, which is the order in which they are listed in the sequence.

For example, T[16] and T[10] both appear in the same generation, but I insert T[16] before because it results from T[1] = 16

which comes earlier than T[4] = 10.

Here, these two (T[1] and T[4]) are still in order of increasing key size, so that's no surprise, but in the sequel, the (key, value) pair resulting from T[16] will be treated before that corresponding to T[10].

Obviously, the key 6 that is inserted only at a later iteration, will also be treated significantly later than the earlier entries.

Python guarantees preservation of the order of insertion in a dict, starting from version 3.7.

However, PARI's Map() orders the keys in increasing size, so one has to be careful:

Ruud's implementation would give a different sequence A390939 (where each row would be sorted in increasing order), 

if one doesn't take into account the order in which keys are inserted in the respective generations/iterations.

The earlier mentioned sequences can be straightforwardly computed.

The more interesting and nontrivial sequences, so far still mostly conjectural:

https://oeis.org/draft/A390940 : list of all keys that ever appear, in order of increasing value

https://oeis.org/draft/A390941 : "late birds": terms A390939 smaller than all later terms

- Maximilian

[Gareth McCaughan]

On 25/11/2025 14:34, M F Hasler wrote:

(cf. the list I posted earlier : 28, 24, 30, 88, 128, 64, 132, 416, 268, 1920, ...:

I think together with {1, 4, 2} that's what Gareth refers to as the set S.)

The full set S is: 1, 2, 4, 24, 28, 30, 32, 64, 88, 128, 132, 134, 268, 416, 1920, 3712, 7412.

We should think of it as {1,2} u {32,134,3712} u {64,268,7424} u {4,24,28,30,88,128,132,416,1920}.

The last set gives us keys/values that double every iteration. The others give us things that double every two iterations, and differences (doubling every iteration) - (doubling every two iterations). 1 and 2 behave somewhat like 32,134,3712 and 64,268,7424 but not quite the same.

Still working through all the details and trying to find the least painful notation etc. for describing exactly what happens. But, by way of taster, here's my current description of exactly what is in T after 80 iterations; the "obvious" guess at how this generalizes to other even numbers of iterations (once things have settled down, which by this point they all have) is I believe perfectly correct. The structure after (large enough) odd numbers of iterations is similar but not quite identical.

Let S = {1,2,4,24,28,30,32,64,88,128,132,134,268,416,1920,3712,7424}. Every entry in T has either its key or its value in S. We should think of S as composed of S1 = {1,32,134,3712}, 2.S1 = {2,64,268,7424}, and S2 = {4,24,28,30,88,128,132,416,1920}. The elements 1 of S1 and 2 of 2.S1 behave a bit differently from the others.

We shall be dealing with numbers of two particular forms: something small times a power of 2, or the difference of two such things. Write <a,n> = a * 2^n and <a,n,b,m> = a*2^n - b*2^m.

We shall further be dealing with _sets_ of such numbers. Write <a,n1..n2> = { <a,n1>, <a,n1+1>, ..., <a,n2> } and <N:a,n1..n2,b,m1..m2> = { <a,n1,b,m1>, <a,n1+1,b,m1+1>, <a,n1+2,b,m1+1>, <a,n1+3,b,m1+2, ..., <a,n+n2,b,m+m2> } alternating between incrementing both n,m and only n.

Sometimes two such sets occur together. Write <<a,n1..n2,b,m1..m2>> = <a,n1..n2,b,m1..m2> u <b,m1..m2> and <<a,n1..n2,b,m1..m2+>> = <a,n1..n2,b,m1..m2> u <b,m1..m2+1>.

OK, so now I can tell you exactly what is in T after 80 iterations.

Things in S1:

    <1,40> -> 1 -> <1,40>
    nothing ->   32 -> < 45,31>
    nothing ->  134 -> <111,28>
    nothing -> 3712 -> <961,23>

Things in 2.S1:

    X -> 2 -> Y
    <<  71,2..58, 45,1..29+>> ->   64 -> <  71,59, 45,30> and also  298 ->   64
    << 137,3..51,111,2..26+>> ->  268 -> < 137,52,111,27> and also  860 ->  268
    <<1201,2..42,961,1..21+>> -> 7424 -> <1201,43,961,22> and also 3842 -> 7424

Things in S2 (for each of these some other things also map there, listed below)

    <  2421,1..64> ->    4 -> <  2421,65>
    <    25,2..64> ->   24 -> <    25,65>
    <359901,2..51> ->   28 -> <359901,52>
    <   253,3..60> ->   30 -> <   235,61>
    <   773,6..56> ->   88 -> <   773,57>
    <  2495,2..54> ->  128 -> <  2495,55>
    <    17,5..57> ->  132 -> <    17,58>
    <   737,2..49> ->  416 -> <   737,50>
    <   319,8..47> -> 1920 -> <   319,48>

where X consists of the following:
    <<61316835,6..49,1,17..39>>, <1,8..16>,
    3924148224, 1962008576, 981004288, 490469376, 245234688,
    122600960, 61300480, 30642048, 15321024, 7656416, 3828416,
    1912160, 956080, 477120, 238560, 118768, 59848, 29776, 14888,
    7316, 1792, 20, 16, 8

and Y = <61316835,50,1,39>

and the other things mapping to elements of S2 are:

to    4: 2444,1222, 616, 1280,640,320
to   24: 82, 12,6
to   28: 720762, <11,8..15>, 448,224, 46, 34, 10
to   30: 984, 896
to   88: 24256,12128, 5824,2912, 1336, <15,2..6>, 668, 274, 152, 62
to  128: <79,3..6>, 264, 104,52,26, 54
to  132: 336, 208
to  416: 804,402,201, 68, 66
to 1920: <87,7..9>, <29,2..6>, 72, 44

To summarize:

For v in S1 we have nothing -> v -> <a(v),n(v)> except that for v=1 we also have <a(1),n(1)> -> 1.
For v in S1 we have <<b(v),m0(v)..m1(v),a(v),n0(v)..n(v)-2+>> -> 2v -> <b(v),m1(v)+1,a(v),n(v)-1> EXCEPT that the case v=2 is different. We also have c(v) -> 2v for a particular choice of c(v), but again v=2 is different.
For v in S2 we have <a(v),n0(v)..n(v)> -> v -> <a(v),n(v)+1> and also c -> v for c in some further set C(v).

The values a,n,n1,b,m0,m1,c,C, and exactly what happens for v=2, can be read off from the more detailed description above.

It is also worth noting the sums of all the keys mapping to each v: for v=1 or v in S2 this equals T[v],for other v in S1 it's 0, and for v in 2.S1 it's <b(v/2),m1(v/2)+1>, i.e. the "leading term" of T[v].

--
g

[Loutcho Glotuk]

Thank you very much to Gareth McCaughan and to M F Hasler for their findings and editorial work!

Sans virus.www.avg.com

--

You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/f06e1d4e-5c27-4931-8bec-0d94705d77cf%40pobox.com.

[Gareth McCaughan]

On 23/11/2025 14:27, Loutcho Glotuk wrote:

> Hi to all,
>
> Let us play with an associative array T. At generation j = 0, T is
> initialized with one entry,
> T[1] = 1.
>
> The evolution rule to get the T of the next generation is:
>     for each key-value pair (k, v) in T, cumulate (v, k) in T.
>
> In order to avoid the ambiguities inherent to in-place modifications
> and to the meaning of "cumulate", let's reformulate. Let T(j) denote
> the T of generation j. The evolution rule is:
> T(j+1) is T(j) cloned and modified by:
> for each key-value pair (k,v) in T(j),
>     if v is a key in T(j+1),
>     then T(j+1)[v] := T(j+1)[v] + k      (an update),
>     else T(j+1)[v] := k        (an insertion).
>
> We can make an integer sequence from that problem, that I would dream
> to add to the OEIS:
> >> what is the set of the numbers that eventually become keys in T?
> Comes to the same:
> >> what is the set of the numbers that eventually become values in T?

OK, here's what I hope is the "complete" version of the thing I sketched
in an earlier email. It could definitely use some presentational
polishing, but I hope it is comprehensible as it stands.

Unfortunately I make a lot of mistakes and it would be an excellent idea
for someone who is not me to check this. Also-unfortunately, it's pretty
tedious.

What I should obviously do is to turn my description into actual code
that I can use to verify that the contents of T are as described after
(say) 80, 81, and 82 iterations; unless I am confused that + the
observation that the various families of numbers involved are disjoint
should be sufficient to ensure that my description is correct. Perhaps I
will do that, but not today.

Here goes.

I think that after < 100 iterations, the process settles down into a
(modestly complicated, but the complexity is all pretty superficial)
steady state that I can describe completely.

Let me begin by giving a complete description of what's in T after 80
iterations. I am assuming that my crappy Python code isn't made of bugs;
someone else might want to check. It is also very possible that I've
screwed something up when transcribing and summarizing.

Let S = {1,2,4,24,28,30,32,64,88,128,132,134,268,416,1920,3712,7424}.
Every entry in T has either its key or its value in S. We should think
of S as composed of S1 = {1,32,134,3712}, 2.S1 = {2,64,268,7424}, and S2
= {4,24,28,30,88,128,132,416,1920}. The elements 1 of S1 and 2 of 2.S1
behave a bit differently from the others.

We shall be dealing with numbers of two particular forms: something
small times a power of 2, or the difference of two such things. Write
<a,n> = a * 2^n and <a,n,b,m> = a*2^n - b*2^m.

We shall further be dealing with _sets_ of such numbers. Write
<a,n1..n2> = { <a,n1>, <a,n1+1>, ..., <a,n2> } and <N:a,n1..n2,b,m1..m2>
= { <a,n1,b,m1>, <a,n1+1,b,m1+1>, <a,n1+2,b,m1+1>, <a,n1+3,b,m1+2, ...,
<a,n+n2,b,m+m2> } alternating between incrementing both n,m and only n.

Sometimes two such sets occur together. Write <<a,n1..n2,b,m1..m2>> =
<a,n1..n2,b,m1..m2> u <b,m1..m2> and <<a,n1..n2,b,m1..m2+>> =
<a,n1..n2,b,m1..m2> u <b,m1..m2+1>.

(I was careless in my naming of things, and below I frequently have
<b,m,a,n> rather than <a,n,b,m>. My apologies for the extra cognitive load.)

<b(v),m1(v)+1,a(v),n(v)-1>. We also have c(v) -> 2v for a particular
choice of c(v). BUT for v=1 things are a little different: the "regular"
set of things mapping to 2 is <<b(1),m0(1)..m1(1),a(1),n0(1)..n(1)-1>>,
and instead of just a single extra c(1) mapping to 2 there is a larger
set C(1).

For v in S2 we have <a(v),n0(v)..n(v)> -> v -> <a(v),n(v)+1> and also c
-> v for c in some further set C(v).

The values a,n,n1,b,m0,m1,c,C, and exactly what happens for v=2, can be

read off from the more detailed description above. All the c and C
values are much smaller than the things that elements of S map to, and
none of them equals anything in S. All the "regular" values that "look"
different really are different.

It is also worth noting the sums of all the keys mapping to each v: for
v=1 or v in S2 this equals T[v],for other v in S1 it's 0, and for v in
2.S1 it's <b(v/2),m1(v/2)+1>, i.e. the "leading term" of T[v].

Let's now look at exactly what happens when we apply our iterative step.
It will turn out that doing it _twice_ restores pretty much the state of
affairs above, with some numbers incremented.

For v in S2, we have lots of {k:v} and the sum of the k equals T[v], so
processing these entries doubles the value of T[v]. The same is true for
v=1 which now maps to <a(1),n(1)+1>.
For other v in S1, there are no {k:v} and so no entries to process.
For v in S1, there are lots of {k:2v} and the sum of the k equals
<b(v),m1(v)+1>. For these the previous value of T[2v] was
<b(v),m1(v)+1,a(v),n(v)-1> so after the update this becomes
<b(v),m1(v)+2,a(v),n(v)-1>.
That's the mappings _to_ S; now let's look at the mappings _from_ S.
Note that the detailed list of the contents of T, above, shows that
nothing in S maps to anything from S, so we don't need to worry that
we're accounting for some entry more than once.
For k in S2, we have k -> <a(k),n(k)+1> which wasn't previously a key,
so now we have <a(k),n(k)+1> -> k which is the expected "next" thing
mapping to k.
For k=1, we have 1 -> <a(1),n(1)> which already mapped to 1, so now it
maps to 2, increasing the "regular" set of things-mapping-to-2 to
<<b(1),m0(1)..m1(1),a(1),n0(1)..n(1)-1+>>.
For other k in S1, we have k -> <a(k),n(k)> which wasn't previously a
key, so now we have <a(k),n(k)> -> k; previously nothing mapped to k.
For k in S1, we have 2k -> <b(k),m1(k)+1,a(k),n(k)-1> which wasn't
previously a key, so now we have <b(k),m1(k)+1,a(k),n(k)-1> -> 2k,
increasing the "regular" set of things mapping to 2k to
<<b(v),m0(v)..m1(v)+1,a(v),n0(v)..n(v)-2+>>, except that in the case k=1
it's now <<b(1),m0(1)..m1(1)+1,a(1),n0(1)..n(1)-1>>.

So let's now summarize what's in T at this point.

For v in S1 we have <a(v),n(v)> -> v -> <a(v),n(v)>.
For v in S1 we have <<b(v),m0(v)..m1(v)+1,a(v),n0(v)..n(v)-2+>> -> 2v ->
<b(v),m1(v)+2,a(v),n(v)-1>. We also have c(v) -> 2v for the same
particular choice of c(v) as before. BUT for v=1 things are a little
different: the "regular" set of things mapping to 2 is
<<b(1),m0(1)..m1(1)+1,a(1),n0(1)..n(1)-1>>, and instead of just a single
extra c(1) mapping to 2 there is still the same larger set C(1).
For v in S2 we have <a(v),n0(v)..n(v)+1> -> v -> <a(v),n(v)+2> and also
c -> v for c in the set C(v).

Once again it's useful to note the sums of all keys mapping to each v in
S: for all v in S1 it equals T[v], for v=2k in 2.S1 it's <b(k),m1(k)+1>
+ <b(k),m1(k)+1,a(k),n(k)-1> = <b(k),m1(k)+2,a(k),n(k)-1>, and for v in
S2 it's once again equal to T[v].

And now let's apply the iterative step again.

First, mappings _to_ S.
For v in either S1 or S2, the sum of k with k->v equals T[v], so
processing these entries doubles the value of T[v], to <a(v),n(v)+1> in
the S1 case and <a(v),n(v)+3> in the S2 case.
For v=2k in 2.S1, the sum is <b(k),m1(k)+2,a(k),n(k)-1> so v now maps to
<b(k),m1(k)+3,a(k),n(k)>.
Now, mappings _from_ S; once again we can see that nothing in S maps to
anything in S, so we are in no danger of double-counting.
For k in S1, we have k -> <a(v),n(v)>. The latter already mapped to k,
so now it maps to 2k.
For k in S1, we have 2k -> <b(k),m1(k)+2,a(k),n(k)-1>. The latter didn't
map anywhere, so now it maps to 2k. Note that we have thus added _two_
new things mapping to 2k.
For k in S2, we have k -> <a(v),n(v)+2>. The latter didn't map anywhere
and so now maps to k.

And, once again summarizing what we have at this point. All the "extra"
mappings once again remain unchanged and I shall not bother mentioning them.

We have <a(1),n(1)+1> -> 1 -> <a(1),n(1)+1>.
For other v in S1, we have nothing -> v -> <a(v),n(v)+1>.
We have <<b(1),m0(1)..m1(1)+2,a(1),n0(1)..n(1)>> -> 2 ->
<b(v),m1(v)+3,a(v),n(v)>.
For other v in S1, we have <<b(v),m0(v)..m1(v)+2,a(v),n0(v)..n(v)-1+>>
-> 2v -> <b(v),m1(v)+3,a(v),n(v)>.
For v in S2, we have <a(v),n0(v)..n(v)+2> -> v -> <a(v),n(v)+3>.

And now we can compare this with what was in T two iterations before,
and verify that it does in fact have the exact same form, with no
changes to the a,b,c,C, with (for S1) the values of n increased by 1 and
the values of m increased by 2 and (for S2) the values of n increased by
2. (I should probably have called the S2 things b,m rather than a,n. Sorry.)

Nothing above depended on the exact values of m,n, so the state of
affairs described above continues for ever.

We can now describe the full set of keys/values that ever occur in T.
They consist of:

1. The elements of S, which by way of reminder are
{1,2,4,24,28,30,32,64,88,128,132,134,268,416,1920,3712,7424}.

2. The "regular" sets of things mapping to elements of S:
    <<61316835,6..,1,17..>>
    <<  71,2.., 45,1..+>>
    << 137,3..,111,2..+>>
    <<1201,2..,961,1..+>>
    <  2421,1..>
    <    25,2..>
    <359901,2..>
    <   253,3..>
    <   773,6..>
    <  2495,2..>
    <    17,5..>
    <   737,2..>
    <   319,8..>

    where e.g. <<71,2..,45,1..+>> means the union of all the
<<71,2..2+2k,45,1+k+>>
    which is in fact the same as the union of all the
<<71,2..2+2k,45,1+k>>.

3. The other one-off entries, presented here in a weird order because it's
   the same as the order in which they are introduced above:

    <1,8..16>

    3924148224, 1962008576, 981004288, 490469376, 245234688,
    122600960, 61300480, 30642048, 15321024, 7656416, 3828416,
    1912160, 956080, 477120, 238560, 118768, 59848, 29776, 14888,
    7316, 1792, 20, 16, 8

    298, 860, 3842

    2444,1222, 616, 1280,640,320
    82, 12,6

    720762, <11,8..15>, 448,224, 46, 34, 10

    984, 896

    24256,12128, 5824,2912, 1336, <15,2..6>, 668, 274, 152, 62

    <79,3..6>, 264, 104,52,26, 54

    336, 208
    804,402,201, 68, 66

    <87,7..9>, <29,2..6>, 72, 44

--
g