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

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

Offset: 1

Author

N. J. A. Sloane, Clark Kimberling

Keywords

• nonn
• easy
• nice
• eigen

References

• Clark Kimberling, "Fractal Sequences and Interspersions", Ars Combinatoria, vol. 45 p 157 1997.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=1..1000
• Dale Gerdemann, Plot of Adjacent Terms, YouTube Video, 2015.
• Clark Kimberling, Interspersions
• Index entries for sequences related to signature sequences

Crossrefs

Cf. A007337, A022775.

Programs

Mathematica

Take[ Transpose[ Sort[ Flatten[ Table[{i + j*Sqrt[2], i}, {i, 17}, {j, 15}], 1], #1[[1]] < #2[[1]] &]][[2]], 96] (* Robert G. Wilson v, Jul 24 2004 *)
Quiet[Block[{$ContextPath}, Needs["Combinatorica`"]], {General::compat}]
memos = <||>;
zeroBasedC[theta_, i_] := zeroBasedC[theta, i] = Module[{memo, depth},
  memo = Lookup[memos, theta, {-1, 0}];
  While[memo[[-1]] <= i, AppendTo[memo, memo[[-1]] + Ceiling[theta * (Length[memo] - 1)]]];
  memos[i] = memo;
  depth = Combinatorica`BinarySearch[memo, i] - 3/2;
  If[IntegerQ[depth] && depth <= i, 1 + zeroBasedC[theta, i - depth], 0]
];
A007336[i_] := zeroBasedC[2^(1/2), i - 1] + 1;
Table[A007336[i], {i, 1, 100}] (* Brady J. Garvin, Aug 19 2024 *)

Python

from bisect import bisect
from collections import defaultdict
from functools import cache
from math import ceil
memos = defaultdict(lambda: [-1, 0])
@cache
def zero_based_c(theta, i):
    memo = memos[theta]
    while memo[-1] <= i:
        memo.append(memo[-1] + ceil(theta * (len(memo) - 1)))
    depth = bisect(memo, i) - 1
    return 0 if depth > i or memo[depth] == i else 1 + zero_based_c(theta, i - depth)
def A007336(i):
    return zero_based_c(2 ** 0.5, i - 1) + 1
print([A007336(i) for i in range(1, 1001)])  # Brady J. Garvin, Aug 18 2024

Formula

If delete first occurrence of 1, 2, 3, ... the sequence is unchanged.

Extensions

More terms from Robert G. Wilson v, Jul 24 2004