Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Project Euler 12: Highly divisible triangular number

  1. May 31, 2014 #1
    After running into the dilemma of having nothing to do a little while ago, I decided to try working on a Project Euler problem with a mathematical approach. Not being a mathematician, I soon found myself in a rut.

    Now, what I have so far is this:

    1. Let T(n) be the nth Triangle Number, n > 0.
    2. Define f(n) = n for all odd n.
    3. Define f(n) = n+1 for all even n.
    4. Define g(n) = floor([itex]\frac{n}{2}[/itex])+1 for all odd n.
    5. Define g(n) = [itex]\frac{n}{2}[/itex] for all even n.
    6. I have proven by induction that f(n) and g(n) are ALWAYS divisors of T(n).

    I have therefore found two persistent sequences in the divisors of the Triangle Numbers. Naturally, all of the divisors of g(n) and f(n) are also divisors of T(n). If both g(n) and f(n) are less than sqrt(T(n)), then we can readily conclude that there are at least twice as many divisors of T(n) as there are of g(n) and f(n).

    It was my hope that by analyzing these two sequences, I could find an underlying metasequence that governs the divisors of the triangle numbers, eventually finding a small set of sequences that completely describe the divisors of T(n) when n is below some upper bound. Instead, I have found myself completely unable to detect any further patterns.

    At first I toyed with the idea that f(n) and g(n) were the only governing sequences for n > 1, but then I realized that T(8) is a counterexample, because the divisor 6 cannot be derived from those two sequences alone.

    So, my question is this: Is there any promise in this approach? If so, could someone give me a gentle nudge in the right direction? I can easily solve this in a short time using a program and prime factorization, but I would love to solve this entirely on paper, if possible.
    Last edited: May 31, 2014
  2. jcsd
  3. May 31, 2014 #2
    Do you know that the ##n##th triangle number is equal to [tex]\frac{n(n+1)}{2}[/tex]
  4. May 31, 2014 #3
    Yes, I used that to prove point 6. Besides suddenly seeing an easier way to prove the relation with f(n) than the proof that I used, I can't think of anything else to do with it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook