A381579 The Chung-Graham representation of n: representation of n in base of even-indexed Fibonacci numbers.

0, 1, 2, 10, 11, 12, 20, 21, 100, 101, 102, 110, 111, 112, 120, 121, 200, 201, 202, 210, 211, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1021, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1121, 1200, 1201, 1202, 1210, 1211, 2000, 2001, 2002, 2010, 2011, 2012, 2020, 2021

Offset: 0

Author

Amiram Eldar, Feb 28 2025

Keywords

• nonn
• easy
• base

Comments

Chung and Graham (1981, 1984) proved that every nonnegative integer n can be uniquely represented as a sum n = Sum_{i>=1} d_i * Fibonacci(2*i), where each d_i is in {0, 1, 2}, and if d_i = d_j = 2 with i < j, then for some k, i < k < j, we have d_k = 0.

Examples

			a(3) = 10 since 3 = 1 * 3 + 0 * 1 = 3 * Fibonacci(2*2) + 0 * Fibonacci(2*1).
a(10) = 102 since 10 = 1 * 8 + 0 * 3 + 2 * 1 = 1 * Fibonacci(2*3) + 0 * Fibonacci(2*2) + 2 * Fibonacci(2*1).
		

Links

• Amiram Eldar, Table of n, a(n) for n = 0..10000
• Rob Burns, Chung-Graham and Zeckendorf representations, arXiv:2502.18870 [math.NT], 2025.
• Hung Viet Chu, Aney Manish Kanji, and Zachary Louis Vasseur, Fixed-Term Decompositions Using Even-Indexed Fibonacci Numbers, arXiv:2501.03231 [math.GM], 2024.
• F. R. K. Chung and R. L. Graham, On irregularities of distribution of real sequences, Proc. Nat. Acad. Sci. USA, Vol. 78, No. 7 (1981), p. 4001.
• F. R. K. Chung and R. L. Graham, On irregularities of distribution, Finite and Infinite Sets, Colloquia Mathematica Societatis János Bolyai, Vol. 37, North-Holland, 1984, pp. 181-222; alternative link.

Crossrefs

Cf. A000045, A001906, A291711 (sum of digits).

Similar sequences: A014417, A104326.

Programs

Mathematica

f[n_] := f[n] = Fibonacci[2*n]; a[n_] := Module[{s = 0, m = n, k}, While[m > 0, k = 1; While[m > f[k], k++]; If[m < f[k], k--]; If[m >= 2*f[k], s += 2*10^(k-1); m -= 2*f[k], s += 10^(k-1); m -= f[k]]]; s]; Array[a, 50, 0]

PARI

m = 20; fvec = vector(m, i, fibonacci(2*i)); f(n) = if(n <= m, fvec[n], fibonacci(2*n));
a(n) = {my(s = 0, m = n, k); while(m > 0, k = 1; while(m > f(k), k++); if(m < f(k), k--); if(m >= 2*f(k), s += 2*10^(k-1); m -= 2*f(k), s += 10^(k-1); m -= f(k))); s;}