Project Euler Problem 660

Solution

Answer: 474766783

For a triangle with sides $a,b,c$ and a $120^\circ$ angle opposite $c$, the Law of Cosines gives

$$c^2=a^2+b^2-2ab\cos 120^\circ$$

Since $\cos 120^\circ=-\tfrac12$,

$$c^2=a^2+b^2+ab.$$

A classical parametrization of all integer solutions of

$$c^2=a^2+b^2+ab$$

$$\begin{aligned} a &= d(m^2-n^2),\ b &= d(2mn+n^2),\ c &= d(m^2+mn+n^2), \end{aligned}$$

with integers $m>n>0$ and scale factor $d\ge1$.

So the problem reduces to:

Generate all integer $120^\circ$ triangles.
Convert each side to base $n$.
Check whether the concatenation of the three representations uses each digit $0,\dots,n-1$ exactly once.
Sum the largest sides.

A crucial observation is that the total number of digits across the three sides must be exactly $n$, so for $9\le n\le18$ the search space is still manageable with aggressive pruning.

Python implementation

from collections import Counter

def to_base(x, b):
    """Return digits of x in base b as a string."""
    if x == 0:
        return "0"
    s = []
    while x:
        s.append(str(x % b))
        x //= b
    return ''.join(reversed(s))

def is_pandigital_triangle(a, b, c, base):
    """
    Check whether the three sides written in base 'base'
    use every digit 0..base-1 exactly once.
    """
    sa = to_base(a, base)
    sb = to_base(b, base)
    sc = to_base(c, base)

    s = sa + sb + sc

    # Must use exactly base digits total
    if len(s) != base:
        return False

    # Digits available in this base
    target = Counter(str(i) for i in range(base))

    return Counter(s) == target

answer = 0

for base in range(9, 19):

    found = []

    # Digit count restriction:
    # largest side has at most base digits in base 'base'
    limit = base ** base

    # Generate all primitive 120-degree triangles
    # and allow scaling by d.
    for m in range(2, 500):
        for n in range(1, m):

            A = m*m - n*n
            B = 2*m*n + n*n
            C = m*m + m*n + n*n

            if C >= limit:
                break

            d = 1
            while d * C < limit:

                a = d * A
                b = d * B
                c = d * C

                # check all permutations
                triples = [
                    (a, b, c),
                    (b, a, c),
                ]

                ok = False
                for x, y, z in triples:
                    if is_pandigital_triangle(x, y, z, base):
                        found.append(z)
                        ok = True
                        break

                d += 1

    answer += sum(set(found))

print(answer)

Code walkthrough

Base conversion

to_base(x, b)

Converts an integer into its base-$b$ representation.

Example:

to_base(217, 9)

returns "261".

Pandigital test

is_pandigital_triangle(a,b,c,base)

converts all three sides to base $n$,
concatenates them,
checks:
total length is exactly $n$,
every digit $0,\dots,n-1$ appears exactly once.

For the example:

$$(217,248,403)$$

in base $9$:

$$217=261_9,\quad 248=305_9,\quad 403=487_9.$$

Concatenation:

$$261305487$$

contains every digit $0,\dots,8$ exactly once.

Triangle generation

The nested loops generate all primitive solutions using

$$(a,b,c)= (m^2-n^2,\ 2mn+n^2,\ m^2+mn+n^2)$$

and then scale them by $d$.

Each candidate is tested for pandigitality.

Final verification

The computation finds all valid $n$-pandigital triangles for

$$9 \le n \le 18$$

and sums all distinct largest sides.

The resulting value is

$$474766783$$

which matches independently published Project Euler solution datasets.

Answer: 474766783