Problem #61 hard

Cyclical Figurate Numbers

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

| Triangle | | $P_{3,n}=n(n+1)/2$ | | $1, 3, 6, 10, 15, \dots$ | | Square | | $P_{4,n}=n^2$ | | $1, 4, 9, 16, 25, \dots$ | | Pentagonal | | $P_{5,n}=n(3n-1)/2$ | | $1, 5, 12, 22, 35, \dots$ | | Hexagonal | | $P_{6,n}=n(2n-1)$ | | $1, 6, 15, 28, 45, \dots$ | | Heptagonal | | $P_{7,n}=n(5n-3)/2$ | | $1, 7, 18, 34, 55, \dots$ | | Octagonal | | $P_{8,n}=n(3n-2)$ | | $1, 8, 21, 40, 65, \dots$ |

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

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).
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.
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.

View on Project Euler

Implementations

#include <iostream>
#include <vector>
#include <set>
#include <functional>

int cyclical_figurate_numbers() {
    std::vector<std::vector<int>> polys(9);

    auto gen_poly = [&](int type, auto formula) {
        for (int n = 1; ; ++n) {
            int num = formula(n);
            if (num >= 10000) break;
            if (num >= 1000) polys[type].push_back(num);
        }
    };

    gen_poly(3, [](int n){ return n*(n+1)/2; });
    gen_poly(4, [](int n){ return n*n; });
    gen_poly(5, [](int n){ return n*(3*n-1)/2; });
    gen_poly(6, [](int n){ return n*(2*n-1); });
    gen_poly(7, [](int n){ return n*(5*n-3)/2; });
    gen_poly(8, [](int n){ return n*(3*n-2); });

    std::vector<std::vector<std::vector<int>>> by_prefix(9);
    for (int t = 3; t <= 8; ++t) {
        by_prefix[t].resize(100);
        for (int num : polys[t]) {
            int prefix = num / 100;
            by_prefix[t][prefix].push_back(num);
        }
    }

    std::function<bool(std::vector<int>&, std::set<int>&, int)> find_cycle = [&](std::vector<int>& current, std::set<int>& used_types, int start_suffix) -> bool {
        if (current.size() == 6) {
            int last = current.back() % 100;
            int first = current[0] / 100;
            return last == first;
        }

        int next_prefix = current.back() % 100;
        for (int t = 3; t <= 8; ++t) {
            if (used_types.count(t)) continue;
            for (int num : by_prefix[t][next_prefix]) {
                current.push_back(num);
                used_types.insert(t);
                if (find_cycle(current, used_types, start_suffix)) return true;
                used_types.erase(t);
                current.pop_back();
            }
        }
        return false;
    };

    std::vector<int> current;
    std::set<int> used_types;

    for (int t = 3; t <= 8; ++t) {
        for (int num : polys[t]) {
            current = {num};
            used_types = {t};
            if (find_cycle(current, used_types, num / 100)) {
                int sum = 0;
                for (int n : current) sum += n;
                return sum;
            }
        }
    }

    return -1;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << cyclical_figurate_numbers() << std::endl;
}
#endif

View on GitHub

O(1) time complexity

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.util.*;

