Algorithms/Sequences/OnesCountingSequence.cs

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

namespace Algorithms.Sequences;

//github.com/ <summary>
//github.com/     <para>
//github.com/         1's-counting sequence: number of 1's in binary expression of n.
//github.com/     </para>
//github.com/     <para>
//github.com/         OEIS: https://oeis.org/A000120.
//github.com/     </para>
//github.com/ </summary>
public class OnesCountingSequence : ISequence
{
    //github.com/ <summary>
    //github.com/     <para>
    //github.com/         Gets the generated sequence of the 1's contained in the binary representation of n.
    //github.com/     </para>
    //github.com/     <para>
    //github.com/         The sequence is generated as follows.
    //github.com/         1. The initial 0 value is provided.
    //github.com/         2. A recursively generated sequence is iterated, starting with a length of 1 (i.e., 2^0),
    //github.com/            followed by increasing 2^x length values.
    //github.com/         3. Each sequence starts with the value 1, and a targeted value of depths that it will recurse
    //github.com/            for the specific iteration.
    //github.com/         4. If the call depth to the recursive function is met, it returns the value argument received.
    //github.com/         5. If the call depth has not been met, it recurses to create 2 sequences, one starting with the
    //github.com/            value argument, and the following with the value argument + 1.
    //github.com/         6. Using ':' as a visual separator for each sequence, this results in the following sequences
    //github.com/            that are returned sequentially after the initial 0.
    //github.com/            1 : 1, 2 : 1, 2, 2, 3 : 1, 2, 2, 3, 2, 3, 3, 4.
    //github.com/     </para>
    //github.com/     <remarks>
    //github.com/         <para>
    //github.com/         This one comes from thinking over information contained within the COMMENTS section of the OEIS page.
    //github.com/         </para>
    //github.com/         <para>
    //github.com/             Using the comments provided by Benoit Cloitre, Robert G. Wilson v, and Daniel Forgues, the above
    //github.com/             algorithm was coded.
    //github.com/         </para>
    //github.com/     </remarks>
    //github.com/ </summary>
    public IEnumerable<BigInteger> Sequence
    {
        get
        {
            yield return 0;
            var depth = 0;
            while (true)
            {
                foreach (var count in GenerateFractalCount(BigInteger.One, depth))
                {
                    yield return count;
                }

                depth++;
            }
        }
    }

    //github.com/ <summary>
    //github.com/     <para>
    //github.com/         Recursive function to generate sequences.
    //github.com/     </para>
    //github.com/ </summary>
    //github.com/ <param name="i">The value that will start off the current IEnumerable sequence.</param>
    //github.com/ <param name="depth">The remaining depth of recursion.  Value of 0 is the stop condition.</param>
    //github.com/ <returns>An IEnumerable sequence of BigInteger values that can be iterated over.</returns>
    private static IEnumerable<BigInteger> GenerateFractalCount(BigInteger i, int depth)
    {
        // Terminal condition
        if (depth == 0)
        {
            yield return i;
            yield break;
        }

        foreach (var firstHalf in GenerateFractalCount(i, depth - 1))
        {
            yield return firstHalf;
        }

        foreach (var secondHalf in GenerateFractalCount(i + 1, depth - 1))
        {
            yield return secondHalf;
        }
    }
}