Find the first Triangular number which has 50 factors?

Question

-----Modification of code requested --------

Question : Count the Fast Triangular Series Number which is having 50 Factors ?

Elaborated : Let's say there is a series

   1 : 1
   3 : 1+2
   6 : 1+2+3 
   10 : 1+2+3+4
   15 : 1+2+3+4+5
   21 : 1+2+3+4+5+6
   28 : 1+2+3+4+5+6+7

here 1,3,6,10,15,21,28 are the numbers coming under triangular series.

lets see the factors of the number

    Number factors         Count
    1     : 1               1              
    3     : 1,3             2
    6     : 1,2,3,6         4
    10    : 1,2,5,10        4
    15    : 1,3,5,15        4
    21    : 1,3,7,21        4
    28    : 1,2,4,7,14,28   6

here 6 is the first triangular number which is having 4 factors. even if 10,15,21 also having 4 factors but they are not the 1st one. Like that lets take a number as 2 which is having 2 factors as 1 and 2 same for number 3 also having 2 factors as 1 and 3

but as per question 3 will be the answer not 2 because 2 is not coming under Triangular series number list even if it is faster than 3.

Answer 1

Solution : Let me break down the Question in multiple modules.

1) Find the triangular series till a number.

2) Store all identified numbers in a List of integers

3) Find the no of factors for a particular number

4) Loop trough the each item of triangular series and find the count of factors for each number.

5) check the the first one whose count is 50 then display the value

6) write break statement to show only the first 50th number.

Program

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace IsNumberTringularSeriesConsoleApp
{ 
    class Program
    {
        /// <summary>
        /// Listing all numbers comes under Triangular series.
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        static List<int> GetTriangularNumbers(int number)
        {
            List<int> lstTriangularNumbers = new List<int>();
            int i;
            int sum = 0;
            int triangularNumber = 0;
            for (i = 1; i < number; i++)
            {
                sum = sum + i;
                triangularNumber = sum;
                lstTriangularNumbers.Add(triangularNumber);
            }
            return lstTriangularNumbers;
        }

        /// <summary>
        /// returns(count) the number of factors for each number
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        public static int FactorCount(int number)
        {
            List<int> factors = new List<int>();
            int max = (int)Math.Sqrt(number);  //round down
            for (int factor = 1; factor <= max; ++factor)
            { 
                //test from 1 to the square root, or the int below it, inclusive.
                if (number % factor == 0)
                {
                    factors.Add(factor);
                    if (factor != number / factor)
                   {
                     // Don't add the square root twice!  
                        factors.Add(number / factor);
                   }
                }
            }
            return factors.Count;
        }

        static void Main(string[] args)
        {
            List<int> lstTriangularNumbers = new List<int>();
            List<int> factors = new List<int>();
            int count = 0;
            //Getting the list of numbers comes under triangular series till 5000
            lstTriangularNumbers = GetTriangularNumbers(5000);

            foreach (int number in lstTriangularNumbers)
            {
                /*
                 * Calling the FactorCount(number) function to check no of factors 
                 * available for the specific triangular number - number.
                 */
                 count = FactorCount(number);
                 //Console.WriteLine("No of factors for : " + number + " is : " + count);
                if (count == 50)
                {
                    Console.WriteLine("No of factors for first Triangular Number : " + number + " is : " + count);
                    break;
                }
            }
            Console.ReadLine();
        }
    }
}

Answer 2

Triangle number #2591 = 3357936 is the first one that has exactly 50 factors: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 36, 48, 54, 72, 81, 108, 144, 162, 216, 324, 432, 648, 1296, 2591, 5182, 7773, 10364, 15546, 20728, 23319, 31092, 41456, 46638, 62184, 69957, 93276, 124368, 139914, 186552, 209871, 279828, 373104, 419742, 559656, 839484, 1119312, 1678968, 3357936

Triangle number #12375 = 76576500 is the first one that has at least 500 factors (actually 576 factors): 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, ..., 19144125, 25525500, 38288250, 76576500

Triangle number #1569375 = 1231469730000 is the first one that has exactly 500 factors

The solution code itself is very easy, providing you can get divisors:

   public static long Solution(int factorsCount) {
      for (long i = 1; ; ++i) {
        long n = i * (i + 1) / 2;

        IList<long> factors = GetDivisors(n);

        // This code tests if a triangle number has exactly factorsCount factors
        // if you want to find out a triangle number which has at least factorsCount factors
        // change "==" comparison to ">=" one:
        // if (factors.Count >= factorsCount)  
        if (factors.Count == factorsCount) 
          return n;
      }
    }

  ...

  long solution = Solution(50);

If you haven't got a routine to get number's factors, you can use this one:

