#### A000010 Euler's Totient

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