A265744 a(n) is the number of Pell numbers (A000129) needed to sum to n using the greedy algorithm (A317204).

0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 4, 5, 3

Offset

0,4

Comments

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.

It would be nice to know for sure whether this sequence also gives the least number of Pell numbers that add to n, i.e., that there cannot be even better nongreedy solutions.

References

A. F. Horadam, Zeckendorf representations of positive and negative integers by Pell numbers, Applications of Fibonacci Numbers, Springer, Dordrecht, 1993, pp. 305-316.

Links

Antti Karttunen, Table of n, a(n) for n = 0..13860

L. Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Pellian Representations, The Fibonacci Quarterly, Vol. 10, No. 5 (1972), pp. 449-488.

Formula

a(n) = A007953(A317204(n)). - Amiram Eldar, Mar 12 2022

Mathematica

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; a[n_] := Module[{s = {}, m = n, k}, While[m > 0, k = 1; While[pell[k] <= m, k++]; k--; AppendTo[s, k]; m -= pell[k]; k = 1]; Plus @@ IntegerDigits[Total[3^(s - 1)], 3]]; Array[a, 100, 0] (* Amiram Eldar, Mar 12 2022 *)

Crossrefs

Cf. A000129, A007953, A317204.

Cf. also A014420, A053610, A265404, A265743, A265745.

Similar sequences: A007895, A116543, A278043.

Sequence in context: A245573 A236968 A345220 * A331083 A245588 A014420

Adjacent sequences: A265741 A265742 A265743 * A265745 A265746 A265747

Keyword

nonn,base

Author

Antti Karttunen, Dec 17 2015

Status

approved