EulerTotientSequence.cs

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

namespace Algorithms.Sequences;

/// <summary>
///     <para>
///         Sequence of Euler totient function phi(n).
///     </para>
///     <para>
///         Wikipedia: https://en.wikipedia.org/wiki/Euler%27s_totient_function.
///     </para>
///     <para>
///         OEIS: https://oeis.org/A000010.
///     </para>
/// </summary>
public class EulerTotientSequence : ISequence
{
    /// <summary>
    ///     <para>
    ///         Gets sequence of Euler totient function phi(n).
    ///     </para>
    ///     <para>
    ///         'n' is copied from value of the loop of i that's being enumerated over.
    ///         1) Initialize result as n
    ///         2) Consider every number 'factor' (where 'factor' is a prime divisor of n).
    ///            If factor divides n, then do following
    ///            a) Subtract all multiples of factor from 1 to n [all multiples of factor
    ///               will have gcd more than 1 (at least factor) with n]
    ///            b) Update n by repeatedly dividing it by factor.
    ///         3) If the reduced n is more than 1, then remove all multiples
    ///            of n from result.
    ///     </para>
    ///     <para>
    ///         Base code was from https://www.geeksforgeeks.org/eulers-totient-function/.
    ///      </para>
    ///     <para>
    ///         Implementation avoiding floating point operations was used for base
    ///         and replacement of loop going from 1 to sqrt(n) was replaced with
    ///         List of prime factors.
    ///     </para>
    /// </summary>
    public IEnumerable<BigInteger> Sequence
    {
        get
        {
            yield return BigInteger.One;

            for (BigInteger i = 2; ; i++)
            {
                var n = i;
                var result = n;

                var factors = PrimeFactors(i);
                foreach (var factor in factors)
                {
                    while (n % factor == 0)
                    {
                        n /= factor;
                    }

                    result -= result / factor;
                }

                if (n > 1)
                {
                    result -= result / n;
                }

                yield return result;
            }
        }
    }

    /// <summary>
    ///     <para>
    ///         Uses the prime sequence to find all prime factors of the
    ///         number we're looking at.
    ///     </para>
    ///     <para>
    ///         The prime sequence is examined until its value squared is
    ///         less than or equal to target, and checked to make sure it
    ///         evenly divides the target.  If it evenly divides, it's added
    ///         to the result which is returned as a List.
    ///     </para>
    /// </summary>
    /// <param name="target">Number that is being factored.</param>
    /// <returns>List of prime factors of target.</returns>
    private static IEnumerable<BigInteger> PrimeFactors(BigInteger target)
    {
        return new PrimesSequence()
              .Sequence.TakeWhile(prime => prime * prime <= target)
              .Where(prime => target % prime == 0)
              .ToList();
    }
}