A023124 Signature sequence of 1/e (arrange the numbers i+j*x (i,j >= 1) in increasing order; the sequence of i's is the signature of x).

1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 5, 1, 4, 3, 2, 5, 1, 4, 3, 2, 5, 1, 4, 3, 6, 2, 5, 1, 4, 3, 6, 2, 5, 1, 4, 3, 6, 2, 5, 1, 4, 7, 3, 6, 2, 5, 1, 4, 7, 3, 6, 2, 5, 1, 4, 7, 3, 6, 2, 5, 1, 8, 4, 7, 3, 6, 2, 5, 1, 8, 4, 7, 3, 6, 2, 5, 1, 8, 4, 7, 3

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• easy
• nice
• eigen

Comments

Arrange the numbers i+j*e (i,j >= 1) in increasing order; this sequence is the sequence of j's. - Michel Marcus, Dec 18 2021

If one deletes the first occurrence of 1, the first occurrence of 2, the first occurrence of 3, etc., then the sequence is unchanged. - Brady J. Garvin, Sep 11 2024

Any signature sequence A is closely related to the partial sums of the corresponding homogeneous Beatty sequence: Let Q(d) = d + the sum from g=0 to g=d-1 of floor(theta * g) and Qinv(i) = the maximum integer d such that Q(d) <= i. If there is some d for which Q(d) = i, then A_i = 1. Otherwise, A_i = A_{i - Qinv(i)} + 1. - Brady J. Garvin, Sep 13 2024

References

• J.-P. Delahaye, Des suites fractales d’entiers, Pour la Science, No. 531 January 2022. Sequence h) p. 82.
• Clark Kimberling, "Fractal Sequences and Interspersions", Ars Combinatoria, vol. 45 p 157 1997.

Links

• T. D. Noe, Table of n, a(n) for n=1..1000
• Clark Kimberling, Interspersions
• Index entries for sequences related to signature sequences

Crossrefs

Cf. A001113, A023123, A032634.

Programs

Mathematica

Quiet[Block[{$ContextPath}, Needs["Combinatorica`"]], {General::compat}]
theta = 1 / E;
sums = {0};
cached = <||>;
A023124[i_] := Module[{term, path, base},
  While[sums[[-1]] < i,
    term = sums[[-1]] + Floor[theta * (Length[sums] - 1)] + 1;
    AppendTo[sums, term];
    cached[term] = 1
  ];
  path = {i};
  While[Not[KeyExistsQ[cached, path[[-1]]]],
    AppendTo[path, path[[-1]] - Combinatorica`BinarySearch[sums, path[[-1]]] + 3/2];
  ];
  base = cached[path[[-1]]];
  MapIndexed[(cached[#1] = base + Length[path] - First[#2]) &, path];
  cached[i]
];
Print[Table[A023124[i], {i, 1, 100}]]; (* Brady J. Garvin, Sep 13 2024 *)

Python

from bisect import bisect
from sympy import floor, E
theta = 1 / E
sums = [0]
cached = {}
def A023124(i):
    while sums[-1] < i:
        term = sums[-1] + floor(theta * (len(sums) - 1)) + 1
        sums.append(term)
        cached[term] = 1
    path = [i]
    while path[-1] not in cached:
        path.append(path[-1] - bisect(sums, path[-1]) + 1)
    base = cached[path[-1]]
    for offset, vertex in enumerate(reversed(path)):
        cached[vertex] = base + offset
    return cached[i]
print([A023124(i) for i in range(1, 1001)])  # Brady J. Garvin, Sep 13 2024