A391868 Start with the list of positive integers 1,2,3,... . After each integer k, insert k empty positions. Fill these positions, from left to right, with the positive integers in order. Repeat this spacing-and-filling process indefinitely. The sequence consists of the positions of the last occurrence of 1 after each step.

1, 2, 3, 5, 10, 30, 260, 27055, 359053260, 64449908835943580, 2076895351339769524927520206130260, 2156747150208372213435450937462084443815303022682314584506286121480

Offset

1,2

Comments

See the Example for a more complete description of the spacing-and-filling process.

In computing the sequence, it is enough to keep track of the list of numbers up to and including the last 1. The process starts as follows (cf. first Python program):

[1],

[1,1],

[1,1,1],

[1,1,1,2,1],

[1,1,1,2,1,3,2,4,5,1],

[1,1,1,2,1,3,2,4,5,1,6,3,7,8,9,2,10,11,4,12,13,14,15,5,16,17,18,19,20,1],

...

a(n) is the length of the n-th list.

Note that for n >= 2, a(n+1) = a(n) + S(n) - 1, where S(n) is the sum of the n-th list.

Note that for n >= 2, S(n+1) = S(n) + T(a(n+1)-a(n)) = S(n) + T(S(n)-1), where T(k) is the k-th triangular number, A000217(k).

The sequence for S(n) is 1,2,3,6,21,231,26796,35902620,... or 1 followed by A007501.

a(16) has 1057 digits.

Links

Michael S. Branicky, Table of n, a(n) for n = 1..15

Formula

a(n) = a(n-1) + S(n-1) - 1 for n >= 3, where S(n) = S(n-1) + A000217(S(n-1)-1) and a(1) = S(1) = 1, a(2) = S(2) = 2.

a(n) = a(n-1) + A007501(n-3) - 1 for n >= 3, with a(1) = 1, a(2) = 2.

a(n) = a(n-1) + A006893(n-2) for n >= 3, with a(1) = 1, a(2) = 2.

Example

We start with 1,2,3,4,5,6,... . Note the only 1 is at position 1, so a(1) = 1.
Then, after each term k we first put k spaces and then subsequently fill these spaces with the positive integers in order:
  1,_,2,_,_,3,_,_,_,4,_,_,_, _,5, _, _, _, _, _,6,...
  1,1,2,2,3,3,4,5,6,4,7,8,9,10,5,11,12,13,14,15,6,...
We see the last 1 at position 2, so a(2) = 2. In the next step, we repeat the spacing-and-filling process:
  1,_,1,_,2,_,_,2,_,_,3,_,_,_,3, _, _, _,4, _, _, _, _,5, _,...
  1,1,1,2,2,3,4,2,5,6,3,7,8,9,3,10,11,12,4,13,14,15,16,5,17,...
We see the last 1 at position 3, so a(3) = 3.
  1,_,1,_,1,_,2,_,_,2,_,_,3,_,_, _,4, _, _, _, _,2, _, _,5,...
  1,1,1,2,1,3,2,4,5,2,6,7,3,8,9,10,4,11,12,13,14,2,15,16,5,...
We see the last 1 at position 5, so a(4) = 5.
We continue this process to obtain further terms.

Prog

(Python) # constructive version
from itertools import islice
def space_and_fill(L):
    out, i = [], 1
    for t in L:
        out.extend([t]+list(range(i, i+t)))
        i += t
    return out
def agen():
    L, s = [1], 1
    yield 1
    while True:
        last1 = len(L) - L[::-1].index(1)
        L = L[:last1]
        yield last1 - 1 + sum(L) # next last1
        L = space_and_fill(L)
print(list(islice(agen(), 9)))
(Python) # version based on first formula
def T(n): return n*(n+1)//2
def S(n):
    if n < 3: return n
    return (Sp:=S(n-1)) + T(Sp-1)
def a(n):
    if n < 3: return n
    return a(n-1) + S(n-1) - 1
print([a(n) for n in range(1, 13)])

Crossrefs

Cf. A000217, A006893, A007501.

Sequence in context: A330333 A003182 A348260 * A363257 A344347 A389623

Adjacent sequences: A391865 A391866 A391867 * A391869 A391870 A391871

Keyword

nonn

Author

Ali Sada and Michael S. Branicky, Jan 18 2026

Status

approved