Project Euler Problem 61 Statement

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

The ordered set of three $4$-digit numbers: $8128$, $2882$, $8281$, has three interesting properties.

1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
2. Each polygonal type: triangle ($P_{3,127}=8128$), square ($P_{4,91}=8281$), and pentagonal ($P_{5,44}=2882$), is represented by a different number in the set.
3. This is the only set of $4$-digit numbers with this property.

Find the sum of the only ordered set of six cyclic $4$-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Solution

Project Euler Problem 61 want's us to find a set of six 4-digit numbers where each number is a different type of polygonal number (from triangle to octagonal), and the numbers form a cyclic sequence. Specifically:

• Each number is a 4-digit polygonal number.
• Each number is a different polygonal type (triangle, square, pentagonal, hexagonal, heptagonal, octagonal).
• The last two digits of each number are the first two digits of the next number.
• The sequence forms a closed cycle (the last number connects back to the first).

1. Initialization

# Set to store valid cycle sums
qx = set()

qx: A set to store the sums of valid cyclic sequences found.

2. Polygonal Number Generator

# Lambda to generate polygonal numbers for n in the range
# t is the polygonal type (3 to 8).
# Formula: P(t, n) = ((t - 2)*n2 + (4 - t)*n) / 2
pn = lambda n: [(t, ((t - 2) * n**2 + (4 - t) * n) // 2) for t in range(3, 9)]

pn: A lambda function that generates polygonal numbers.

• t ranges from 3 to 8, representing different polygonal types:
  • 3: Triangle
  • 4: Square
  • 5: Pentagonal
  • 6: Hexagonal
  • 7: Heptagonal
  • 8: Octagonal
• Formula: Computes the \( n \)-th polygonal number of type \( t \).

3. Recursive Path Finder

def next_path(types, data):
    """
    Recursively search for a cycle using the 'ds' adjacency info.
    - types: polygonal types used so far
    - data: the actual 4-digit numbers in the path
    """
    global qx, ds

    # Base case: Check if a complete cycle is formed
    if len(types) == qn and data[0] // 100 == data[-1] % 100 and len(set(data)) == len(data):
        qx.add(sum(data))
    else:
        # Extend the path with valid next (type, number) pairs
        [next_path(types + [t], data + [n])
         for t, n in ds.get((types[-1], data[-1]), [])
         if t not in types and n not in data]

next_path: A recursive function to build potential cyclic sequences.

• Parameters:
  • types: List of polygonal types used so far.
  • data: List of 4-digit numbers forming the current path.
• Base Case:
  • len(types) == qn: Checks if the desired number of polygonal types has been used.
  • data[0] // 100 == data[-1] % 100: Ensures the cycle wraps around correctly (last two digits of the last number match the first two digits of the first number).
  • len(set(data)) == len(data): Ensures all numbers in the cycle are unique.
  • If all conditions are met, the sum of the cycle is added to qx.
• Recursive Case:
  • Extends the current path by exploring all possible next numbers that:
    • Match the cyclic condition (last two digits of the current number match the first two digits of the next number).
    • Use a new polygonal type.
    • Are unique in the current path.

4. Generating Polygonal Numbers

# p will hold all (type, number) pairs, starting with n=19 (since smaller n typically produce <1000)
p, n, qn = [], 19, int(input())        # qn is how many polygonal types we need in the cycle
q = list(map(int, input().split()))    # The polygonal types we actually care about (e.g., 3,4,5,6...)

• p: List to store tuples of polygonal type and number.
• n: Starting index for generating polygonal numbers (starts at 19 to ensure 4-digit numbers).
• qn: Number of polygonal types to include in the cycle (typically 6 for Problem 61).
• q: List of polygonal types to consider, input by the user (e.g., [3,4,5,6,7,8]).

5. Collecting 4-Digit Polygonal Numbers

# Collect all 4-digit polygonal numbers for each relevant type in q.
while n <= 141:  # 141 is a safe upper bound for generating 4-digit polygonal numbers
    p += [
        (t, d) for t, d in pn(n)
        if t in q and 1000 <= d <= 9999 and d % 100 > 9
    ]
    n += 1

Loop from n=19 to n=141: Generates polygonal numbers for each type in q.

• pn(n): Generates the \( n \)-th polygonal number for each type.
• Filters:
  • t in q: Only include types specified by the user.
  • 1000 <= d <= 9999: Ensure the number is 4-digit.
  • d % 100 > 9: Ensures the last two digits are at least 10 (to avoid numbers like xx00, which can't form a valid next number with two digits).

6. Building the Adjacency Dictionary

# Build a "graph" (dictionary ds) where each key is (type, number),
# and the value is a list of (next_type, next_number) that connect
# by the last two digits == first two digits criterion.
ds = {}
for t1, d1 in p:
    for t2, d2 in p:
        if t1 != t2 and d1 % 100 == d2 // 100:
            ds[(t1, d1)] = ds.get((t1, d1), []) + [(t2, d2)]

ds: A dictionary representing the adjacency list of a graph.

• Keys: Tuples (t1, d1) representing the current polygonal type and number.
• Values: Lists of tuples (t2, d2) representing possible next polygonal type and number that satisfy the cyclic condition.

• For each pair of polygonal numbers (t1, d1) and (t2, d2):
  • t1 != t2: Ensure different polygonal types.
  • d1 % 100 == d2 // 100: The last two digits of d1 match the first two digits of d2.
  • If both conditions are met, (t2, d2) is added to the adjacency list for (t1, d1).

7. Initiating the Recursive Search

# Start a path from each possible (type, number) in ds
[next_path([t], [d]) for t, d in ds]

List Comprehension: Iterates over each (t, d) in ds and starts the recursive search with:

• [t]: Initial list of polygonal types used.
• [d]: Initial list of numbers in the path.

8. Outputting the Results

# Print all possible cycle sums in ascending order
[print(x) for x in sorted(qx)]

Sorting and Printing: Sorts the valid cycle sums stored in qx and prints each sum in ascending order.

How the Code Solves the Problem

1. Generating Polygonal Numbers:

   The code first generates all relevant 4-digit polygonal numbers for the specified types (q). It ensures that each number is valid (4-digit and has meaningful last two digits).

2. Building Connections:

   It constructs an adjacency dictionary (ds) where each polygonal number points to potential successors that satisfy the cyclic condition (last two digits match the first two of the next number) and are of different polygonal types.

3. Recursive Search for Cycles:

   Using the next_path function, the code recursively explores all possible paths through the adjacency dictionary, ensuring that:

   • Each polygonal type is used exactly once.
   • Each number in the cycle is unique.
   • The sequence forms a closed cycle.

4. Collecting and Outputting Results:

   Valid cycles that meet all criteria have their sums added to the qx set. Finally, the code sorts and prints these sums, providing the solution to the problem.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 61

HackerRank Project Euler 61: You are given a set of numbers $N\in {3,4,5,6,7,8}$ find the sum of $4-digit$ numbers from $N-gonal$ sets that respect the above property. If there are multiple such numbers print their sums in sorted order..