login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003603 Fractal sequence obtained from Fibonacci numbers (or Wythoff array).
(Formerly M0138)
57

%I M0138

%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 C. Kimberling, <a href="http://faculty.evansville.edu/ck6/integer/fractals.html">Fractal sequences</a>

%H C. 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 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)

%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

%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, A035513, A033192, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 07:05 EDT 2018. Contains 316276 sequences. (Running on oeis4.)