A355717 Smallest number of generalized pentagonal numbers which sum to n.

0, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 3, 1, 2, 2, 1, 2, 2, 3, 2, 2, 3, 1, 2, 2, 3, 1, 2, 2, 2, 2, 2, 3, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 3, 2, 2, 3, 2, 2, 3, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 3, 2, 3, 3, 2, 1, 2, 2, 2, 3, 2, 3, 1, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 3, 2, 3, 2, 1, 2, 2, 3, 2, 2, 3, 2, 1

Offset: 0

Author

Bernard Schott, Jul 15 2022

Keywords

• nonn

Comments

From Euler's Pentagonal Number Theorem, every number is expressible as the sum of at most three generalized pentagonal numbers (A001318) (see Richard K. Guy reference).

Corresponding sums of only pentagonal numbers of positive rank are A100878(n). Those numbers are a subset of the generalized pentagonals so that a(n) <= A100878(n).

More specifically, by the definition given in the name, we understand the following: Given n >= 0 we seek a multiset S such that (1) S is a multiset of GPN = {0, 1, 2, 5, ...} = A001318; (2) Sum(S) = n; (3) if T is a multiset of GPN and Sum(T) = n then card(T) >= card(S). Additionally one might require that the set is not empty. If a multiset satisfies these three conditions, then a(n) = card(S). Note that no actual summation has to be performed to decide the value of a(n); only membership in GPN needs to be tested, as shown in the Maple and Python program. - Peter Luschny, Jul 18 2022

Examples

			Let GPN = {0, 1, 2, 5, ...} be the generalized pentagonal numbers.
a(0) = 0 since {} is a multiset of GPN, Sum {} = 0, and card({}) = 0.
a(1) = 1 since {1} is a multiset of GPN, Sum {1} = 1, and card({1}) = 1.
a(3) = 2 since {1, 2} is a multiset of GPN, Sum {1, 2} = 3, and card({1, 2}) = 2.
a(11) = 3 since {2, 2, 7} is a multiset of GPN, Sum {2, 2, 7} = 11, card({2, 2, 7}) = 3, and no other multiset S of GPN with Sum(S) = 11 has less members.
		

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section D3, Figurate numbers, pp. 222-228.

Links

• Eric Weisstein's World of Mathematics, Pentagonal Number Theorem.

Crossrefs

Cf. A001318, A093519 (indices of 3's).

Cf. A100878.

Programs

Maple

A355717_list := proc(upto) local P, Q, k, q, isgpn; P := []; Q := [0];
isgpn := k -> ormap(n -> 0 = 8*k - (n + irem(n,2)) * (3*n + 2 - irem(n,2)), [$0..k]);
for k from 1 to upto do
    q := 3;
    if isgpn(k) then
        P := [op(P), k]; q := 1;
        elif ormap(p -> member(k - p, P), P) then q := 2 fi:
        Q := [op(Q), q];
od: Q end:
print(A355717_list(100));  # Peter Luschny, Jul 18 2022

Python

def A355717_list(ln: int) -> list[int]:
    P: list[int] = []
    Q: list[int] = [0]
    def is_gpn(k: int) -> bool:
        return any(8 * k == ((n + n % 2) * (3 * n + 2 - n % 2)) for n in range(k + 1))
    for k in range(1, ln):
        q = 3
        if is_gpn(k):
            P.append(k)
            q = 1
        elif any([(k - p) in P for p in P]):
            q = 2
        Q.append(q)
    return Q
print(A355717_list(100))  # Peter Luschny, Jul 18 2022

Formula

a(n) <= 3.

a(A001318(n)) = 1.