Challenge: Highly Divisible Triangular Number

Posted on: July 13, 2016 2:45:35 AM

This challenge wants you to return the first triangular number that has over 500 factors. This challenge was a 2 part, first you have to be able to calculate out a "triangular number" which they define as a natural number added upon itself (similar to Fibonacci numbers) so that the 7th number in the series would be 1+2+3+4+5+6+7 or 28. The second part is being able to quickly calculate all the factors of a number. This was relatively straight forward, so I'll just post the code, there are comments in certain areas as to why I chose to do it like I did.

Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ProjectEuler_12
{
    internal class Program
    {
        private static HashSet GetMultiples(long num)
        {
            // use a hashset to guarantee uniqueness
            HashSet multiples = new HashSet { 1L, num };

            long root = (long)Math.Sqrt(num);

            // we only need to loop up to the square root of the num
            // because we're getting both the low and high factor of the num at once
            // no number could be higher than root*root
            for (long i = 2; i <= root; i++)
            {
                if (num % i == 0)
                {
                    multiples.Add(i);
                    multiples.Add(num / i);
                }
            }

            return multiples;
        }

        private static void Main(string[] args)
        {
            IEnumerable triangularNumbers = TriangularNumberGenerator();

            int multipleCount = 0;
            using (var enumerator = triangularNumbers.GetEnumerator())
            {
                long count = 0;
                long highestMultipleCountAchieved = 0;

                while (multipleCount < 500)
                {
                    enumerator.MoveNext();
                    count++;

                    multipleCount = GetMultiples(enumerator.Current).Count;

                    if (multipleCount > highestMultipleCountAchieved)
                    {
                        highestMultipleCountAchieved = multipleCount;
                        Debug.WriteLine("Number: {2}, Index: {0}, Multiple Count: {1}", count, highestMultipleCountAchieved, enumerator.Current);
                    }
                }

                Console.WriteLine("First triangular number index to have 500 multiples: {0}\r\nTriangular Number: {1}", count, enumerator.Current);
            }
        }

        /// <summary>
        /// The sequence of triangle numbers is generated by adding the natural numbers.
        /// </summary>
        /// <returns></returns>
        private static IEnumerable TriangularNumberGenerator()
        {
            long prevNum = 0;
            long sum = 0;

            while (true)
            {
                sum += ++prevNum;

                // use of yield return lets us go up as high as we need and only
                // as high as we need in this infinite series
                yield return sum;
            }
        }
    }
}

Comments


No comments yet, be the first to leave one.

Leave a Comment