Algorithms/Sequences/MakeChangeSequence.cs

using System.Collections.Generic;
using System.Numerics;

namespace Algorithms.Sequences;

//github.com/ <summary>
//github.com/     <para>
//github.com/         Number of ways of making change for n cents using coins of 1, 2, 5, 10 cents.
//github.com/     </para>
//github.com/     <para>
//github.com/         OEIS: https://oeis.org/A000008.
//github.com/     </para>
//github.com/ </summary>
public class MakeChangeSequence : ISequence
{
    //github.com/ <summary>
    //github.com/     <para>
    //github.com/         Gets sequence of number of ways of making change for n cents
    //github.com/         using coins of 1, 2, 5, 10 cents.
    //github.com/     </para>
    //github.com/     <para>
    //github.com/         Uses formula from OEIS page by Michael Somos
    //github.com/         along with first 17 values to prevent index issues.
    //github.com/     </para>
    //github.com/     <para>
    //github.com/         Formula:
    //github.com/         a(n) = a(n-2) +a(n-5) - a(n-7) + a(n-10) - a(n-12) - a(n-15) + a(n-17) + 1.
    //github.com/     </para>
    //github.com/ </summary>
    public IEnumerable<BigInteger> Sequence
    {
        get
        {
            var seed = new List<BigInteger>
                       {
                           1, 1, 2, 2, 3, 4, 5, 6, 7, 8,
                           11, 12, 15, 16, 19, 22, 25,
                       };
            foreach (var value in seed)
            {
                yield return value;
            }

            for(var index = 17; ; index++)
            {
                BigInteger newValue = seed[index - 2] + seed[index - 5] - seed[index - 7]
                                    + seed[index - 10] - seed[index - 12] - seed[index - 15]
                                    + seed[index - 17] + 1;

                seed.Add(newValue);
                yield return newValue;
            }
        }
    }
}