cp's OEIS Frontend

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

%I A023123 #23 Oct 16 2024 21:49:02
%S A023123 1,2,3,1,4,2,5,3,6,1,4,7,2,5,8,3,6,9,1,4,7,10,2,5,8,11,3,6,9,1,12,4,7,
%T A023123 10,2,13,5,8,11,3,14,6,9,1,12,4,15,7,10,2,13,5,16,8,11,3,14,6,17,9,1,
%U A023123 12,4,15,7,18,10,2,13,5,16,8,19,11,3,14,6,17,9,20,1,12,4,15,7,18,10,21,2
%N A023123 Signature sequence of e (arrange the numbers i+j*x (i,j >= 1) in increasing order; the sequence of i's is the signature of x).
%C A023123 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
%C A023123 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
%D A023123 Clark Kimberling, "Fractal Sequences and Interspersions", Ars Combinatoria, vol. 45 p 157 1997.
%H A023123 T. D. Noe, <a href="/A023123/b023123.txt">Table of n, a(n) for n=1..1000</a>
%H A023123 Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/intersp.html">Interspersions</a>
%H A023123 <a href="/index/Si#signature_sequences">Index entries for sequences related to signature sequences</a>
%t A023123 Quiet[Block[{$ContextPath}, Needs["Combinatorica`"]], {General::compat}]
%t A023123 theta = E;
%t A023123 sums = {0};
%t A023123 cached = <||>;
%t A023123 A023123[i_] := Module[{term, path, base},
%t A023123   While[sums[[-1]] < i,
%t A023123     term = sums[[-1]] + Floor[theta * (Length[sums] - 1)] + 1;
%t A023123     AppendTo[sums, term];
%t A023123     cached[term] = 1
%t A023123   ];
%t A023123   path = {i};
%t A023123   While[Not[KeyExistsQ[cached, path[[-1]]]],
%t A023123     AppendTo[path, path[[-1]] - Combinatorica`BinarySearch[sums, path[[-1]]] + 3/2];
%t A023123   ];
%t A023123   base = cached[path[[-1]]];
%t A023123   MapIndexed[(cached[#1] = base + Length[path] - First[#2]) &, path];
%t A023123   cached[i]
%t A023123 ];
%t A023123 Print[Table[A023123[i], {i, 1, 100}]]; (* _Brady J. Garvin_, Sep 13 2024 *)
%o A023123 (Python)
%o A023123 from bisect import bisect
%o A023123 from sympy import floor, E
%o A023123 theta = E
%o A023123 sums = [0]
%o A023123 cached = {}
%o A023123 def A023123(i):
%o A023123     while sums[-1] < i:
%o A023123         term = sums[-1] + floor(theta * (len(sums) - 1)) + 1
%o A023123         sums.append(term)
%o A023123         cached[term] = 1
%o A023123     path = [i]
%o A023123     while path[-1] not in cached:
%o A023123         path.append(path[-1] - bisect(sums, path[-1]) + 1)
%o A023123     base = cached[path[-1]]
%o A023123     for offset, vertex in enumerate(reversed(path)):
%o A023123         cached[vertex] = base + offset
%o A023123     return cached[i]
%o A023123 print([A023123(i) for i in range(1, 1001)])  # _Brady J. Garvin_, Sep 13 2024
%Y A023123 Cf. A023124, A022843
%K A023123 nonn,easy,nice,eigen
%O A023123 1,2
%A A023123 _Clark Kimberling_
%E A023123 The a(47) term was missing. Corrected by _T. D. Noe_, Aug 12 2008