%I M0137 #42 Sep 11 2024 00:36:40
%S 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,
%T 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,
%U 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
%N 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).
%D Clark Kimberling, "Fractal Sequences and Interspersions", Ars Combinatoria, vol. 45 p 157 1997.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A007336/b007336.txt">Table of n, a(n) for n=1..1000</a>
%H Dale Gerdemann, <a href="https://www.youtube.com/watch?v=W7D2-jIY1Gw">Plot of Adjacent Terms</a>, YouTube Video, 2015.
%H Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/intersp.html">Interspersions</a>
%H <a href="/index/Si#signature_sequences">Index entries for sequences related to signature sequences</a>
%F If delete first occurrence of 1, 2, 3, ... the sequence is unchanged.
%t 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 *)
%t Quiet[Block[{$ContextPath}, Needs["Combinatorica`"]], {General::compat}]
%t memos = <||>;
%t zeroBasedC[theta_, i_] := zeroBasedC[theta, i] = Module[{memo, depth},
%t memo = Lookup[memos, theta, {-1, 0}];
%t While[memo[[-1]] <= i, AppendTo[memo, memo[[-1]] + Ceiling[theta * (Length[memo] - 1)]]];
%t memos[i] = memo;
%t depth = Combinatorica`BinarySearch[memo, i] - 3/2;
%t If[IntegerQ[depth] && depth <= i, 1 + zeroBasedC[theta, i - depth], 0]
%t ];
%t A007336[i_] := zeroBasedC[2^(1/2), i - 1] + 1;
%t Table[A007336[i], {i, 1, 100}] (* _Brady J. Garvin_, Aug 19 2024 *)
%o (Python)
%o from bisect import bisect
%o from collections import defaultdict
%o from functools import cache
%o from math import ceil
%o memos = defaultdict(lambda: [-1, 0])
%o @cache
%o def zero_based_c(theta, i):
%o memo = memos[theta]
%o while memo[-1] <= i:
%o memo.append(memo[-1] + ceil(theta * (len(memo) - 1)))
%o depth = bisect(memo, i) - 1
%o return 0 if depth > i or memo[depth] == i else 1 + zero_based_c(theta, i - depth)
%o def A007336(i):
%o return zero_based_c(2 ** 0.5, i - 1) + 1
%o print([A007336(i) for i in range(1, 1001)]) # _Brady J. Garvin_, Aug 18 2024
%Y Cf. A007337, A022775.
%K nonn,easy,nice,eigen
%O 1,2
%A _N. J. A. Sloane_, _Clark Kimberling_
%E More terms from _Robert G. Wilson v_, Jul 24 2004