A135817 Length of Wythoff representation of n.

1, 1, 2, 3, 2, 4, 3, 3, 5, 4, 4, 4, 3, 6, 5, 5, 5, 4, 5, 4, 4, 7, 6, 6, 6, 5, 6, 5, 5, 6, 5, 5, 5, 4, 8, 7, 7, 7, 6, 7, 6, 6, 7, 6, 6, 6, 5, 7, 6, 6, 6, 5, 6, 5, 5, 9, 8, 8, 8, 7, 8, 7, 7, 8, 7, 7, 7, 6, 8, 7, 7, 7, 6, 7, 6, 6, 8, 7, 7, 7, 6, 7, 6, 6, 7, 6, 6, 6, 5, 10, 9, 9, 9, 8, 9, 8, 8, 9, 8, 8, 8, 7, 9, 8, 8

Offset: 1

Author

Wolfdieter Lang, Jan 21 2008

Keywords

• nonn
• base
• easy

Comments

For the Wythoff representation of n see the W. Lang reference and A189921.

The Wythoff complementary sequences are A(n):=A000201(n) and B(n)=A001950(n), n>=1. The Wythoff representation of n=1 is A(1) and for n>=2 there is a unique representation as composition of A- or B-sequence applied to B(1)=2. E.g., n=4 is A(A(B(1))), written as AAB or as `110`, i.e., 1 for A and 0 for B.

The Wythoff orbit of 1 (starting always with B(1), applying any number of A- or B-sequences) produces every number n>1 just once. This produces a binary Wythoff code for n>1, ending always in 0 (for B(1)). See the W. Lang link for this code.

Examples

			W(4) = `110`, i.e., 4 = A(A(B(1))) with Wythoff's A and B sequences.
		

References

• Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (editors), Application of Fibonacci numbers, vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337. [See A317208 for a link.]

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Aviezri S. Fraenkel, From Enmity to Amity, American Mathematical Monthly 117 (2010) 646-648.
• Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quarterly 33 (1995) 3-8.
• Wolfdieter Lang, Wythoff representations for n=1...150.

Crossrefs

Cf. A135818 (number of 1's or A's in Wythoff representation of n).

Cf. A007895 (number of 0's or B's in Wythoff representation of n).

Row lengths of A189921.

Programs

Mathematica

z[n_] := Floor[(n + 1)*GoldenRatio] - n - 1; h[n_] := z[n] - z[n - 1]; w[n_] := Module[{m = n, zm = 0, hm, s = {}}, While[zm != 1, hm = h[m]; AppendTo[s, hm]; If[hm == 1, zm = z[m], zm = z[z[m]]]; m = zm]; s]; w[0] = 0; a[n_] := Length[w[n]]; Array[a, 100] (* Amiram Eldar, Jul 01 2023 *)

Formula

a(n) = number of digits in Wythoff representation of n>=1.

a(n) = length of Wythoff code for n>=1.

a(n) = number of applications of Wythoff sequences A or B on 1 in the Wythoff representation for n >=1.