// Get prime divisors 
private static IList<long> CoreGetPrimeDivisors(long value, IList<int> primes) {
  List<long> results = new List<long>();

  int v = 0;
  long threshould = (long) (Math.Sqrt(value) + 1);

  for (int i = 0; i < primes.Count; ++i) {
    v = primes[i];

    if (v > threshould)
      break;

    if ((value % v) != 0)
      continue;

    while ((value % v) == 0) {
      value = value / v;

      results.Add(v);
    }

    threshould = (long) (Math.Sqrt(value) + 1);
  }

  if (value > 1)
    results.Add(value);

  return results;
}

/// <summary>
/// Get prime divisors 
/// </summary>
public static IList<long> GetPrimeDivisors(long value, IList<int> primes) {
  if (!Object.ReferenceEquals(null, primes))
    return CoreGetPrimeDivisors(value, primes);

  List<long> results = new List<long>();

  while ((value % 2) == 0) {
    results.Add(2);

    value = value / 2;
  }

  while ((value % 3) == 0) {
    results.Add(3);

    value = value / 3;
  }

  while ((value % 5) == 0) {
    results.Add(5);

    value = value / 5;
  }

  while ((value % 7) == 0) {
    results.Add(7);

    value = value / 7;
  }

  int v = 0;
  long n = (long) (Math.Sqrt(value) / 6.0 + 1);
  long threshould = (long) (Math.Sqrt(value) + 1);

  for (int i = 2; i <= n; ++i) {
    v = 6 * i - 1;

    if ((value % v) == 0) {
      while ((value % v) == 0) {
        results.Add(v);

        value = value / v;
      }

      threshould = (long) (Math.Sqrt(value) + 1);
    }

    v = 6 * i + 1;

    if ((value % v) == 0) {
      while ((value % v) == 0) {
        results.Add(v);

        value = value / v;
      }

      threshould = (long) (Math.Sqrt(value) + 1);
    }

    if (v > threshould)
      break;
  }

  if (value > 1) {
    if (results.Count <= 0)
      results.Add(value);
    else if (value != results[results.Count - 1])
      results.Add(value);
  }

  return results;
}

/// <summary>
/// Get all divisors
/// </summary>
public static IList<long> GetDivisors(long value, IList<int> primes) {
  HashSet<long> hs = new HashSet<long>();

  IList<long> divisors = GetPrimeDivisors(value, primes);

  ulong n = (ulong) 1;
  n = n << divisors.Count;

  for (ulong i = 1; i < n; ++i) {
    ulong v = i;
    long p = 1;

    for (int j = 0; j < divisors.Count; ++j) {
      if ((v % 2) != 0)
        p *= divisors[j];

      v = v / 2;
    }

    hs.Add(p);
  }

  List<long> result = new List<long>();

  result.Add(1);

  var en = hs.GetEnumerator();

  while (en.MoveNext())
    result.Add(en.Current);

  result.Sort();

  return result;
}

/// <summary>
/// Get all divisors
/// </summary>
public static IList<long> GetDivisors(long value) {
  return GetDivisors(value, null);
}

Answer 3

here is my answer

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TriangularSeries
{
    class MyClass
    {
        static void Main(string[] args)
        {
            int result;
            TriangularSeries aSeries = new TriangularSeries();
            result = aSeries.TSeries();
            Console.WriteLine("The first Triangular Series number that has 50Factors is : " + result);
            Console.Read();
        }
    }

    //Find the Triangular Series numbers
    class TriangularSeries
    {
        public int TSeries()
        {
            int fCount = 0, T1 = 1, i = 1, T2 = 0, fval = 0;
            while (fCount != 50)
            {
                i += 1;
                T2 = T1 + i;

                fCount = CalcFactors(T1);
                fval = T1;                   
                T1 = T2;

            }
            return fval;
        }

        public int CalcFactors(int num1)
        {

            List<int> factors = new List<int>();
            int max = (int)Math.Sqrt(num1);  //round down
            for (int factor = 1; factor <= max; ++factor)
            {
                //test from 1 to the square root, or the int below it, inclusive.
                if (num1 % factor == 0)
                {
                    factors.Add(factor);
                    if (factor != num1 / factor)
                    {
                        // Don't add the square root twice!  
                        factors.Add(num1 / factor);
                    }
                }
            }
            return factors.Count;

        }
    }   
}

Answer 4

Here is my program in C language

#include<stdio.h>
int i;
int num1=0,num2=1;
int a[3000];
int tri_series()         //This function finds the Triangular series numbers
{
    for(i=0;num2<=3000;i++)
    {
    num1=num1+num2;
    a[i]=num1;
    num2++;
    }
}
int main()
{
tri_series();            //Calling the function tri_series
int num,count;
    for(i=0;i<=3000;i++)
    {
      count=0;
      for(num=1;num<=a[i];num++)
      {
        if(a[i]%num==0)  //Finds the factors of each Triangular Series Number 
        count=count+1;   
      }
      if(count==50)      //Break at the first Triangular Series Number having 50 factors
      {
       printf("%d:%d\t",a[i],count);
       break;
      }
    }
}

Performance issue: This code generates a performance issue when comes to execution time. It takes "a minute" to execute and display the output.