public class Solution061 implements Solution {
  public String solve() {
    List<List<Integer>> polys = new ArrayList<>();
    for (int i = 0; i < 9; i++) polys.add(new ArrayList<>());

    for (int t = 3; t <= 8; t++) {
      for (int n = 1; ; n++) {
        int num;
        switch (t) {
          case 3: num = n * (n + 1) / 2; break;
          case 4: num = n * n; break;
          case 5: num = n * (3 * n - 1) / 2; break;
          case 6: num = n * (2 * n - 1); break;
          case 7: num = n * (5 * n - 3) / 2; break;
          case 8: num = n * (3 * n - 2); break;
          default: num = 0;
        }
        if (num >= 10000) break;
        if (num >= 1000) polys.get(t).add(num);
      }
    }

    List<List<List<Integer>>> byPrefix = new ArrayList<>();
    for (int t = 3; t <= 8; t++) {
      List<List<Integer>> prefixes = new ArrayList<>();
      for (int p = 0; p < 100; p++) prefixes.add(new ArrayList<>());
      for (int num : polys.get(t)) {
        int prefix = num / 100;
        prefixes.get(prefix).add(num);
      }
      byPrefix.add(prefixes);
    }

    int[] result = new int[1];
    for (int t = 3; t <= 8; t++) {
      for (int num : polys.get(t)) {
        List<Integer> current = new ArrayList<>();
        current.add(num);
        Set<Integer> used = new HashSet<>();
        used.add(t);
        if (findCycle(current, used, byPrefix, num / 100, result)) {
          return String.valueOf(result[0]);
        }
      }
    }
    return "0";
  }

  private boolean findCycle(List<Integer> current, Set<Integer> used, List<List<List<Integer>>> byPrefix, int startPrefix, int[] result) {
    if (current.size() == 6) {
      int last = current.get(current.size() - 1) % 100;
      int first = current.get(0) / 100;
      if (last == first) {
        result[0] = current.stream().mapToInt(Integer::intValue).sum();
        return true;
      }
      return false;
    }
    int nextPrefix = current.get(current.size() - 1) % 100;
    for (int t = 3; t <= 8; t++) {
      if (used.contains(t)) continue;
      for (int num : byPrefix.get(t - 3).get(nextPrefix)) {
        current.add(num);
        used.add(t);
        if (findCycle(current, used, byPrefix, startPrefix, result)) return true;
        used.remove(t);
        current.remove(current.size() - 1);
      }
    }
    return false;
  }
}

View on GitHub

def gen_poly(typ):
    polys = []
    n = 1
    while True:
        if typ == 3:
            num = n * (n + 1) // 2
        elif typ == 4:
            num = n * n
        elif typ == 5:
            num = n * (3 * n - 1) // 2
        elif typ == 6:
            num = n * (2 * n - 1)
        elif typ == 7:
            num = n * (5 * n - 3) // 2
        elif typ == 8:
            num = n * (3 * n - 2)
        if num >= 10000:
            break
        if num >= 1000:
            polys.append(num)
        n += 1
    return polys

