cp's OEIS Frontend

A003603 Fractal sequence obtained from Fibonacci numbers (or Wythoff array).

%I A003603 M0138 #92 Jan 05 2025 19:51:33
%S A003603 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 A003603 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 A003603 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 A003603 Fractal sequence obtained from Fibonacci numbers (or Wythoff array).
%C A003603 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 A003603 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003603 Reinhard Zumkeller, <a href="/A003603/b003603.txt">Rows n = 1..20 of triangle, flattened</a>
%H A003603 J. H. Conway and N. J. A. Sloane, <a href="/A019586/a019586.pdf">Notes on the Para-Fibonacci and related sequences</a>.
%H A003603 David Garth and Joseph Palmer, <a href="https://web.archive.org/web/2024*/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 A003603 Clark Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/fractals.html">Fractal sequences</a>.
%H A003603 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 A003603 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 A003603 N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>.
%F A003603 Vertical para-budding sequence: says which row of Wythoff array (starting row count at 1) contains n.
%F A003603 If one deletes the first occurrence of 1, 2, 3, ... the sequence is unchanged.
%F A003603 From _Clark Kimberling_, Oct 29 2009: (Start)
%F A003603 The fractal sequence of the Wythoff array can be constructed without reference to the Wythoff array or Fibonacci numbers. Write initial rows:
%F A003603 Row 1: .... 1
%F A003603 Row 2: .... 1
%F A003603 Row 3: .... 1..2
%F A003603 Row 4: .... 1..3..2
%F A003603 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 A003603 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 A003603 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 A003603 := proc(n::posint)
%p A003603     local r,c,W ;
%p A003603     for r from 1 do
%p A003603         for c from 1 do
%p A003603             W := A035513(r,c) ;
%p A003603             if W = n then
%p A003603                 return r ;
%p A003603             elif W > n then
%p A003603                 break ;
%p A003603             end if;
%p A003603         end do:
%p A003603     end do:
%p A003603 end proc:
%p A003603 seq(A003603(n),n=1..100) ; # _R. J. Mathar_, Aug 13 2021
%t A003603 num[n_, b_] := Last[NestWhile[{Mod[#[[1]], Last[#[[2]]]], Drop[#[[2]], -1], Append[#[[3]], Quotient[#[[1]], Last[#[[2]]]]]} &, {n, b, {}}, #[[2]] =!= {} &]];
%t A003603 left[n_, b_] := If[Last[num[n, b]] == 0, Dot[num[n, b], Rest[Append[Reverse[b], 0]]], n];
%t A003603 fractal[n_, b_] := # - Count[Last[num[Range[#], b]], 0] &@
%t A003603    FixedPoint[left[#, b] &, n];
%t A003603 Table[fractal[n, Table[Fibonacci[i], {i, 2, 12}]], {n, 30}] (* _Birkas Gyorgy_, Apr 13 2011 *)
%t A003603 row[1] = row[2] = {1};
%t A003603 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 A003603 Array[row, 9] // Flatten (* _Jean-François Alcover_, Jul 12 2016 *)
%o A003603 (Haskell)  -- according to Kimberling, see formula section.
%o A003603 a003603 n k = a003603_row n !! (k-1)
%o A003603 a003603_row n = a003603_tabl !! (n-1)
%o A003603 a003603_tabl = [1] : [1] : wythoff [2..] [1] [1] where
%o A003603    wythoff is xs ys = f is xs ys [] where
%o A003603       f js     []     []     ws = ws : wythoff js ys ws
%o A003603       f js     []     [v]    ws = f js [] [] (ws ++ [v])
%o A003603       f (j:js) (u:us) (v:vs) ws
%o A003603         | u == v = f js us vs (ws ++ [v,j])
%o A003603         | u /= v = f (j:js) (u:us) vs (ws ++ [v])
%o A003603 -- _Reinhard Zumkeller_, Jan 26 2012
%Y A003603 Equals A019586(n) + 1. Cf. A003602, A000045, A033192, A035513, A035612, A094967, A265650.
%K A003603 nonn,easy,nice,eigen,tabf
%O A003603 1,4
%A A003603 _N. J. A. Sloane_, _Mira Bernstein_
%E A003603 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
%E A003603 Keyword tabf added by _Reinhard Zumkeller_, Jan 26 2012