Problem 61 | Project Euler |

[sx349]

https://pe-cn.github.io/61/

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

[TerenceG-cn]

import math
import copy

# 三边形数
def is_triangle(n):
    return math.sqrt(1 + 8 * n) % 2 == 1

# 四边形数
def is_square(num):
    low = 1
    high = num
    while low < high:
        mid = (low + high) // 2
        if mid * mid == num:
            return True
        elif mid * mid < num:
            low = mid + 1
        else:
            high = mid - 1
    return low * low == num

# 五边形数
def is_pentagonal(n):
    # return math.sqrt(1 + 24 * n) % 6 == 5 or math.sqrt(1+24*n)%6==1 广义五边形数
    return math.sqrt(1 + 24 * n) % 6 == 5

# 六边形数
def is_hexagonal(n):
    return math.sqrt(1 + 8 * n) % 4 == 1

# 七边形数
def is_heptagonal(n):
    return math.sqrt(9 + 40 * n) % 10 == 7

# 八边形数
def is_octagonal(n):
    return math.sqrt(1 + 3 * n) % 3 == 2

figurate_numbers_dict = {
    'triange': [],
    'square': [],
    'pentagonal': [],
    'hexagonal': [],
    'heptagonal': [],
    'octagonal': []
}
for num in range(1000, 10000):
    if is_triangle(num): figurate_numbers_dict['triange'].append(num)
    if is_square(num): figurate_numbers_dict['square'].append(num)
    if is_pentagonal(num): figurate_numbers_dict['pentagonal'].append(num)
    if is_hexagonal(num): figurate_numbers_dict['hexagonal'].append(num)
    if is_heptagonal(num): figurate_numbers_dict['heptagonal'].append(num)
    if is_octagonal(num): figurate_numbers_dict['octagonal'].append(num)

def rec_fun(tar_num, tar_polygon, fig_nums, res):
    res.append(tar_num)
    del fig_nums[tar_polygon]
    if fig_nums == {}:
        if res[0] // 100 == res[-1] % 100:
            print(res)
            print(sum(res))
        else:
            del res[-1]
    else:
        for polygon in fig_nums:
            for n in fig_nums[polygon]:
                if n // 100 == tar_num % 100:
                    new_fig_nums = copy.deepcopy(fig_nums)
                    rec_fun(n, polygon, new_fig_nums, res)
        del res[-1]

fig_nums = copy.deepcopy(figurate_numbers_dict)
for n in figurate_numbers_dict['triange']:
    rec_fun(n, 'triange', fig_nums, res=[])
    fig_nums['triange'] = figurate_numbers_dict['triange']

[p-gp]

/*e61.c--Cyclical figurate numbers*/
#include <stdio.h>
#include <stdlib.h>

int num[6][100];
int x1, x2;
int var[6];
int count[6];
//int srt;

int f1(int x);

int main()
{
    for (int i = 0; i <= 5; ++i) {
        int x = 0, j = 1;
        switch (i) {
            case 0: 
                while (x < 10000) {
                    x = j * (j + 1) / 2;
                    if (x >= 1010 && x < 10000)
                        num[i][++num[i][0]] = x;
                    ++j;
                }
                break;
            case 1:
                while (x < 10000) {
                    x = j * j;
                    if (x >= 1010 && x < 10000)
                        num[i][++num[i][0]] = x;
                    ++j;
                }
                break;
            case 2:
                while (x < 10000) {
                    x = j * (3 * j - 1) / 2;
                    if (x >= 1010 && x < 10000)
                        num[i][++num[i][0]] = x;
                    ++j;
                }
                break;
            case 3:
                while (x < 10000) {
                    x = j * (2 * j - 1);
                    if (x >= 1010 && x < 10000)
                        num[i][++num[i][0]] = x;
                    ++j;
                }
                break;
            case 4:
                while (x < 10000) {
                    x = j * (5 * j - 3) / 2;
                    if (x >= 1010 && x < 10000)
                        num[i][++num[i][0]] = x;
                    ++j;
                }
                break;
            case 5:
                while (x < 10000) {
                    x = j * (3 * j -2);
                    if (x >= 1010 && x < 10000)
                        num[i][++num[i][0]] = x;
                    ++j;
                }
            //break;
        }
    }

    for (int i = 1; i <= num[0][0]; ++i) {
        x1 = num[0][i] / 100, x2 = num[0][i] % 100;
        f1(x2);
    }

    return 0;
}