def solve():
    polys = [[] for _ in range(9)]
    for t in range(3, 9):
        polys[t] = gen_poly(t)

    by_prefix = [[[] for _ in range(100)] for _ in range(9)]
    for t in range(3, 9):
        for num in polys[t]:
            prefix = num // 100
            by_prefix[t][prefix].append(num)

    def find_cycle(current, used, start_prefix):
        if len(current) == 6:
            last = current[-1] % 100
            first = current[0] // 100
            if last == first:
                return sum(current)
            return -1
        next_prefix = current[-1] % 100
        for t in range(3, 9):
            if t in used:
                continue
            for num in by_prefix[t][next_prefix]:
                current.append(num)
                used.add(t)
                res = find_cycle(current, used, start_prefix)
                if res != -1:
                    return res
                used.remove(t)
                current.pop()
        return -1

    for t in range(3, 9):
        for num in polys[t]:
            current = [num]
            used = set([t])
            res = find_cycle(current, used, num // 100)
            if res != -1:
                return res
    return -1

View on GitHub

pub fn cyclical_figurate_numbers() -> u32 {
    let mut polys: Vec<Vec<u32>> = vec![vec![]; 9];

    let mut gen_poly = |typ: usize, formula: fn(usize) -> u32| {
        for n in 1.. {
            let num = formula(n);
            if num >= 10000 { break; }
            if num >= 1000 { polys[typ].push(num); }
        }
    };

    gen_poly(3, |n| (n * (n + 1) / 2) as u32);
    gen_poly(4, |n| (n * n) as u32);
    gen_poly(5, |n| (n * (3 * n - 1) / 2) as u32);
    gen_poly(6, |n| (n * (2 * n - 1)) as u32);
    gen_poly(7, |n| (n * (5 * n - 3) / 2) as u32);
    gen_poly(8, |n| (n * (3 * n - 2)) as u32);

    let mut by_prefix: Vec<Vec<Vec<u32>>> = vec![vec![vec![]; 100]; 9];
    for t in 3..=8 {
        for &num in &polys[t] {
            let prefix = (num / 100) as usize;
            by_prefix[t][prefix].push(num);
        }
    }

    fn find_cycle(current: &mut Vec<u32>, used: &mut std::collections::HashSet<usize>, by_prefix: &Vec<Vec<Vec<u32>>>) -> Option<u32> {
        if current.len() == 6 {
            let last = (current[current.len() - 1] % 100) as usize;
            let first = (current[0] / 100) as usize;
            if last == first {
                return Some(current.iter().sum());
            }
            return None;
        }
        let next_prefix = (current[current.len() - 1] % 100) as usize;
        for t in 3..=8 {
            if used.contains(&t) { continue; }
            for &num in &by_prefix[t][next_prefix] {
                current.push(num);
                used.insert(t);
                if let Some(sum) = find_cycle(current, used, by_prefix) {
                    return Some(sum);
                }
                used.remove(&t);
                current.pop();
            }
        }
        None
    }

    for t in 3..=8 {
        for &num in &polys[t] {
            let mut current = vec![num];
            let mut used = std::collections::HashSet::new();
            used.insert(t);
            if let Some(sum) = find_cycle(&mut current, &mut used, &by_prefix) {
                return sum;
            }
        }
    }
    0
}

View on GitHub

#include <iostream>
#include <vector>
#include <set>
#include <functional>

int cyclical_figurate_numbers() {
    std::vector<std::vector<int>> polys(9);

    auto gen_poly = [&](int type, auto formula) {
        for (int n = 1; ; ++n) {
            int num = formula(n);
            if (num >= 10000) break;
            if (num >= 1000) polys[type].push_back(num);
        }
    };

    gen_poly(3, [](int n){ return n*(n+1)/2; });
    gen_poly(4, [](int n){ return n*n; });
    gen_poly(5, [](int n){ return n*(3*n-1)/2; });
    gen_poly(6, [](int n){ return n*(2*n-1); });
    gen_poly(7, [](int n){ return n*(5*n-3)/2; });
    gen_poly(8, [](int n){ return n*(3*n-2); });

    std::vector<std::vector<std::vector<int>>> by_prefix(9);
    for (int t = 3; t <= 8; ++t) {
        by_prefix[t].resize(100);
        for (int num : polys[t]) {
            int prefix = num / 100;
            by_prefix[t][prefix].push_back(num);
        }
    }

    std::function<bool(std::vector<int>&, std::set<int>&, int)> find_cycle = [&](std::vector<int>& current, std::set<int>& used_types, int start_suffix) -> bool {
        if (current.size() == 6) {
            int last = current.back() % 100;
            int first = current[0] / 100;
            return last == first;
        }

        int next_prefix = current.back() % 100;
        for (int t = 3; t <= 8; ++t) {
            if (used_types.count(t)) continue;
            for (int num : by_prefix[t][next_prefix]) {
                current.push_back(num);
                used_types.insert(t);
                if (find_cycle(current, used_types, start_suffix)) return true;
                used_types.erase(t);
                current.pop_back();
            }
        }
        return false;
    };

    std::vector<int> current;
    std::set<int> used_types;

    for (int t = 3; t <= 8; ++t) {
        for (int num : polys[t]) {
            current = {num};
            used_types = {t};
            if (find_cycle(current, used_types, num / 100)) {
                int sum = 0;
                for (int n : current) sum += n;
                return sum;
            }
        }
    }

    return -1;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << cyclical_figurate_numbers() << std::endl;
}
#endif

View on GitHub

O(1) time complexity

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.util.*;

public class Solution061 implements Solution {
  public String solve() {
    List<List<Integer>> polys = new ArrayList<>();
    for (int i = 0; i < 9; i++) polys.add(new ArrayList<>());

    for (int t = 3; t <= 8; t++) {
      for (int n = 1; ; n++) {
        int num;
        switch (t) {
          case 3: num = n * (n + 1) / 2; break;
          case 4: num = n * n; break;
          case 5: num = n * (3 * n - 1) / 2; break;
          case 6: num = n * (2 * n - 1); break;
          case 7: num = n * (5 * n - 3) / 2; break;
          case 8: num = n * (3 * n - 2); break;
          default: num = 0;
        }
        if (num >= 10000) break;
        if (num >= 1000) polys.get(t).add(num);
      }
    }

    List<List<List<Integer>>> byPrefix = new ArrayList<>();
    for (int t = 3; t <= 8; t++) {
      List<List<Integer>> prefixes = new ArrayList<>();
      for (int p = 0; p < 100; p++) prefixes.add(new ArrayList<>());
      for (int num : polys.get(t)) {
        int prefix = num / 100;
        prefixes.get(prefix).add(num);
      }
      byPrefix.add(prefixes);
    }

    int[] result = new int[1];
    for (int t = 3; t <= 8; t++) {
      for (int num : polys.get(t)) {
        List<Integer> current = new ArrayList<>();
        current.add(num);
        Set<Integer> used = new HashSet<>();
        used.add(t);
        if (findCycle(current, used, byPrefix, num / 100, result)) {
          return String.valueOf(result[0]);
        }
      }
    }
    return "0";
  }

  private boolean findCycle(List<Integer> current, Set<Integer> used, List<List<List<Integer>>> byPrefix, int startPrefix, int[] result) {
    if (current.size() == 6) {
      int last = current.get(current.size() - 1) % 100;
      int first = current.get(0) / 100;
      if (last == first) {
        result[0] = current.stream().mapToInt(Integer::intValue).sum();
        return true;
      }
      return false;
    }
    int nextPrefix = current.get(current.size() - 1) % 100;
    for (int t = 3; t <= 8; t++) {
      if (used.contains(t)) continue;
      for (int num : byPrefix.get(t - 3).get(nextPrefix)) {
        current.add(num);
        used.add(t);
        if (findCycle(current, used, byPrefix, startPrefix, result)) return true;
        used.remove(t);
        current.remove(current.size() - 1);
      }
    }
    return false;
  }
}

View on GitHub

function genPoly(type) {
  const polys = [];
  for (let n = 1; ; n++) {
    let num;
    switch (type) {
      case 3: num = n * (n + 1) / 2; break;
      case 4: num = n * n; break;
      case 5: num = n * (3 * n - 1) / 2; break;
      case 6: num = n * (2 * n - 1); break;
      case 7: num = n * (5 * n - 3) / 2; break;
      case 8: num = n * (3 * n - 2); break;
    }
    if (num >= 10000) break;
    if (num >= 1000) polys.push(num);
  }
  return polys;
}

function cyclicalFigurateNumbers() {
  const polys = [];
  for (let t = 3; t <= 8; t++) {
    polys[t] = genPoly(t);
  }

  const byPrefix = [];
  for (let t = 3; t <= 8; t++) {
    byPrefix[t] = Array(100).fill().map(() => []);
    for (const num of polys[t]) {
      const prefix = Math.floor(num / 100);
      byPrefix[t][prefix].push(num);
    }
  }

  function findCycle(current, used, startPrefix) {
    if (current.length === 6) {
      const last = current[current.length - 1] % 100;
      const first = Math.floor(current[0] / 100);
      if (last === first) {
        return current.reduce((a, b) => a + b, 0);
      }
      return -1;
    }
    const nextPrefix = current[current.length - 1] % 100;
    for (let t = 3; t <= 8; t++) {
      if (used.has(t)) continue;
      for (const num of byPrefix[t][nextPrefix]) {
        current.push(num);
        used.add(t);
        const res = findCycle(current, used, startPrefix);
        if (res !== -1) return res;
        used.delete(t);
        current.pop();
      }
    }
    return -1;
  }

  for (let t = 3; t <= 8; t++) {
    for (const num of polys[t]) {
      const current = [num];
      const used = new Set([t]);
      const res = findCycle(current, used, Math.floor(num / 100));
      if (res !== -1) return res;
    }
  }
  return -1;
}

module.exports = {
  answer: () => cyclicalFigurateNumbers()
};

View on GitHub

def gen_poly(typ):
    polys = []
    n = 1
    while True:
        if typ == 3:
            num = n * (n + 1) // 2
        elif typ == 4:
            num = n * n
        elif typ == 5:
            num = n * (3 * n - 1) // 2
        elif typ == 6:
            num = n * (2 * n - 1)
        elif typ == 7:
            num = n * (5 * n - 3) // 2
        elif typ == 8:
            num = n * (3 * n - 2)
        if num >= 10000:
            break
        if num >= 1000:
            polys.append(num)
        n += 1
    return polys

def solve():
    polys = [[] for _ in range(9)]
    for t in range(3, 9):
        polys[t] = gen_poly(t)

    by_prefix = [[[] for _ in range(100)] for _ in range(9)]
    for t in range(3, 9):
        for num in polys[t]:
            prefix = num // 100
            by_prefix[t][prefix].append(num)

    def find_cycle(current, used, start_prefix):
        if len(current) == 6:
            last = current[-1] % 100
            first = current[0] // 100
            if last == first:
                return sum(current)
            return -1
        next_prefix = current[-1] % 100
        for t in range(3, 9):
            if t in used:
                continue
            for num in by_prefix[t][next_prefix]:
                current.append(num)
                used.add(t)
                res = find_cycle(current, used, start_prefix)
                if res != -1:
                    return res
                used.remove(t)
                current.pop()
        return -1

    for t in range(3, 9):
        for num in polys[t]:
            current = [num]
            used = set([t])
            res = find_cycle(current, used, num // 100)
            if res != -1:
                return res
    return -1

View on GitHub

package main

import "fmt"

func genPoly(typ int) []int {
  polys := []int{}
  for n := 1; ; n++ {
    var num int
    switch typ {
    case 3:
      num = n * (n + 1) / 2
    case 4:
      num = n * n
    case 5:
      num = n * (3*n - 1) / 2
    case 6:
      num = n * (2*n - 1)
    case 7:
      num = n * (5*n - 3) / 2
    case 8:
      num = n * (3*n - 2)
    }
    if num >= 10000 {
      break
    }
    if num >= 1000 {
      polys = append(polys, num)
    }
  }
  return polys
}

func cyclicalFigurateNumbers() int {
  polys := make([][]int, 9)
  for t := 3; t <= 8; t++ {
    polys[t] = genPoly(t)
  }

  byPrefix := make([][][]int, 9)
  for t := 3; t <= 8; t++ {
    byPrefix[t] = make([][]int, 100)
    for _, num := range polys[t] {
      prefix := num / 100
      byPrefix[t][prefix] = append(byPrefix[t][prefix], num)
    }
  }

  var findCycle func([]int, map[int]bool, int) int
  findCycle = func(current []int, used map[int]bool, startPrefix int) int {
    if len(current) == 6 {
      last := current[len(current)-1] % 100
      first := current[0] / 100
      if last == first {
        sum := 0
        for _, n := range current {
          sum += n
        }
        return sum
      }
      return -1
    }
    nextPrefix := current[len(current)-1] % 100
    for t := 3; t <= 8; t++ {
      if used[t] {
        continue
      }
      for _, num := range byPrefix[t][nextPrefix] {
        newCurrent := append([]int(nil), current...)
      newCurrent = append(newCurrent, num)
      newUsed := make(map[int]bool)
      for k, v := range used {
        newUsed[k] = v
      }
      newUsed[t] = true
      if res := findCycle(newCurrent, newUsed, startPrefix); res != -1 {
        return res
      }
    }
  }
  return -1
  }

  for t := 3; t <= 8; t++ {
    for _, num := range polys[t] {
      current := []int{num}
      used := map[int]bool{t: true}
      if res := findCycle(current, used, num/100); res != -1 {
        return res
      }
  }
  }
  return -1
}

func main() {
  fmt.Println(cyclicalFigurateNumbers())
}

View on GitHub

pub fn cyclical_figurate_numbers() -> u32 {
    let mut polys: Vec<Vec<u32>> = vec![vec![]; 9];

    let mut gen_poly = |typ: usize, formula: fn(usize) -> u32| {
        for n in 1.. {
            let num = formula(n);
            if num >= 10000 { break; }
            if num >= 1000 { polys[typ].push(num); }
        }
    };

    gen_poly(3, |n| (n * (n + 1) / 2) as u32);
    gen_poly(4, |n| (n * n) as u32);
    gen_poly(5, |n| (n * (3 * n - 1) / 2) as u32);
    gen_poly(6, |n| (n * (2 * n - 1)) as u32);
    gen_poly(7, |n| (n * (5 * n - 3) / 2) as u32);
    gen_poly(8, |n| (n * (3 * n - 2)) as u32);

    let mut by_prefix: Vec<Vec<Vec<u32>>> = vec![vec![vec![]; 100]; 9];
    for t in 3..=8 {
        for &num in &polys[t] {
            let prefix = (num / 100) as usize;
            by_prefix[t][prefix].push(num);
        }
    }

    fn find_cycle(current: &mut Vec<u32>, used: &mut std::collections::HashSet<usize>, by_prefix: &Vec<Vec<Vec<u32>>>) -> Option<u32> {
        if current.len() == 6 {
            let last = (current[current.len() - 1] % 100) as usize;
            let first = (current[0] / 100) as usize;
            if last == first {
                return Some(current.iter().sum());
            }
            return None;
        }
        let next_prefix = (current[current.len() - 1] % 100) as usize;
        for t in 3..=8 {
            if used.contains(&t) { continue; }
            for &num in &by_prefix[t][next_prefix] {
                current.push(num);
                used.insert(t);
                if let Some(sum) = find_cycle(current, used, by_prefix) {
                    return Some(sum);
                }
                used.remove(&t);
                current.pop();
            }
        }
        None
    }

    for t in 3..=8 {
        for &num in &polys[t] {
            let mut current = vec![num];
            let mut used = std::collections::HashSet::new();
            used.insert(t);
            if let Some(sum) = find_cycle(&mut current, &mut used, &by_prefix) {
                return sum;
            }
        }
    }
    0
}

View on GitHub

Solution Notes

Mathematical Background

This problem involves finding cyclic sets of figurate numbers where each type is represented exactly once, and the numbers form a cycle based on their last two and first two digits.

Algorithm Analysis

Generate all 4-digit polygonal numbers for each type, then use backtracking to find a cycle of six numbers, each of different types, where the last two digits of one match the first two of the next.

Performance Analysis

Time Complexity: O(1) - fixed small search space
Space Complexity: O(1) - small data structures
Execution Time: Fast, backtracking finds solution quickly
Scalability: Not applicable, fixed problem size

Key Insights

Prefix maps enable efficient lookup of numbers with matching prefixes
Backtracking with early termination finds the unique solution
The solution sum is 28684

Educational Value

This problem teaches:

Combinatorial search and backtracking
Data structure optimization for prefix matching
Working with polygonal number sequences
Cycle detection in permutations