题目61：找出唯一具有循环性质的6个四位数定形数集合的元素和

欧拉计划

Cyclical figurate numbers

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 , square , and pentagonal , 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.

题目：

三角形数，四角形数，五角形数，六角形数，七角形数和八角形数都是定形数，他们分别由以下公式产生：



三个四位数形成的有序集合: 8128, 2882, 8281,有三个有趣的性质：

1. 这个集合是循环的：每个数的后两位数是下一个数的前两位数，包括第三个和第一个的关系。
2. 三种定形数中的每一种都能被这三个数中的一个不同的数代表：三角形数 , 四角形数 , 和五角形数 。
3. 这是唯一具有以上性质的四位数的集合。

找出唯一的一个六个四位数的循环集合，使得从三角形数到八角形数中的每一种都能由该集合中的一个不同的数代表。

求这个集合中元素之和。

迷雾少年

Mark

jerryxjr1220

([8128, 2882, 8256, 5625, 2512, 1281], 28684)
Time:0.016s

import sys
import time
st = time.time()
def calc_numbers(start, end, proc):
    n = 1
    out = []
    while True:
        z = proc(n)
        if z >= start and z < end: out.append(z)
        if z >= end: return out
        n += 1

p3 = calc_numbers(1000, 10000, lambda n : n * (n + 1) / 2)
p4 = calc_numbers(1000, 10000, lambda n : n * n)
p5 = calc_numbers(1000, 10000, lambda n : n * (3 * n - 1) / 2)
p6 = calc_numbers(1000, 10000, lambda n : n * (2 * n - 1))
p7 = calc_numbers(1000, 10000, lambda n : n * (5 * n - 3) / 2)
p8 = calc_numbers(1000, 10000, lambda n : n * (3 * n - 2))


def find_loop(lists, start, end, found_numbers = []):
    if len(lists) == 1 and start * 100 + end in lists[0]:
        found_numbers.append(start * 100 + end)
        found_numbers.append(n)
        print (found_numbers, sum(found_numbers))
        ed = time.time()
        print ('Time:%.3fs'%(ed-st))
        sys.exit()
    
    for cur_list in lists:
        for c in cur_list:
            if c / 100 == start:
                lists_copy = lists[0:]
                lists_copy.remove(cur_list)
                find_loop(lists_copy, c % 100, end, found_numbers + [c])

for n in p8:
    find_loop([p3, p4, p5, p6, p7], n % 100, n / 100)

飘飞的白杨

import sys
from time import time

ttt = time()

def getlist(lam):
    '''获取x角形数的列表'''
    l = []
    for i in range(1, 1000):
        n = lam(i)
        if n < 1000: continue
        if n >= 10000: return l
        l.append(n)

def progrem61_2(numbers):
    if len(numbers) == 6 and numbers[-1] % 100 == numbers[0] // 100:
        print(numbers, sum(numbers), "\ntime:%.5fs"%(time()-ttt))
        sys.exit()
    for i in range(6):
        if flag[i]: continue
        flag[i] = True
        for j in p[i]:
            if j // 100 == numbers[-1] % 100:
                progrem61_2(numbers+[j])
        flag[i] = False

def progrem61_1():
    flag[-1] = True
    # 八角形数最少，从八角形数中选择第一个数
    for i in p8:
        progrem61_2([i])