int f1(int x)
{
    if (count[0] == 5) {
        if (x == x1) {
            int sum = x1 * 100 + x2;
            //srt = srt * 10 + 0;
            for (int i = 1; i <= 5; ++i) {
                printf("%d ", var[i]);
                sum += var[i];
            }
            printf("%d\n", x1 * 100 + x2);
            printf("%d\n", sum);                
            exit(0);
        }
    }
    for (int i = 1; i <= 5; ++i) {
        if (!count[i]) {
            count[i] = 1;
            count[0]++;
            //srt = srt * 10 + i;
            for (int j = 1; j <= num[i][0]; ++j) {
                if (x == num[i][j] / 100) {
                    var[i] = num[i][j];
                    f1(num[i][j] % 100);
                }
            }
            count[i] = 0;
            count[0]--;
            //srt /= 10;
        }
    }
    return 0;
}

............................................................................................................................

5625 2882 8128 2512 1281 8256

28684

[Jin-bao]

Python

def P3n() -> list:
  PnList = []
  for n in range(45, 141):
    Pn = int(n*(n+1) / 2)
    if (Pnr:=Pn%100) > 9:
      PnList += [[Pn//100, Pnr]]
  return PnList

def P4n() -> list:
  PnList = []
  for n in range(32, 100):
    Pn = n**2
    if (Pnr:=Pn%100) > 9:
      PnList += [[Pn//100, Pnr]]
  return PnList

def P5n() -> list:
  PnList = []
  for n in range(26, 82):
    Pn = int(n*(3*n-1) / 2)
    if (Pnr:=Pn%100) > 9:
      PnList += [[Pn//100, Pnr]]
  return PnList

def P6n() -> list:
  PnList = []
  for n in range(23, 71):
    Pn = n*(2*n-1)
    if (Pnr:=Pn%100) > 9:
      PnList += [[Pn//100, Pnr]]
  return PnList

def P7n() -> list:
  PnList = []
  for n in range(21, 64):
    Pn = int(n*(5*n-3) / 2)
    if (Pnr:=Pn%100) > 9:
      PnList += [[Pn//100, Pnr]]
  return PnList

def P8n() -> list:
  PnList = []
  for n in range(19, 59):
    Pn = n*(3*n-2)
    if (Pnr:=Pn%100) > 9:
      PnList += [[Pn//100, Pnr]]
  return PnList

from itertools import permutations

PnList = [P3n(), P4n(), P5n(), P6n(), P7n(), P8n()]
script = list(permutations([0,1,2,3,4,5], 6))

for sitem in script:
  leftChain = []
  for item1 in PnList[sitem[0]]:
    for item2 in PnList[sitem[1]]:
      for item3 in PnList[sitem[2]]:
        if item1[1]==item2[0] and item2[1]==item3[0]:
          leftChain += [[item1, item2, item3]]
  righChain = []
  for item1 in PnList[sitem[3]]:
    for item2 in PnList[sitem[4]]:
      for item3 in PnList[sitem[5]]:
        if item1[1]==item2[0] and item2[1]==item3[0]:
          righChain += [[item1, item2, item3]]
  cycleList = []
  for item1 in leftChain:
    for item2 in righChain:
      if item1[2][1]==item2[0][0] and item1[0][0]==item2[2][1]:
        cycleList = [
          item1[0][0]*100+item1[0][1],
          item1[1][0]*100+item1[1][1],
          item1[2][0]*100+item1[2][1],
          item2[0][0]*100+item2[0][1],
          item2[1][0]*100+item2[1][1],
          item2[2][0]*100+item2[2][1]
        ]
        print(sum(cycleList))
        exit(0)