Skip to content

Problem 12: Highly divisible triangular number

Link to the problem: https://projecteuler.net/problem=12.

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be \(1 + 2 + 3 + 4 + 5 + 6 + 7 = 28\).

The first ten terms would be \(1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\)

Let us list the factors of the first seven triangle numbers: 

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

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

A simple solution

Let's call our triangle number \(t\). A brute force solution might look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(defwire main-wire
  123 = .limit
  1 >= .t >= .a
  0 >= .count

  (Repeat
   (-> 0 > .count
       (Math.Inc .a)
       .t (Math.Add .a) > .t
       (ForRange
        1 .t
        (When
         (-> >= .i .t (Math.Mod .i) (Is 0))
         (Math.Inc .count))))
   :Forever true
   :Until (-> .count (IsMore .limit)))

  .t (Assert.Is 157080 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:02:01.000] [T-5192] [logging.cpp::62] [main-wire] Answer: 157080

However, it is extremely slow. We had to reduce the limit so it could run in a reasonable amount of time.

A better and faster solution

We can do better than the above solution.

Considering that for every divisor up to the square root there is by construction a corresponding divisor above it, we can count the number of divisors up to \(\sqrt{t}\) and double that number — unless the last divisor is exactly \(\sqrt{t}\), in which case we should only count it once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
(defwire main-wire
  500 = .limit
  1 >= .t >= .a
  0 >= .count

  (Repeat
   (-> 0 > .count
       (Math.Inc .a)
       .t (Math.Add .a) > .t
       (ToFloat) (Math.Sqrt) (ToInt) >= .ttx
       (ForRange
        1 .ttx
        (When
         (-> >= .i
             .t (Math.Mod .i) (Is 0))
         (-> .count (Math.Add 2) > .count)))
       (When
        (-> .ttx (Math.Multiply .ttx) (Is .t))
        (Math.Dec .count)))
   :Forever true
   :Until (-> .count (IsMore .limit)))

  .t (Assert.Is 76576500 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:02:08.677] [T-4792] [logging.cpp::62] [main-wire] Answer: 76576500

More details on the Project Euler's website: https://projecteuler.net/overview=012.