p3 = getlist(lambda n: n * (n + 1) // 2)
p4 = getlist(lambda n: n * n)
p5 = getlist(lambda n: n * (3 * n - 1) // 2)
p6 = getlist(lambda n: n * (2 * n - 1))
p7 = getlist(lambda n: n * (5 * n - 3) // 2)
p8 = getlist(lambda n: n * (3 * n - 2))
p = [p3, p4, p5, p6, p7, p8]
flag = [False] * 6 # 标志数组，用于判断是否遍历过
progrem61_1()

guosl

/*
答案：28684
耗时：0.0000797秒
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <omp.h>
using namespace std;

vector<int> v[6];//v[0],...,v[5]分别是三角数，...，八角数
int x[6];//记录查找的结果
int p[6] = { 0,1,2,3,4,5 };//改变表的查找次序用

void GenTriangle(void)//生成三角数表
{
  int k = 1;
  while (true)
  {
    int n = k * (k + 1) / 2;
    if (n > 9999)
      break;
    else if (n >= 1000)
      v[0].push_back(n);
    ++k;
  }
}

void GenSquare(void)//生成四角形数表
{
  int k = 1;
  while (true)
  {
    int n = k * k;
    if (n > 9999)
      break;
    else if (n >= 1000)
      v[1].push_back(n);
    ++k;
  }
}

void GenPentagonal(void)//生成五角形数表
{
  int k = 1;
  while (true)
  {
    int n = k * (3 * k - 1) / 2;
    if (n > 9999)
      break;
    else if (n >= 1000)
      v[2].push_back(n);
    ++k;
  }
}

void GenHexagonal(void)//生成六角形数表
{
  int k = 1;
  while (true)
  {
    int n = k * (2 * k - 1);
    if (n > 9999)
      break;
    else if (n >= 1000)
      v[3].push_back(n);
    ++k;
  }
}

void GenHeptagonal(void)//生成七角形数表
{
  int k = 1;
  while (true)
  {
    int n = k * (5 * k - 3) / 2;
    if (n > 9999)
      break;
    else if (n >= 1000)
      v[4].push_back(n);
    ++k;
  }
}

void GenOctagonal(void)//生成八角形数表
{
  int k = 1;
  while (true)
  {
    int n = k * (3 * k - 2);
    if (n > 9999)
      break;
    else if (n >= 1000)
      v[5].push_back(n);
    ++k;
  }
}

bool dfs(int k, int f, int b)//深度搜索找匹配链
{
  if (k == 6)
    return (f == b);//检查是否可以和第一个数匹配
  int a1 = b * 100, a2 = a1 + 99;
  //找出下一个表中可能匹配的范围
  auto itr1 = lower_bound(v[p[k]].begin(), v[p[k]].end(), a1);
  auto itr2 = upper_bound(v[p[k]].begin(), v[p[k]].end(), a2);
  for (auto itr = itr1; itr != itr2; ++itr)//具体查找
  {
    //找到可能的匹配
    x[k] = *itr;//记录查找的结果
    if (dfs(k + 1, f, x[k] % 100))//往下找
      return true;
  }
  return false;
}

int main(void)
{
  double t = omp_get_wtime();
  //生成各种数的表
  GenTriangle();
  GenSquare();
  GenPentagonal();
  GenHexagonal();
  GenHeptagonal();
  GenOctagonal();
  do
  {
    bool bFind = false;
    for (int i = 0; i < (int)v[p[0]].size(); ++i)
    {
      int a0 = v[p[0]][i];
      int b = a0 % 100;//后二位
      int f = a0 / 100;//前二位
      x[0] = v[p[0]][i];//记录查找的结果
      bFind = dfs(1, f, b);
      if (bFind)
        break;
    }
    if (bFind)
      break;
  } while (next_permutation(p, p + 6));//改变一下表的查找次序
  int nSum = 0;
  for (int i = 0; i < 6; ++i)
    nSum += x[i];
  t = omp_get_wtime() - t;
  cout << nSum << endl << t << endl;
  return 0;
}

B1tetheDust

import time as t

start = t.perf_counter()


def divide_4_digit_num(a_num_list):
    new_list = []
    for each_num in a_num_list:
        new_list.append([str(each_num)[:2], str(each_num)[2:]])
    return new_list


def belong_to(a_num):
    range_list = [95, 163, 219, 267, 310, 350]
    for belong_i in range(6):
        if a_num <= range_list[belong_i]:
            return belong_i


def find_cyclic_num():
    Tri = [int(n * (n + 1) / 2) for n in range(45, 141)]  # length = 96
    Squ = [int(n ** 2) for n in range(32, 100)]  # length = 68
    Penta = [int(n * (3 * n - 1) / 2) for n in range(26, 82)]  # length = 56
    Hexa = [int(n * (2 * n - 1)) for n in range(23, 71)]  # length = 48
    Hept = [int(n * (5 * n - 3) / 2) for n in range(21, 64)]  # length = 43
    Octa = [int(n * (3 * n - 2)) for n in range(19, 59)]  # length = 40
    Tri_list, Squ_list = divide_4_digit_num(Tri), divide_4_digit_num(Squ)
    Penta_list, Hexa_list = divide_4_digit_num(Penta), divide_4_digit_num(Hexa)
    Hept_list, Octa_list = divide_4_digit_num(Hept), divide_4_digit_num(Octa)
    dict_list = {"Tri_list": Tri_list, "Squ_list": Squ_list, "Penta_list": Penta_list, "Hexa_list": Hexa_list,
                 "Hept_list": Hept_list, "Octa_list": Octa_list}
    total = []
    for lists in dict_list:
        total += dict_list[lists]
    len_total = len(total)
    for i00 in range(len_total):
        index_list = [belong_to(i00)]
        for i10 in range(len_total):
            if belong_to(i10) not in index_list and total[i00][1] == total[i10][0]:
                index_list = [belong_to(i00), belong_to(i10)]
                for i20 in range(len_total):
                    if belong_to(i20) not in index_list and total[i10][1] == total[i20][0]:
                        index_list = [belong_to(i00), belong_to(i10), belong_to(i20)]
                        for i30 in range(len_total):
                            if belong_to(i30) not in index_list and total[i20][1] == total[i30][0]:
                                index_list = [belong_to(i00), belong_to(i10), belong_to(i20), belong_to(i30)]
                                for i40 in range(len_total):
                                    if belong_to(i40) not in index_list and total[i30][1] == total[i40][0]:
                                        cur_num_list = [total[i00], total[i10], total[i20], total[i30], total[i40]]
                                        index_list = [belong_to(i00), belong_to(i10), belong_to(i20), belong_to(i30),
                                                      belong_to(i40)]
                                        for i50 in range(len_total):
                                            if belong_to(i50) not in index_list and \
                                                    total[i40][1] == total[i50][0] and \
                                                    total[i50][1] == cur_num_list[0][0]:
                                                cur_num_list.append(total[i50])
                                                return cur_num_list


res = find_cyclic_num()
print(res)
print(sum([int(i[0] + i[1]) for i in res]))
print("It costs %f s" % (t.perf_counter() - start))

[['25', '12'], ['12', '81'], ['81', '28'], ['28', '82'], ['82', '56'], ['56', '25']]
28684
It costs 0.530015 s