A390938 Number of new keys inserted at iteration n in a map initialized with T[1] := 1, then iterate: for each (key, value) already in T, T[value] := T[value]+key if T[value] already exists, else T[value] := key.

1, 0, 1, 0, 1, 0, 1, 1, 2, 1, 4, 2, 3, 2, 4, 3, 3, 6, 5, 6, 4, 9, 8, 9, 10, 10, 9, 12, 10, 12, 12, 13, 13, 14, 13, 14, 12, 15, 13, 15, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14, 16, 14

Offset

0,9

Comments

Row lengths of A390939, read as irregular table, which is the main entry for this and related sequences: see there for more information.

Iteration n = 0 corresponds to initialization of the map with one single entry T[1] = 1, hence a(0) = 1.

Eventually, only the 17 entries T[k] with k in A390943 continue growing, roughly or exactly doubling at every or every other iteration. Therefore only these can lead to new entries, and do so, with the exception of T[1] on odd iterations n = 2m+1 and T[32, 134 and 3712] on even iterations n = 2m, where they initially have the same value as in the previous iteration. (All of these four double their value only every other iteration). Thus, a(2m+1) = 16 and a(2m) = 17-3 = 14 for m >= 20.

Links

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

Formula

a(n) = A390937(n) - A390937(n-1) for n > 0.

a(2m) = 14, a(2m+1) = 16, for m >= 20.

Example

a(0) = 1 because T[1] := 1 is the only entry inserted at iteration 0; i.e., when the map is initialized.
a(1) = a(3) = a(5) = 0 because at these iterations, no new entry is inserted. For example, at the first iteration, the only existing entry (key, value) = (1, 1) leads to T[1] := T[1] + 1 = 2, similarly.
a(2) = 1 because at iteration 2, the only existing entry (key, value) = (1, 2) leads to insertion of the new entry T[2] := 1.
Similarly, at iteration 4 and 6, a new entry T[4] := 1 and T[8] := 1, respectively, is inserted.
See the main entry A390939 for more examples and explanations.

Prog

(Python)
def A390938(n):
    if n>39: return 16 if n&1 else 14
    if not hasattr(A := A390938, 'T'): A.T={1:1}; A.terms=[1]
    while len(A.terms) <= n:
        A.terms += [0]
        for k, v in tuple(A.T.items()):
            try: A.T[v] += k
            except KeyError: A.T[v] = k; A.terms[-1] += 1
    return A.terms[n]

Crossrefs

Cf. A390939 (keys in order they are inserted in the map), A390940 (all keys ever inserted in the map, in increasing order), A390941 (late birds: keys so that all subsequently inserted keys are larger), A390943 (keys for which T[k] grows forever).

Cf. A390937: cumulative (partial) sums of this sequence.

Sequence in context: A323901 A132223 A224712 * A363301 A135941 A036998

Adjacent sequences: A390935 A390936 A390937 * A390939 A390940 A390941

Keyword

nonn,easy

Author

M. F. Hasler, Nov 24 2025

Status

approved