%I M0138 #91 Jun 03 2024 14:27:36
%S 1,1,1,2,1,3,2,1,4,3,2,5,1,6,4,3,7,2,8,5,1,9,6,4,10,3,11,7,2,12,8,5,
%T 13,1,14,9,6,15,4,16,10,3,17,11,7,18,2,19,12,8,20,5,21,13,1,22,14,9,
%U 23,6,24,15,4,25,16,10,26,3,27,17,11,28,7,29,18,2,30,19,12,31,8,32,20,5,33
%N Fractal sequence obtained from Fibonacci numbers (or Wythoff array).
%C Length of n-th row = A000045(n); last term of n-th row = A094967(n-1); sum of n-th row = A033192(n-1). - _Reinhard Zumkeller_, Jan 26 2012
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Reinhard Zumkeller, <a href="/A003603/b003603.txt">Rows n = 1..20 of triangle, flattened</a>
%H J. H. Conway and N. J. A. Sloane, <a href="/A019586/a019586.pdf">Notes on the Para-Fibonacci and related sequences</a>.
%H David Garth and Joseph Palmer, <a href="https://www.fq.math.ca/Papers1/54-1/GarthPalmer10292015.pdf">Self-Similar Sequences and Generalized Wythoff Arrays</a>, Fibonacci Quart. 54 (2016), no. 1, 72-78.
%H Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/fractals.html">Fractal sequences</a>.
%H Clark Kimberling, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa73/aa7321.pdf">Numeration systems and fractal sequences</a>, Acta Arithmetica 73 (1995) 103-117.
%H A. J. Macfarlane, <a href="https://arxiv.org/abs/2405.18128">On the fibbinary numbers and the Wythoff array</a>, arXiv:2405.18128 [math.CO], 2024. See page 8.
%H N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>.
%F Vertical para-budding sequence: says which row of Wythoff array (starting row count at 1) contains n.
%F If one deletes the first occurrence of 1, 2, 3, ... the sequence is unchanged.
%F From _Clark Kimberling_, Oct 29 2009: (Start)
%F The fractal sequence of the Wythoff array can be constructed without reference to the Wythoff array or Fibonacci numbers. Write initial rows:
%F Row 1: .... 1
%F Row 2: .... 1
%F Row 3: .... 1..2
%F Row 4: .... 1..3..2
%F For n>4, to form row n+1, let k be the least positive integer not yet used; write row n, and right after the first number that is also in row n-1, place k; right after the next number that is also in row n-1, place k+1, and continue. A003603 is the concatenation of the rows. (End)
%F Conjecture: a(n) = abs(floor(n/phi) - floor(n*(1/phi + 1/(-phi)^(A035612(n) + 1)))) where phi = (1+sqrt(5))/2. - _Alan Michael Gómez Calderón_, Oct 27 2023
%e In the recurrence for making new rows, we get row 5 from row 4 thus: write row 4: 1,3,2, and then place 4 right after 1, and place 5 right after 2, getting 1,4,3,2,5. - _Clark Kimberling_, Oct 29 2009
%p A003603 := proc(n::posint)
%p local r,c,W ;
%p for r from 1 do
%p for c from 1 do
%p W := A035513(r,c) ;
%p if W = n then
%p return r ;
%p elif W > n then
%p break ;
%p end if;
%p end do:
%p end do:
%p end proc:
%p seq(A003603(n),n=1..100) ; # _R. J. Mathar_, Aug 13 2021
%t num[n_, b_] := Last[NestWhile[{Mod[#[[1]], Last[#[[2]]]], Drop[#[[2]], -1], Append[#[[3]], Quotient[#[[1]], Last[#[[2]]]]]} &, {n, b, {}}, #[[2]] =!= {} &]];
%t left[n_, b_] := If[Last[num[n, b]] == 0, Dot[num[n, b], Rest[Append[Reverse[b], 0]]], n];
%t fractal[n_, b_] := # - Count[Last[num[Range[#], b]], 0] &@
%t FixedPoint[left[#, b] &, n];
%t Table[fractal[n, Table[Fibonacci[i], {i, 2, 12}]], {n, 30}] (* _Birkas Gyorgy_, Apr 13 2011 *)
%t row[1] = row[2] = {1};
%t row[n_] := row[n] = Module[{ro, pos, lp, ins}, ro = row[n-1]; pos = Position[ro, Alternatives @@ Intersection[ro, row[n-2]]] // Flatten; lp = Length[pos]; ins = Range[lp] + Max[ro]; Do[ro = Insert[ro, ins[[i]], pos[[i]] + i], {i, 1, lp}]; ro];
%t Array[row, 9] // Flatten (* _Jean-François Alcover_, Jul 12 2016 *)
%o (Haskell) -- according to Kimberling, see formula section.
%o a003603 n k = a003603_row n !! (k-1)
%o a003603_row n = a003603_tabl !! (n-1)
%o a003603_tabl = [1] : [1] : wythoff [2..] [1] [1] where
%o wythoff is xs ys = f is xs ys [] where
%o f js [] [] ws = ws : wythoff js ys ws
%o f js [] [v] ws = f js [] [] (ws ++ [v])
%o f (j:js) (u:us) (v:vs) ws
%o | u == v = f js us vs (ws ++ [v,j])
%o | u /= v = f (j:js) (u:us) vs (ws ++ [v])
%o -- _Reinhard Zumkeller_, Jan 26 2012
%Y Equals A019586(n) + 1. Cf. A003602, A000045, A033192, A035513, A035612, A094967, A265650.
%K nonn,easy,nice,eigen,tabf
%O 1,4
%A _N. J. A. Sloane_, _Mira Bernstein_
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
%E Keyword tabf added by _Reinhard Zumkeller_, Jan 26 2012