A390939 Keys added to a map T initialized with T[1] = 1 and updated at each iteration according to T[value] := (T[value] if defined else 0) + key, for all (key, value) pairs already in T; listed in order the keys are added to the map (cf. comments for details).

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, 4842, 82, 30, 26, 134, 512, 7316, 9684, 100, 224, 14888, 19368, 200, 60, 52, 448, 1024, 29776, 38736, 400, 59848, 77472, 800, 90, 120, 104, 62, 54, 1920

Offset

0,2

Comments

At each iteration, the (key, value) pairs are treated in the same order as they are listed in this sequence, i.e., as the keys were inserted into the map.

The sequence can also be considered as an irregular table, read by rows, where row r lists the (new) keys added (i.e., inserted in the map) at iteration r, cf. example. Row lengths are given in A390938.

The set of new keys that appear during iteration r does not depend on the order in which the (key, value) pairs are treated, but that order matters for the precise order in which they appear and therefore are listed in this sequence.

It turns out that the 17 entries with keys listed in A390943 continue to grow to infinity (eventually doubling at every or every other step) and provide new terms of this sequence, while all other entries of the map remain constant after reaching one of the values listed in A390943. See Gareth McCaughan's SeqFan post for details.

Links

Table of n, a(n) for n=0..58.

Gareth McCaughan, Reply to "A key/value nightmare sequence", post to the SeqFan list, Nov. 24, 2025.

Luc Rousseau, A key/value nightmare sequence, post to the SeqFan list, Nov. 23, 2025.

Example

The keys and corresponding initial values added at iteration r >= 0 are the following:
   r | new keys          | corresponding values
-----+-------------------+--------------------------------
   0 | 1                 | 1
   1 | (no new entry)    | (key k=1 => T[1] := T[1]+1 = 2)
   2 | 2                 | 1
   3 | (no new entry)    | (k=1 => T[2] := T[2]+1 = 2, k=2 => T[1] := T[1]+2 = 4)
   4 | 4                 | 1 (and k=2 => T[2] := 2+2 = 4)
   5 | (no new entry)    | (k=1, k=2 => T[4] := 1+1+2 = 4; k=4 => T[1] := 4+4 = 8)
   6 | 8                 | 1 (and k=2, k=4 => T[4] := 4+2+4 = 10)
   7 | 10                | 4 (and T[8] := 1+1 = 2, T[4] := 10+2 = 12, T[1] := 8+8)
   8 | 16, 12            | 1, 4
   9 | 24                | 4
  10 | 32, 20, 46, 6     | 1, 2, 4, 12
  11 | 44, 80            | 2, 4
  12 | 64, 88, 160       | 1, 2, 4
  13 | 208, 320          | 2, 4
  14 | 128, 416, 616, 28 | 1, 2, 4, 10
  15 | 896, 1222, 34     | 2, 4, 28
  16 | 256, 1792, 2444   | 1, 2, 4
...  | ...               | ...
At iteration 8, the entry T[16] = 1 is inserted before the entry T[12] = 4, because (key, value) = (1, 16) is treated before (4, 12). Later, key 16 is treated before key 12; key 32 is inserted and consequently treated before key 20 which comes before key 6, and so on.
Eventually, only the 17 values T[k] with k in A390943 may lead to new entries, and for iterations r >= 40 it will be the 16 values with k > 1 when r is odd, or the 14 values with k not in {32, 134, 3712} when r is even.

Prog

(Python) # version >= 3.7 guarantees that dict preserves order of insertion
def A390939(n):
    if not hasattr(A := A390939, 'T'): A.T = {1:1}; A.terms = [1]
    if n >= len(A.terms):
       while n >= len(A.T):
          for k, v in tuple(A.T.items()): A.T[v] = A.T.get(v, 0)+k
       A.terms = tuple(A.T)
    return A.terms[n]

Crossrefs

Cf. A390938 (number of elements inserted at iteration n), A390940 (all keys that ever occur, in increasing order), A390941 (late birds: terms smaller than all subsequent terms), A390943 (list of keys for which T[k] grows to infinity; also the possible limiting values for all other entries), A390942 and A390944 (value of T[2] resp. T[4] at the n-th iteration).

Sequence in context: A102431 A076919 A336659 * A341655 A171757 A350780

Adjacent sequences: A390936 A390937 A390938 * A390940 A390941 A390942

Keyword

nonn

Author

M. F. Hasler, Nov 24 2025

Status

approved