A095903 Lexical ordering of the lazy Fibonacci representations.

1, 2, 3, 4, 5, 7, 6, 8, 9, 12, 10, 13, 15, 20, 11, 14, 16, 21, 17, 22, 25, 33, 18, 23, 26, 34, 28, 36, 41, 54, 19, 24, 27, 35, 29, 37, 42, 55, 30, 38, 43, 56, 46, 59, 67, 88, 31, 39, 44, 57, 47, 60, 68, 89, 49, 62, 70, 91, 75, 96, 109, 143, 32, 40, 45, 58, 48, 61, 69, 90, 50, 63

Offset: 1

Author

Clark Kimberling, Jun 12 2004

Keywords

• easy
• nonn

Comments

A permutation of the natural numbers. As suggested by the example, the numbers can be generated as a graph consisting of two components, each being a tree. One tree has root 1 and consists of the numbers in the lower Wythoff sequence, A000201; the other has root 2 and consists of the numbers in the upper Wythoff sequence, A001950. (One could start with 0 and have a single tree instead of two components.)

Regard generations g(n) of the graph as rows of an array (see Example); then |g(n)| = 2^n. Every row includes exactly two Fibonacci numbers; specifically, row n includes F(2n) and F(2n+1). - Clark Kimberling, Mar 11 2015

Examples

			Start with 1,2. Suffix the next two Fibonacci numbers, getting 1+2, 1+3; 2+3, 2+5. Suffix the next two Fibonacci numbers, getting 1+2+3, 1+2+5, 1+3+5, 1+3+8; 2+3+5, 2+3+8, 2+5+8, 2+5+13. Continue, obtaining
row 1:  1,2
row 2:  3,4,5,7
row 3:  6,8,9,12,10,13,15,20
row 4:  11,14,16,21,17,22,25,33,18,23,26,34,28,36,41,54
		

Links

• Clark Kimberling, Table of n, a(n) for n = 1..4000

Crossrefs

Cf. A000045, A095791, A000201, A001950, A255773 (the 1-tree), A255774 (the 2-tree).

Programs

Mathematica

Map[Total,Fibonacci[Flatten[NestList[Flatten[Map[{Join[#,{Last[#]+1}],Join[#,{Last[#]+2}]}&,#],1]&,{{2},{3}},7],1]]]  (* Peter J. C. Moses, Mar 06 2015 *)

PARI

a(n) = n++; my(x=0,y=0); for(i=0,logint(n,2)-1, y++;[x,y]=[y,x+y]; if(bittest(n,i), [x,y]=[y,x+y])); y; \\ Kevin Ryde, Jun 19 2021