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();
        }
    }
}