Euler Solution 45

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 45

Find the next number that is triangular, pentagonal and hexagonal after 40755, where:

  • Triangular(n) = n(n + 1)/2
  • Pentagonal(n) = n(3n - 1)/2
  • Hexagonal(n) = n(2n - 1)

C by SanguineV

Runtime: 6.19ms

/* The formulas are more complex than a simple addition with an iterator that
 * can also generate each of the numbers. The initial states are:
 * Triangular number 1, iterator 1, iteration value 1
 * Pentagonal number 1, iterator 4, iteration value 3
 * Hexagonal number 1, iterator 5, iteration value 4
 * use these to increase and also calculate the starting values for start point
 * of 40755. */
#include <stdio.h>

int main(void) {
  // Initialise the variables used.
  unsigned long titer = 286;
  unsigned long tval = 40755;
  unsigned long piter = 496;
  unsigned long pval = 40755;
  unsigned long hiter = 573;
  unsigned long hval = 40755;
  // Iterate once on the slowest growing number (triangular)
  tval += titer;
  titer++;
  // Loop until all three are equal
  while (!(tval == pval && hval == pval)) {
    // If the triangular number is smallest then increase it
    if (tval <= pval && tval <= hval) {
      tval += titer;
      titer++;
    }
    // If the pentagonal number is smallest then increase it
    else if (pval <= tval && pval <= hval) {
      pval += piter;
      piter += 3;
    }
    // If the hexagonal number is smallest then increase it
    else if (hval <= tval && hval <= pval) {
      hval += hiter;
      hiter += 4;
    }
  }
  // Print the result and exit
  printf("%u\n",tval);
  return 0;
}

Apparently "unsigned long long"s behave really oddly, stick to "unsigned long" if you need to use large numbers. May also be why problems occurred in other attempts...

Python by Althalus

Runtime: 140 ms

All hexagonal numbers are triangular.

pentagonals = set([n*(3*n-1)/2 for n in range(1,60001)])
hexagonals = set([n*(2*n-1) for n in range(1,60001)])

print pentagonals.intersection(hexagonals)
Personal tools