# Problem 63 Powerful digit counts

## Problem 63: Powerful digit counts

https://projecteuler.net/problem=63

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

## 分析

16807 是 5 位数，也是 7 的 5 次方
134217728 是 9 位数，也是 8 的 9 次方

## 方法

### Python

cnt = 0
for x in range(1, 10) :
n = 1
while True:
if 10**(n-1) > x**n: break
if len(str(x**n)) == n:
#print(x,n, x**n)
cnt += 1
n += 1
print(cnt)

### Golang

package main

import (
"fmt"
"math/big"
)

func main() {
cnt := 0
for x := int64(1); x < 10; x++ {
for n := 1; ; n++ {
bx := big.NewInt(x)
pow := big.NewInt(x) // x^n
for i := 1; i <= n-1; i++ {
pow.Mul(pow, bx)
}

b10 := big.NewInt(10)
pow10 := big.NewInt(1) // 10^(n-1)
for i := 1; i <= n-1; i++ {
pow10.Mul(pow10, b10)
}

if pow10.Cmp(pow) > 0 {
break
}

if len(pow.String()) == n {
fmt.Println(x, n, pow.String())
cnt++
}
}
}

fmt.Println(cnt)
}


### CPP

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 123 => [1,2,3]
// n >= 0
std::vector<char> int2vector(int n)
{
std::vector<char> digits;
if(n == 0){
digits.push_back('0');
return digits;
}

while(n > 0){
digits.push_back( n % 10 + '0' );
n /= 10;
}

std::reverse(digits.begin(), digits.end());

return digits;
}

/***********************************************************
* a+b
* a >= 0
* b >= 0
* return a+b
************************************************************/
std::vector<char> add(const std::vector<char>& a, const std::vector<char>& b)
{
// 存放和（逆序）
std::vector<char> sum;

// 从低位到高位，依次相加
int i = 0, j = 0, acc = 0; // acc 进位
for(i = a.size()-1, j = b.size()-1; i >= 0 && j >= 0; i--, j --){
int v = (int) (a[i] - '0') + (int) (b[j] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// a.size > b.size, b已经加完，a剩余
for(; i >= 0; i--){
int v = (int) (a[i] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// a.size < b.size, a已经加完，b剩余
for(; j >= 0; j--){
int v = (int) (b[j] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// 补上 acc
if( acc > 0){
sum.push_back( (char) ( acc + '0' ) );
}

// 对sum进行逆序
std::reverse(sum.begin(), sum.end());
return sum;
}

/***********************************************************
* a*b
* a >= 0
* b 是 0~9 之间的整数
* return a*b
************************************************************/
std::vector<char> mul(const std::vector<char>& a, int b)
{
// 存放乘积
std::vector<char> product;

if(b == 0){
product.push_back('0');
return std::move(product);
}

// 将乘法转换为加法
for(int i = 0; i < a.size(); i++){ // product = a
product.push_back(a[i]);
}

for(int i = 0; i < b-1; i ++){  //  累加 b-1 次 a
product = add(product, a);
}

return std::move(product);
}

/***********************************************************
* a*b
* a >= 0
* b >= 0
* return a*b
************************************************************/
std::vector<char> mul(const std::vector<char>& a, const std::vector<char>& b)
{
// 存放乘积
std::vector<char> product;
std::vector<char> a1;
for(int i = 0; i< a.size(); i ++) a1.push_back(a[i]);

// 将乘法转换为加法
for(int i = b.size() - 1; i >= 0; i--){
std::vector<char> p = mul(a1, (int)(b[i] - '0') );
product = add(product, p);
a1.push_back('0'); // a1 *= 10，因为b的位数每高一位，a1 要乘以 10
}

return product;
}

// x^n
std::vector<char> pow(int x, int n)
{
if(n == 0){
std::vector<char> v;
v.push_back('1');
return v;
}

std::vector<char> vx = int2vector(x);
std::vector<char> product = int2vector(x);

for(int i = 1; i <= n-1; i++){
product = mul(product, vx);
}

return product;
}

// a>b: return 1
// a==b: return 0
// a<b: return -1
int compare(const std::vector<char>& a, const std::vector<char>& b)
{
if(a.size() > b.size()) return 1;
if(a.size() < b.size()) return -1;

for(int i = a.size()-1; i >= 0; i--){
if(a[i] > b[i]) return 1;
if(a[i] < b[i]) return -1;
}

return 0;
}

std::string v2string(const std::vector<char>& v)
{
std::string s;
for(int i = 0; i<v.size(); i++){
s.push_back(v[i]);
}
return s;
}

int main()
{
int cnt = 0;
for (int x = 1; x < 10; x++ ){

for (int n = 1;;n++){
std::vector<char> powx = pow(x, n);
std::vector<char> pow10 = pow(10, n-1);
if (compare(pow10, powx) > 0) {
break;
}

if (powx.size() == n) {
printf("%d, %d, %s\n", x,n, v2string(powx).c_str());
cnt += 1;
}
}

}

printf("%d\n", cnt);
return 0;

}

## 答案

49

1^1, 1
2^1, 2
3^1, 3
4^1, 4
4^2, 16
5^1, 5
5^2, 25
5^3, 125
6^1, 6
6^2, 36
6^3, 216
6^4, 1296
7^1, 7
7^2, 49
7^3, 343
7^4, 2401
7^5, 16807
7^6, 117649
8^1, 8
8^2, 64
8^3, 512
8^4, 4096
8^5, 32768
8^6, 262144
8^7, 2097152
8^8, 16777216
8^9, 134217728
8^10, 1073741824
9^1, 9
9^2, 81
9^3, 729
9^4, 6561
9^5, 59049
9^6, 531441
9^7, 4782969
9^8, 43046721
9^9, 387420489
9^10, 3486784401
9^11, 31381059609
9^12, 282429536481
9^13, 2541865828329
9^14, 22876792454961
9^15, 205891132094649
9^16, 1853020188851841
9^17, 16677181699666569
9^18, 150094635296999121
9^19, 1350851717672992089
9^20, 12157665459056928801
9^21, 109418989131512359209

# Problem 62 Cubic permutations

## Problem 62: Cubic permutations

https://projecteuler.net/problem=62

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

## 分析

41063625（345 的立方）可以排列（即数字重组）出 56623104 (384的立方) 和 66430125 (405的立方)

## 方法 按位数遍历

(1) 先将所有数，分解成数字，然后将数字从小到大排序重组，得到新的一组字符串。比如 41063625 转换成 '01234566'
(2) 再对新的一组字符串做排序，这样包含的数字相同的数就排到了一起
(3) 再遍历排序后的这组字符串，找到重复了5次字符串
(4) 如果找到了满足条件的字符串 S ，说明本组中存在5个数，包含的数字完全相同。那么再遍历依次这组数，和(1) 一样分解排序重组后得到的字符串，如果和 S 相等，则满足条件，保存。最后输出所有保存的数即可

### Python

# 一个数对应的排列的位数，肯定和它的位数相等，即8位数的排列，必然也是8位数
# 那么我们就从1位数开始，找到所有位数相同的立方数，然后尝试从中找5个立方数的数字相同的数

lastLen = 0
cubes = [] # 存放所有位数相同的立方数
i = 1
while True :
cube = i**3
if len(str(cube)) > lastLen : # 位数增加
lastLen = len(str(cube))

# 至此，cubes 中已经保存了所有位数为 lastLen 的立方数
# 再判断 cubes 中是否存在 5 个数，它们包含的数字相同

# (1) 先将所有数，分解成数字，然后将数字从小到大重组，得到新的一组字符串。比如 41063625 转换成 '01234566'
cubes_str = [ ''.join(sorted(list(str(n)))) for n in cubes]

# (2) 再对这组字符串做排序，这样包含的数字相同的数就排到了一起
cubes_str = sorted(cubes_str)

# (3) 再遍历排序后的这组字符串，找到出现了5次字符串
repeatedCnt = 0
lastStr = 0
for n in cubes_str :
if n == lastStr :
repeatedCnt += 1
if repeatedCnt == 4 : # 重复了4次，加上自己，共出现5次
answer = [ c for c in cubes  if ''.join(sorted(list(str(c)))) == lastStr ]
print(answer)
exit(0)
else:
lastStr = n
repeatedCnt = 0
# 重置 cubes
cubes = []
cubes.append(cube)
i += 1

### Golang

package main

import (
"fmt"
"sort"
"strings"
)

// 将n分解成数字，然后将数字从小到大重组，得到新的一组字符串。
// 如 n = 41063625，返回 '01234566'
func sortNumber(n int64) string {

// 分解
str := fmt.Sprintf("%v", n)
var digits []string
for _, c := range str {
digits = append(digits, fmt.Sprintf("%v", c-48))
}

// 排序
sort.Slice(digits, func(i, j int) bool {
return digits[i] < digits[j]
})

// 重组
return strings.Join(digits, "")
}

func main() {

// 一个数对应的排列的位数，肯定和它的位数相等，即8位数的排列，必然也是8位数
// 那么我们就从1位数开始，找到所有位数相同的立方数，然后尝试从中找5个立方数的数字相同的数

lastLen := 0
var cubes []int64 // 存放所有位数相同的立方数
for i := int64(1); ; i++ {
cube := i * i * i
cubeStr := fmt.Sprintf("%v", cube)
if len(cubeStr) > lastLen { // 位数增加
lastLen = len(cubeStr)

// 至此，cubes 中已经保存了所有位数为 lastLen 的立方数
// 再判断 cubes 中是否存在 5 个数，它们包含的数字相同

// (1) 先将所有数，分解成数字，然后将数字从小到大重组，得到新的一组字符串。比如 41063625 转换成 '01234566'
var cubesStr []string
for _, c := range cubes {
// e.g. c = 41063625 转换成 '01234566'，存放到 cubesStr 中
cubesStr = append(cubesStr, sortNumber(c))
}

// (2) 再对这组字符串做排序，这样包含的数字相同的数就排到了一起
sort.Slice(cubesStr, func(i, j int) bool {
return cubesStr[i] < cubesStr[j]
})

// (3) 再遍历排序后的这组字符串，找到出现了5次字符串
repeatedCnt, lastStr := 0, ""
for _, s := range cubesStr {
if s == lastStr {
repeatedCnt++
if repeatedCnt == 4 { // 重复了4次，加上自己，共出现5次
var answer []int64
for _, c := range cubes {
if sortNumber(c) == lastStr {
answer = append(answer, c)
}
}

fmt.Println(answer)
return
}
} else {
repeatedCnt = 0
lastStr = s
}
}

// 重置 cubes
cubes = []int64{}

} else {
// 位数没有增加，继续添加
cubes = append(cubes, cube)
}
}
}

127035954683

# Problem 61 Cyclical figurate numbers

## Problem 61: Cyclical figurate numbers

https://projecteuler.net/problem=61

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

Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
Square P4,n=n2 1, 4, 9, 16, 25, ...
Pentagonal P5,n=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal P6,n=n(2n−1) 1, 6, 15, 28, 45, ...
Heptagonal P7,n=n(5n−3)/2 1, 7, 18, 34, 55, ...
Octagonal P8,n=n(3n−2) 1, 8, 21, 40, 65, ...

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 (P3,127=8128), square (P4,91=8281), and pentagonal (P5,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.

## 分析

8128,2882,8281 分别是三角形数，五边形数和五边形数，并且前一个数的后两位数字，是后一个数的前两位（最后一个数的后两位，是第一个数的前两位），形成了一个循环，即 abcd, cdef, efab 这样的格式。

## 方法 遍历判断

### Python


# 三角形数 n(n+1)/2
triangle = [ int(n*(n+1)/2) for n in range(1, 200) if n*(n+1)/2 >= 1000 and n*(n+1)/2 <= 9999 ]
# 四边形数 n^2
square = [ n*n for n in range(1, 101) if n*n >= 1000 and n*n <= 9999 ]
# 五边形数 n(3n−1)/2
pentagonal = [ int(n*(3*n-1)/2) for n in range(1, 100) if n*(3*n-1)/2 >= 1000 and n*(3*n-1)/2 <= 9999 ]
# 六边形数 n(2n−1)
hexagonal = [ n*(2*n-1) for n in range(1, 100) if n*(2*n-1) >= 1000 and n*(2*n-1) <= 9999 ]
# 七边形数 n(5n−3)/2
heptagonal = [ int(n*(5*n-3)/2) for n in range(1, 100) if n*(5*n-3)/2 >= 1000 and n*(5*n-3)/2 <= 9999 ]
# 八边形数 n(3n−2)
octagonal = [ n*(3*n-2) for n in range(1, 100) if n*(3*n-2) >= 1000 and n*(3*n-2) <= 9999 ]

# 保存所有类型的数并去重
all = set()
for n in triangle: all.add(n)
for n in square: all.add(n)
for n in pentagonal: all.add(n)
for n in hexagonal: all.add(n)
for n in heptagonal: all.add(n)
for n in octagonal: all.add(n)

# 将所有的数从小到大排序，用于后面的遍历
all = sorted(all)

# 判断 nums 中的数，是否包含了 kinds 中的所有种类（不能一个数代表多个种类）
# 初始时：kinds = {3,4,5,6,7,8} 表示 三角形数，四边形数，.... 八边形数
def containsAllKinds(nums, kinds):
if len(nums) == 0:
return True if len(kinds) == 0 else False

global triangle, square, pentagonal, hexagonal, heptagonal, octagonal

if nums[0] in triangle:
# remove 3 from kinds
kinds_cpy = kinds.copy()
if 3 in kinds_cpy:
kinds_cpy.remove(3)
if containsAllKinds(nums[1:], kinds_cpy): return True

if nums[0] in square:
# remove 4 from kinds
kinds_cpy = kinds.copy()
if 4 in kinds_cpy:
kinds_cpy.remove(4)
if containsAllKinds(nums[1:], kinds_cpy): return True

if nums[0] in pentagonal:
# remove 5 from kinds
kinds_cpy = kinds.copy()
if 5 in kinds_cpy:
kinds_cpy.remove(5)
if containsAllKinds(nums[1:], kinds_cpy): return True

if nums[0] in hexagonal:
# remove 6 from kinds
kinds_cpy = kinds.copy()
if 6 in kinds_cpy:
kinds_cpy.remove(6)
if containsAllKinds(nums[1:], kinds_cpy): return True

if nums[0] in heptagonal:
# remove 7 from kinds
kinds_cpy = kinds.copy()
if 7 in kinds_cpy:
kinds_cpy.remove(7)
if containsAllKinds(nums[1:], kinds_cpy): return True

if nums[0] in octagonal:
# remove 8 from kinds
kinds_cpy = kinds.copy()
if 8 in kinds_cpy:
kinds_cpy.remove(8)
if containsAllKinds(nums[1:], kinds_cpy): return True

return False

# 假设 6个数依次为 : x1,x2,x3,x4,x5,x6
# 遍历寻找答案
for x1 in all:
# 找到所有以 x1 后两位开头的数，即可能的 x2 集合
possiblex2  = [ x2 for x2 in all if str(x2)[0:2] == str(x1)[-2:] ]

for x2 in possiblex2:
# 找到所有以 x2 后两位开头的数，即可能的 x3 集合
possiblex3  = [ x3 for x3 in all if str(x3)[0:2] == str(x2)[-2:] ]

for x3 in possiblex3:
# 找到所有以 x3 后两位开头的数，即可能的 x4 集合
possiblex4  = [ x4 for x4 in all if str(x4)[0:2] == str(x3)[-2:] ]

for x4 in possiblex4:
# 找到所有以 x4 后两位开头的数，即可能的 x5 集合
possiblex5  = [ x5 for x5 in all if str(x5)[0:2] == str(x4)[-2:] ]

for x5 in possiblex5:
# 找到所有以 x5 后两位开头的数，即可能的 x6 集合
possiblex6  = [ x6 for x6 in all if str(x6)[0:2] == str(x5)[-2:] ]

for x6 in possiblex6:
# 判断 x6 的后两位，是否是x1 的前两位，如果是，则满足了循环的要求
if str(x1)[0:2] == str(x6)[-2:] :
nums = [x1,x2,x3,x4,x5,x6]

# 不能有重复数字
if len(set(nums)) < 6 : continue

# 判断 x1,x2,x3,x4,x5,x6 是否满足分别是三角形数... 八边形数都存在
if containsAllKinds(nums, set([3,4,5,6,7,8])):
print(x1,x2,x3,x4,x5,x6, "sum:", sum(nums))

### Golang

package main

import (
"fmt"
"sort"
)

var triangle []int
var square []int
var pentagonal []int
var hexagonal []int
var heptagonal []int
var octagonal []int

func containsElement(slice []int, element int) bool {
for _, e := range slice {
if e == element {
return true
}
}
return false
}

func removeElementFromSlice(slice []int, element int) []int {
var cpy []int
for _, e := range slice {
if e != element {
cpy = append(cpy, e)
}
}
return cpy
}

// 判断 nums 中的数，是否包含了 kinds 中的所有种类（不能一个数代表多个种类）
// 初始时：kinds = {3,4,5,6,7,8} 表示 三角形数，四边形数，.... 八边形数
func containsAllKinds(nums, kinds []int) bool {

// 数字没了
if len(nums) == 0 {
if len(kinds) == 0 { // 类型也没了，说明覆盖全了
return true
}
return false
}

if containsElement(triangle, nums[0]) {
// remove 3 from kinds
kindsCopy := removeElementFromSlice(kinds, 3)
if containsAllKinds(nums[1:], kindsCopy) {
return true
}
}

if containsElement(square, nums[0]) {
// remove 4 from kinds
kindsCopy := removeElementFromSlice(kinds, 4)
if containsAllKinds(nums[1:], kindsCopy) {
return true
}
}

if containsElement(pentagonal, nums[0]) {
// remove 5 from kinds
kindsCopy := removeElementFromSlice(kinds, 5)
if containsAllKinds(nums[1:], kindsCopy) {
return true
}
}

if containsElement(hexagonal, nums[0]) {
// remove 6 from kinds
kindsCopy := removeElementFromSlice(kinds, 6)
if containsAllKinds(nums[1:], kindsCopy) {
return true
}
}

if containsElement(heptagonal, nums[0]) {
// remove 7 from kinds
kindsCopy := removeElementFromSlice(kinds, 7)
if containsAllKinds(nums[1:], kindsCopy) {
return true
}
}

if containsElement(octagonal, nums[0]) {
// remove 8 from kinds
kindsCopy := removeElementFromSlice(kinds, 8)
if containsAllKinds(nums[1:], kindsCopy) {
return true
}
}

return false
}

func getNumbers(expression func(n int) int) []int {
var numbers []int
for n := 1; ; n++ {
v := expression(n)
if v >= 1000 && v <= 9999 {
numbers = append(numbers, v)
}
if v >= 10000 {
break
}
}
return numbers
}

func main() {

// 找到所有所有4位的三角形数、四边形数，五边形数，六边形数，七边形数，八边形数，
// 存放到 triangle, square, pentagonal, hexagonal, heptagonal, octagonal 中

// 三角形数 n(n+1)/2
triangle = getNumbers(func(n int) int {
return n * (n + 1) / 2
})

// 四边形数 n^2
square = getNumbers(func(n int) int {
return n * n
})

// 五边形数 n(3n−1)/2
pentagonal = getNumbers(func(n int) int {
return n * (3*n - 1) / 2
})

// 六边形数 n(2n−1)
hexagonal = getNumbers(func(n int) int {
return n * (2*n - 1)
})

// 七边形数 n(5n−3)/2
heptagonal = getNumbers(func(n int) int {
return n * (5*n - 3) / 2
})

// 八边形数 n(3n−2)
octagonal = getNumbers(func(n int) int {
return n * (3*n - 2)
})

// 保存所有类型的数并去重
mapNumbers := make(map[int]struct{}, 0) // 使用map去重
for _, n := range triangle {
mapNumbers[n] = struct{}{}
}
for _, n := range square {
mapNumbers[n] = struct{}{}
}
for _, n := range pentagonal {
mapNumbers[n] = struct{}{}
}
for _, n := range hexagonal {
mapNumbers[n] = struct{}{}
}
for _, n := range heptagonal {
mapNumbers[n] = struct{}{}
}
for _, n := range octagonal {
mapNumbers[n] = struct{}{}
}

var all []int
for k := range mapNumbers {
all = append(all, k)
}

// 将所有的数从小到大排序，用于后面的遍历
sort.Slice(all, func(i, j int) bool {
return all[i] < all[j]
})

// 假设 6个数依次为 : x1,x2,x3,x4,x5,x6
// 遍历寻找答案
for _, x1 := range all {
// 找到所有以 x1 后两位开头的数即可能的 x2 集合
last2bitOfx1 := (fmt.Sprintf("%v", x1))[2:4]

var possiblex2 []int
for _, x2 := range all {
first2bitOfx2 := (fmt.Sprintf("%v", x2))[0:2]
if last2bitOfx1 == first2bitOfx2 {
possiblex2 = append(possiblex2, x2)
}
}

for _, x2 := range possiblex2 {
// 找到所有以 x2 后两位开头的数，即可能的 x3 集合
last2bitOfx2 := (fmt.Sprintf("%v", x2))[2:4]

var possiblex3 []int
for _, x3 := range all {
first2bitOfx3 := (fmt.Sprintf("%v", x3))[0:2]
if last2bitOfx2 == first2bitOfx3 {
possiblex3 = append(possiblex3, x3)
}
}

for _, x3 := range possiblex3 {
// 找到所有以 x3 后两位开头的数，即可能的 x4 集合
last2bitOfx3 := (fmt.Sprintf("%v", x3))[2:4]

var possiblex4 []int
for _, x4 := range all {
first2bitOfx4 := (fmt.Sprintf("%v", x4))[0:2]
if last2bitOfx3 == first2bitOfx4 {
possiblex4 = append(possiblex4, x4)
}
}

for _, x4 := range possiblex4 {
// 找到所有以 x4 后两位开头的数，即可能的 x5 集合
last2bitOfx4 := (fmt.Sprintf("%v", x4))[2:4]

var possiblex5 []int
for _, x5 := range all {
first2bitOfx5 := (fmt.Sprintf("%v", x5))[0:2]
if last2bitOfx4 == first2bitOfx5 {
possiblex5 = append(possiblex5, x5)
}
}

for _, x5 := range possiblex5 {
// 找到所有以 x5 后两位开头的数，即可能的 x6 集合
last2bitOfx5 := (fmt.Sprintf("%v", x5))[2:4]

var possiblex6 []int
for _, x6 := range all {
first2bitOfx6 := (fmt.Sprintf("%v", x6))[0:2]
if last2bitOfx5 == first2bitOfx6 {
possiblex6 = append(possiblex6, x6)
}
}

for _, x6 := range possiblex6 {
// 判断 x6 的后两位，是否是x1 的前两位，如果是，则满足了循环的要求
first2bitOfx1 := (fmt.Sprintf("%v", x1))[0:2]
last2bitOfx6 := (fmt.Sprintf("%v", x6))[2:4]
if first2bitOfx1 != last2bitOfx6 {
continue
}

nums := []int{x1, x2, x3, x4, x5, x6}

// 不能有重复数字
mapNums := make(map[int]struct{}, 0)
for _, n := range nums {
mapNums[n] = struct{}{}
}

if len(mapNums) != len(nums) {
continue
}

// 判断 x1,x2,x3,x4,x5,x6 是否满足分别是三角形数... 八边形数都存在
if containsAllKinds(nums, []int{3, 4, 5, 6, 7, 8}) {
fmt.Println(x1, x2, x3, x4, x5, x6, "sum:", x1+x2+x3+x4+x5+x6)
}
}
}
}
}
}
}

}


## 答案

28684

6个数为：1281 8128 2882 8256 5625 2512

# Problem 60 Prime pair sets

## Problem 60: Prime pair sets

https://projecteuler.net/problem=60

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

## 方法1 尝试 + 穷举

primes = [i for i in range(1,10000) if isPrime(i)]

curMin = 9999999999
answer = []
for a in range(0, len(primes)-5):
print("a", a)
stra = str(primes[a])
for b in range(a+1, len(primes)-4):
strb = str(primes[b])
if not isPrime(int(stra+strb)) or not isPrime(int(strb+stra)) :
continue
for c in range(b+1, len(primes)-3):
strc = str(primes[c])
if not isPrime(int(stra+strc)) or not isPrime(int(strc+stra)) or \
not isPrime(int(strb+strc)) or not isPrime(int(strc+strb)) :
continue
for d in range(c+1, len(primes)-2):
strd = str(primes[d])
if not isPrime(int(stra+strd)) or not isPrime(int(strd+stra)) or \
not isPrime(int(strb+strd)) or not isPrime(int(strd+strb)) or \
not isPrime(int(strc+strd)) or not isPrime(int(strd+strc)) :
continue
for e in range(d+1, len(primes)-1):
stre = str(primes[e])
if not isPrime(int(stra+stre)) or not isPrime(int(stre+stra)) or \
not isPrime(int(strb+stre)) or not isPrime(int(stre+strb)) or \
not isPrime(int(strc+stre)) or not isPrime(int(stre+strc)) or \
not isPrime(int(strd+stre)) or not isPrime(int(stre+strd)) :
continue
s = primes[a] +  primes[b] + primes[c] + primes[d] + primes[e]
print(stra, strb, strc, strd, stre, "sum:",s)
if s < curMin :
curMin = s
answer = [curMin, stra, strb, strc, strd, stre]
break

print(answer)

### Python

from math import sqrt
import time

def isPrime(n):
if n <= 1 : return False
if n == 2 or n == 3 : return True
if n % 2 == 0 : return False

# 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
# 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
# 即大于等于5的质数一定满足 n%6==1 or n%6==5
# https://blog.csdn.net/songyunli1111/article/details/78690447
if n % 6 != 1 and n % 6 != 5 : return False

# 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i in range(5, int(sqrt(n)) + 1, 6):
if n % i == 0 or n % (i+2) == 0: return False

return True

primes = [i for i in range(1, 26034) if isPrime(i)]

curMin = 26034
answer = []
for a in range(0, len(primes)-5):
if 5*primes[a] >= curMin: break # [优化点1] if a+a+a+a+a > curMin, then a+b+c+d+e > curMin, break
stra = str(primes[a])
for b in range(a+1, len(primes)-4):
if primes[a] + 4*primes[b] >= curMin: break # [优化点1]
strb = str(primes[b])
if not isPrime(int(stra+strb)) or not isPrime(int(strb+stra)) :
continue
for c in range(b+1, len(primes)-3):
if primes[a] + primes[b] + 3*primes[c] >= curMin: break # [优化点1]
strc = str(primes[c])
if not isPrime(int(stra+strc)) or not isPrime(int(strc+stra)) or \
not isPrime(int(strb+strc)) or not isPrime(int(strc+strb)) :
continue
for d in range(c+1, len(primes)-2):
if primes[a] + primes[b] + primes[c] + 2*primes[d] >= curMin: break # [优化点1]
strd = str(primes[d])
if not isPrime(int(stra+strd)) or not isPrime(int(strd+stra)) or \
not isPrime(int(strb+strd)) or not isPrime(int(strd+strb)) or \
not isPrime(int(strc+strd)) or not isPrime(int(strd+strc)) :
continue
#print( primes[a],primes[b],primes[c],primes[d])
for e in range(d+1, len(primes)-1):
if primes[a] + primes[b] + primes[c] + primes[d] + primes[e] >= curMin: break # [优化点1]
stre = str(primes[e])
if not isPrime(int(stra+stre)) or not isPrime(int(stre+stra)) or \
not isPrime(int(strb+stre)) or not isPrime(int(stre+strb)) or \
not isPrime(int(strc+stre)) or not isPrime(int(stre+strc)) or \
not isPrime(int(strd+stre)) or not isPrime(int(stre+strd)) :
continue
s = primes[a] +  primes[b] + primes[c] + primes[d] + primes[e]
print(stra, strb, strc, strd, stre, "sum:", s)
if s < curMin :
curMin = s
answer = [curMin, stra, strb, strc, strd, stre]
break

print("answer:", answer)

### Golang

package main

import (
"fmt"
"strconv"
)

func isPrime(n int64) bool {
if n <= 1 {
return false
}

if n == 2 || n == 3 {
return true
}

if n%2 == 0 {
return false
}

// 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
// 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
// 即大于等于5的质数一定满足 n%6==1 or n%6==5
// https://blog.csdn.net/songyunli1111/article/details/78690447
if n%6 != 1 && n%6 != 5 {
return false
}

// 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i := int64(5); i*i <= n; i++ {
if n%i == 0 {
return false
}
}

return true
}

func isBothPrimes(a, b string) bool {
ab, _ := strconv.ParseInt(a+b, 10, 64)
if !isPrime(ab) {
return false
}

ba, _ := strconv.ParseInt(b+a, 10, 64)
if !isPrime(ba) {
return false
}
return true
}

func main() {

primes := []int{2}
for i := 3; i <= 26033; i += 2 {
if isPrime(int64(i)) {
primes = append(primes, i)
}
}
fmt.Println(len(primes))

curMin := 26034
for a := 5; a < len(primes)-4; a++ {
if 5*primes[a] >= curMin { // [优化点1] if a+a+a+a+a > curMin, then a+b+c+d+e > curMin, break
break
}
stra := fmt.Sprintf("%d", primes[a])

for b := a + 1; b < len(primes)-3; b++ {
if primes[a]+4*primes[b] >= curMin { // [优化点1]
break
}
strb := fmt.Sprintf("%d", primes[b])
if !isBothPrimes(stra, strb) {
continue
}

for c := b + 1; c < len(primes)-2; c++ {
if primes[a]+primes[b]+3*primes[c] >= curMin { // [优化点1]
break
}
strc := fmt.Sprintf("%d", primes[c])
if !isBothPrimes(stra, strc) || !isBothPrimes(strb, strc) {
continue
}

for d := c + 1; d < len(primes)-1; d++ {
if primes[a]+primes[b]+primes[c]+2*primes[d] >= curMin {
break
}

strd := fmt.Sprintf("%d", primes[d])
if !isBothPrimes(stra, strd) || !isBothPrimes(strb, strd) || !isBothPrimes(strc, strd) {
continue
}

for e := d + 1; e < len(primes); e++ {
if primes[a]+primes[b]+primes[c]+primes[d]+primes[e] >= curMin {
break
}
stre := fmt.Sprintf("%d", primes[e])
if !isBothPrimes(stra, stre) || !isBothPrimes(strb, stre) ||
!isBothPrimes(strc, stre) || !isBothPrimes(strd, stre) {
continue
}

sum := primes[a] + primes[b] + primes[c] + primes[d] + primes[e]
fmt.Printf("%v, %v, %v, %v, %v, sum:%v", stra, strb, strc, strd, stre, sum)
if sum < curMin {
curMin = sum
}
break
}
}
}
}
}
fmt.Printf("answer:%v\n", curMin)
}

### CPP

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdint>

bool isPrime(int64_t n)
{
if(n <= 1 ) return false;
if(n == 2 || n == 3) return true;
if(n % 2 == 0) return false;

// 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
// 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
// 即大于等于5的质数一定满足 n%6==1 or n%6==5
// https://blog.csdn.net/songyunli1111/article/details/78690447
if(n % 6 != 1 && n % 6 != 5 ) return false;

// 从 [5, sqrt(n)] 遍历寻找是否是其因数
for(int64_t i=5; i * i <= n; i+=6){
if( n % i == 0 || n % (i+2) == 0 ) return false;
}
return true;
}

bool isBothPrimes(std::string a, std::string b)
{
std::string strAB = a + b;
long ab = atol(strAB.c_str());
if (!isPrime((int64_t)ab)) {
return false;
}

std::string strBA = b + a;
long ba = atol(strBA.c_str());
if (!isPrime((int64_t)ba)) {
return false;
}

return true;
}

int main()
{
std::vector<int> primes;
primes.push_back(2);
for(int i = 3; i <= 26033; i += 2) {
if(isPrime((int64_t)i)) {
primes.push_back(i);
}
}
printf("%ld\n", primes.size());

int curMin = 26034;
for( int a = 5; a < primes.size()-4; a++) {
if( 5*primes[a] >= curMin) break; // [优化点1] if a+a+a+a+a > curMin, then a+b+c+d+e > curMin, break

std::string stra = std::to_string(primes[a]);
for(int b = a + 1; b < primes.size()-3; b++) {
if( primes[a]+4*primes[b] >= curMin) break;  // [优化点1]

std::string strb = std::to_string(primes[b]);
if( !isBothPrimes(stra, strb)) continue;

for(int c = b + 1; c < primes.size()-2; c++) {
if(primes[a]+primes[b]+3*primes[c] >= curMin) break;  // [优化点1]

std::string strc = std::to_string(primes[c]);
if( !isBothPrimes(stra, strc) || !isBothPrimes(strb, strc)) continue;

for(int d = c + 1; d < primes.size()-1; d++) {
if( primes[a]+primes[b]+primes[c]+2*primes[d] >= curMin) break;

std::string strd = std::to_string(primes[d]);
if( !isBothPrimes(stra, strd) || !isBothPrimes(strb, strd) ||
!isBothPrimes(strc, strd)){
continue;
}

for( int e = d + 1; e < primes.size(); e++) {
if(primes[a]+primes[b]+primes[c]+primes[d]+primes[e] >= curMin) break;

std::string stre = std::to_string(primes[e]);
if (!isBothPrimes(stra, stre) || !isBothPrimes(strb, stre) ||
!isBothPrimes(strc, stre) || !isBothPrimes(strd, stre)) {
continue;
}

int sum = primes[a] + primes[b] + primes[c] + primes[d] + primes[e];
printf("%d, %d, %d, %d, %d, sum:%d\n", primes[a], primes[b], primes[c], primes[d], primes[e], sum);
if (sum < curMin) {
curMin = sum;
}
break;
}
}
}
}
}

printf("answer:%d\n", curMin);
return 0;
}

26033

# Problem 59 XOR decryption

## Problem 59: XOR decryption

https://projecteuler.net/problem=59

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using p059_cipher.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

## 分析

XOR 异或操作可以用于加密，因为它有一个特性：加密和解密可以使用相同的秘钥。如 65 XOR 42 = 107, 107 XOR 42 = 65，65 使用秘钥42加密得到107，107 又可以使用秘钥42解密成65。

## 方法 如分析中的思路

### CPP

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

int main()
{
// 读取文件中的所有数字，转换成字符，保存到cipher中
char line[32] = {0};
std::vector<char> cipher; // 密文
std::ifstream f("p059_cipher.txt");
while(f.getline(line, 32, ',')){
int ascii = atoi(line);
cipher.push_back( (char) ascii );
}
f.close();

// 尝试使用 a~z 来解码
for(char key1 = 'a'; key1 <= 'z'; key1++){
for(char key2 = 'a'; key2 <= 'z'; key2++){
for(char key3 = 'a'; key3 <= 'z'; key3++){

char keys[3] = {key1, key2, key3};
std::vector<char> plainText;
bool isValid = true;
for(int i = 0; i < cipher.size(); i++){
char key = keys[ i % 3];
char plain = cipher[i] ^ key;
// 如果 plain 是不可打印的字符，必然不可能是明文
if( plain < 32 || plain >= 127){
isValid = false;
break;
}

plainText.push_back(plain);
}

if(!isValid) continue;

printf("\n\nkey:%c%c%c\n", key1, key2,key3);
for(int i=0;i<plainText.size(); i++) printf("%c", plainText[i]);
printf("\n");
}
}
}

// 通过上面的尝试解码，从输出的360种可能解码中，最终发现密码为 exp
// 所以使用 exp 来解码，并且统计明文的ASCII码值总和

char keys[3] = {'e', 'x', 'p'};
int sum = 0;
printf("\n\n--- the plain text ---\n");
for(int i = 0; i < cipher.size(); i++){
char key = keys[ i % 3];
char plain = cipher[i] ^ key;
sum += (int)plain;
printf("%c", plain);
}
printf("\n\nthe sum of plain ascii is: %d\n", sum);
return 0;
}

## 答案

129448

An extract taken from the introduction of one of Euler's most celebrated papers, "De summis serierum reciprocarum" [On the sums of series of reciprocals]: I have recently found, quite unexpectedly, an elegant expression for the entire sum of this series 1 + 1/4 + 1/9 + 1/16 + etc., which depends on the quadrature of the circle, so that if the true sum of this series is obtained, from it at once the quadrature of the circle follows. Namely, I have found that the sum of this series is a sixth part of the square of the perimeter of the circle whose diameter is 1; or by putting the sum of this series equal to s, it has the ratio sqrt(6) multiplied by s to 1 of the perimeter to the diameter. I will soon show that the sum of this series to be approximately 1.644934066842264364; and from multiplying this number by six, and then taking the square root, the number 3.141592653589793238 is indeed produced, which expresses the perimeter of a circle whose diameter is 1. Following again the same steps by which I had arrived at this sum, I have discovered that the sum of the series 1 + 1/16 + 1/81 + 1/256 + 1/625 + etc. also depends on the quadrature of the circle. Namely, the sum of this multiplied by 90 gives the biquadrate (fourth power) of the circumference of the perimeter of a circle whose diameter is 1. And by similar reasoning I have likewise been able to determine the sums of the subsequent series in which the exponents are even numbers.

# Problem 58 Spiral primes

## Problem 58: Spiral primes

https://projecteuler.net/problem=58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

## 分析

1 为第1层，往外一圈一圈扩展，则：

• 第 2 层四个角的数字：3，5，7，9 差值为 2 = 2*2 - 2
• 第 3 层四个角的数字：13，17，21，25 差值为 4 = 2*3 - 2
• 第 4 层四个角的数字：31，37，43，49 差值为 6 = 2*4 - 2
• 第 n 层四个角的数字：x1,x2,x3,x4 差值为 2n - 2

边长：Edge(n) = 2n-1

TR(n+1) = BR(n) + Edge(n+1) - 1 = TR(n)+6n-6+2n+1-1 = TR(n)+8n-6

## 方法 根据分析中的公式，遍历判断质数

### CPP

#include <stdio.h>

bool isPrime(int n)
{
if(n <= 1 ) return false;
if(n == 2 || n == 3) return true;
if(n % 2 == 0) return false;
if(n % 6 != 1 && n % 6 != 5 ) return false;
for(int i=5; i * i <= n; i++){
if( n % i == 0 ) return false;
}
return true;
}

int main()
{
int totalCnt = 1; // 第一层的 1
int primeCnt = 0;
int prevTR = 1; // TR(1)

// 循环判断第 n 圈的四个数
for(int n = 2; ; n++){
int tr = prevTR + 8*n - 14; // TR(n) = TR(n-1) + 8n - 14
totalCnt += 4;

if(isPrime(tr)) primeCnt++;       // 右上角数：TR(n)
if(isPrime(tr+2*n-2)) primeCnt++; // 左上角数：TL(n) = TR(n)+2n-2
if(isPrime(tr+4*n-4)) primeCnt++; // 左下角数：BL(n) = TL(n) + Edge(n) - 1 = TR(n)+4n-4
if(isPrime(tr+6*n-6)) primeCnt++; // 右下角数：BR(n) = BL(n) + Edge(n) - 1 = TR(n)+6n-6

//printf("n=%d, %d,%d,%d,%d, [%d/%d]\n", n, tr, tr+2*n-2, tr+4*n-4, tr+6*n-6, primeCnt, totalCnt);

if( (float)primeCnt / (float)totalCnt  < 0.1){
printf("%d\n", 2*n-1);// Edge(n) = 2n-1
break;
}
prevTR = tr;
}

return 0;
}

### Golang

package main

import (
"fmt"
)

func isPrime(n int) bool {
if n <= 1 {
return false
}

if n == 2 || n == 3 {
return true
}

if n%2 == 0 {
return false
}

// 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
// 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
// 即大于等于5的质数一定满足 n%6==1 or n%6==5
// https://blog.csdn.net/songyunli1111/article/details/78690447
if n%6 != 1 && n%6 != 5 {
return false
}

// 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i := 5; i*i <= n; i++ {
if n%i == 0 {
return false
}
}

return true
}

func main() {
totalCnt := 1 // 第一层的 1
primeCnt := 0
prevTR := 1 // TR(1)

// 循环判断第 n 圈的四个数
for n := 2; ; n++ {
tr := prevTR + 8*n - 14 // TR(n) = TR(n-1) + 8n - 14
totalCnt += 4

if isPrime(tr) { // 右上角数：TR(n)
primeCnt++
}
if isPrime(tr + 2*n - 2) { // 左上角数：TL(n) = TR(n)+2n-2
primeCnt++
}
if isPrime(tr + 4*n - 4) { // 左下角数：BL(n) = TL(n) + Edge(n) - 1 = TR(n)+4n-4
primeCnt++
}
if isPrime(tr + 6*n - 6) { // 右下角数：BR(n) = BL(n) + Edge(n) - 1 = TR(n)+6n-6
primeCnt++
}

if float32(primeCnt)/float32(totalCnt) < 0.1 {
fmt.Println(2*n - 1) // Edge(n) = 2n-1
break
}
prevTR = tr
}
}

### Python

from math import sqrt

def isPrime(n):
if n <= 1 : return False
if n == 2 or n == 3 : return True
if n % 2 == 0 : return False

# 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
# 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
# 即大于等于5的质数一定满足 n%6==1 or n%6==5
# https://blog.csdn.net/songyunli1111/article/details/78690447
if n % 6 != 1 and n % 6 != 5 : return False

# 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i in range(5, int(sqrt(n)) + 1):
if n % i == 0 : return False

return True

totalCnt = 1 # 第一层的 1
primeCnt = 0
prevTR = 1  # TR(1)

# 循环判断第 n 圈的四个数
n = 2
while True:
tr = prevTR + 8*n - 14 # TR(n) = TR(n-1) + 8n - 14
totalCnt += 4

if isPrime(tr) : # 右上角数：TR(n)
primeCnt += 1

if isPrime(tr + 2*n - 2) : # 左上角数：TL(n) = TR(n)+2n-2
primeCnt += 1

if isPrime(tr + 4*n - 4) : # 左下角数：BL(n) = TL(n) + Edge(n) - 1 = TR(n)+4n-4
primeCnt += 1

if isPrime(tr + 6*n - 6) : # 右下角数：BR(n) = BL(n) + Edge(n) - 1 = TR(n)+6n-6
primeCnt += 1

if primeCnt/totalCnt < 0.1 :
print(2*n - 1) # Edge(n) = 2n-1
break

prevTR = tr
n += 1

26241

# Problem 57: Square root convergents

## Problem 57: Square root convergents

https://projecteuler.net/problem=57

## 分析

第 1 次扩展结果: fraction = 1 + 1/2

...

1 + 1/(2+1/(2+1/(2+1/(2+1/(2+1/2)))))  x 2
1 + 1/(2+1/(2+1/(2+1/(2+2/(4+1)))))
1 + 1/(2+1/(2+1/(2+1/(2+2/5))))        x 5
1 + 1/(2+1/(2+1/(2+5/(10+2))))
1 + 1/(2+1/(2+1/(2+5/12)))             x 12
1 + 1/(2+1/(2+12/(24+5)))
1 + 1/(2+1/(2+12/29))                  x 29
1 + 1/(2+29/(58+12))
1 + 1/(2+29/70)                       x 70
1 + 70/(140+29)
1 + 70/169

(1) 先找最后一个 1/(a+b/c) 格式的算式

(2) 再对该算式做 *c 处理，得到 c/(a*c+b)，计算出 a*c+b 的值，变成 c/d

(3) 再使用 c/d 替换 1/(a+b/c) 即可

## 方法1 如分析

### Golang

package main

import (
"fmt"
"math/big"
"strings"
)

// 做 cnt 次展开，返回最终分数的分子和分母
func expansion(cnt int) (numerator, denominator *big.Int) {

// 1 + 1/2 => 1 + 1/(2+1/2)  => 1 + 1/(2 + 1/(2+1/2) ) => 1 + 1/(2+1/(2+ 1/(2+1/2) ))
// i.e 每次展开相当于替换 1/2 为 1/(2+1/2)
// cnt: 1, fraction: 1 + 1/2
// cnt: 2, fraction: 1 + 1/(2+1/2)
// cnt: 3, fraction: 1 + 1/(2+1/(2+1/2))
// cnt: 4, fraction: 1 + 1/(2+1/(2+1/(2+1/2)))
// cnt: 5, fraction: 1 + 1/(2+1/(2+1/(2+1/(2+1/2))))
// cnt: 6, fraction: 1 + 1/(2+1/(2+1/(2+1/(2+1/(2+1/2)))))

fraction := "1+1/2"      // 第一次展开的值
for i := 1; i < cnt; i++ { // 再做 cnt-1 次展开
fraction = strings.ReplaceAll(fraction, "1/2", "1/(2+1/2)")
}

// 接下来，计算 fraction 算式的值

// 以cnt=6时为例，整个求值过程如下：
// 1 + 1/(2+1/(2+1/(2+1/(2+1/(2+1/2)))))  x 2
// 1 + 1/(2+1/(2+1/(2+1/(2+2/(4+1)))))
// 1 + 1/(2+1/(2+1/(2+1/(2+2/5))))        x 5
// 1 + 1/(2+1/(2+1/(2+5/(10+2))))
// 1 + 1/(2+1/(2+1/(2+5/12)))             x 12
// 1 + 1/(2+1/(2+12/(24+5)))
// 1 + 1/(2+1/(2+12/29))                  x 29
// 1 + 1/(2+29/(58+12))
// 1 + 1/(2+29/70)                       x 70
// 1 + 70/(140+29)
// 1 + 70/169

// 可见，每次相当于：
// (1) 先找最后一个 1/(a+b/c) 格式的算式
// (2) 再对该算式做 *c 处理，得到 c/(a*c+b)，计算出a*c+b的值，变成 c/d
// (3) 再使用 c/d 替换 1/(a+b/c) 即可

for{
// (1) 先找到最后一个 1/(a+b/c) 格式的算式，
// 起始点 start 为倒数第二个除号 / 前一位
// 结束点 end 为 start 之后的第一个右括号 )
// 如果找不到，说明整个算式已经是 1+a/b 的形式了，结束

start, end := -1, -1 // 起止点
seq := 0
for i := len(fraction) - 1; i >= 0; i-- {
if fraction[i:i+1] == "/" {
seq++
if seq == 2 { // 倒数第二个 /
start = i - 1
break
}
}
}

// 没找到 start，说明已经是 1+a/b 的形式了
if start == -1 {
break
}

// start 之后的第一个右括号 ) 即为 end
for i := start; i <= len(fraction) - 1; i++ {
if fraction[i:i+1] == ")" {
end = i
break
}
}

// (2) 取出算式 expression = fraction[start,end] 做 *c 处理，得到 c/(a*c+b) => c/d
// 从算式 1/(a+b/c) 中取出 a,b,c 的值，计算出 d, 并生成 c/d
// 注意，a,b,c,d 都可能是大数
expression := fraction[start:end+1] // 1/(a+b/c)
expression = strings.ReplaceAll(expression,"(", "") // 1/(a+b/c) => 1/a+b/c)
expression = strings.ReplaceAll(expression,")", "") // 1/a+b/c) => 1/a+b/c
arr := strings.Split(expression, "/") // [1,a+b,c]
arr2 := strings.Split(arr[1], "+") // [a,b]

a,b,c,d := big.NewInt(0),big.NewInt(0),big.NewInt(0),big.NewInt(0)
a, _ = a.SetString(arr2[0], 10)
b, _ = b.SetString(arr2[1], 10)
c, _ = c.SetString(arr[2], 10)
d = d.Mul(a,c) // d := a*c+b
d = d.Add(d,b)
s := fmt.Sprintf("%v/%v", c.String(), d.String()) // s: c/d

// (3) 再使用 c/d 替换 1/(a+b/c) 即可
fraction = strings.ReplaceAll(fraction, fraction[start:end+1], s)

//fmt.Println(fraction)
}

// 运行至此，fraction 格式为 1+a/b
// 取出从 1+a/b 中取出 a,b 的值
arr := strings.Split(fraction,"+") // [1,a/b]
arr2 := strings.Split(arr[1], "/") // [a,b]

a,b := big.NewInt(0),big.NewInt(0)
a, _ = a.SetString(arr2[0], 10)
b, _ = b.SetString(arr2[1], 10)

// 1+a/b => (a+b)/b, 分子 a+b, 分母 b
// [对分子分母不用做约分]
numerator, denominator= big.NewInt(0), big.NewInt(0)
numerator = numerator.Add(a,b) // 分子
denominator = b                // 分母

//fmt.Printf("cnt=%v, fraction=%v/%v\n", cnt, numerator, denominator)
return numerator, denominator
}

func main() {
cnt := 0
for i := 1; i <= 1000; i++ {
numerator, denominator := expansion(i)
if len(numerator.String()) > len(denominator.String()) {
cnt++
}
}

fmt.Println(cnt)
}

## 方法2 来自论坛中的第一个答案

### Python

def expand(n):
(num,den) = (1,2)
for i in range(1, n): (num,den) = (den,num + 2*den)
return (num,den)

def nth(n):
(num,den) = expand(n)
return len(str(num+den)) > len(str(den))

counter = 0
for n in range(0, 1000):
if nth(n+1): counter += 1
print(counter)

153

# Problem 56 Powerful digit sum

## Problem 56: Powerful digit sum

https://projecteuler.net/problem=56

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

## 分析

ab, 其中 a, b < 100，求所有数字的和最大的数，它的所有数字和。

## 方法1 使用字符串解决大数问题 [适用于C++]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 123 => [1,2,3]
// n >= 0
std::vector<char> int2vector(int n)
{
std::vector<char> digits;
if(n == 0){
digits.push_back('0');
return digits;
}

while(n > 0){
digits.push_back( n % 10 + '0' );
n /= 10;
}

std::reverse(digits.begin(), digits.end());

return digits;
}

/***********************************************************
* a+b
* a >= 0
* b >= 0
* return a+b
************************************************************/
std::vector<char> add(const std::vector<char>& a, const std::vector<char>& b)
{
// 存放和（逆序）
std::vector<char> sum;

// 从低位到高位，依次相加
int i = 0, j = 0, acc = 0; // acc 进位
for(i = a.size()-1, j = b.size()-1; i >= 0 && j >= 0; i--, j --){
int v = (int) (a[i] - '0') + (int) (b[j] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// a.size > b.size, b已经加完，a剩余
for(; i >= 0; i--){
int v = (int) (a[i] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// a.size < b.size, a已经加完，b剩余
for(; j >= 0; j--){
int v = (int) (b[j] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// 补上 acc
if( acc > 0){
sum.push_back( (char) ( acc + '0' ) );
}

// 对sum进行逆序
std::reverse(sum.begin(), sum.end());
return sum;
}

/***********************************************************
* a*b
* a >= 0
* b 是 0~9 之间的整数
* return a*b
************************************************************/
std::vector<char> mul(const std::vector<char>& a, int b)
{
// 存放乘积
std::vector<char> product;

if(b == 0){
product.push_back('0');
return std::move(product);
}

// 将乘法转换为加法
for(int i = 0; i < a.size(); i++){ // product = a
product.push_back(a[i]);
}

for(int i = 0; i < b-1; i ++){  //  累加 b-1 次 a
product = add(product, a);
}

return std::move(product);
}

/***********************************************************
* a*b
* a >= 0
* b >= 0
* return a*b
************************************************************/
std::vector<char> mul(const std::vector<char>& a, const std::vector<char>& b)
{
// 存放乘积
std::vector<char> product;
std::vector<char> a1;
for(int i = 0; i< a.size(); i ++) a1.push_back(a[i]);

// 将乘法转换为加法
for(int i = b.size() - 1; i >= 0; i--){
std::vector<char> p = mul(a1, (int)(b[i] - '0') );
product = add(product, p);
a1.push_back('0'); // a1 *= 10，因为b的位数每高一位，a1 要乘以 10
}

return product;
}

int main()
{
int max = 0;
for(int a = 1; a <= 100; a++){

std::vector<char> va = int2vector(a);
std::vector<char> product = int2vector(a);

for(int b = 1; b <= 100; b++){
std::vector<char> tmp = mul(product, va);
product.swap(tmp);

int sum = 0;
for(int i = 0; i < product.size(); i++){
sum += product[i] - '0';
}

if(sum > max){
max = sum;
}
}
}

printf("max:%d\n", max);
return 0;
}

## 方法2 使用库函数解决大数问题 [适用于 Golang]

package main

import (
"fmt"
"math/big"
)

func sumOfDigits(a, b int) int {

bigA := big.NewInt(int64(a))
mul := big.NewInt(int64(a))
for i := 1; i < b; i++ {
mul.Mul(mul, bigA)
}

sum := 0
for _, s := range mul.String() {
sum += int(s - 48)
}

return sum
}

func main() {

max := 0
for a := 1; a <= 100; a++ {
for b := 1; b <= 100; b++ {
sum := sumOfDigits(a, b)
if sum > max {
max = sum
}
}
}

fmt.Println(max)
}


## 方法3 无需考虑大数问题，直接计算 [适用于 Python]

max = 0
for a in range(1,101):
for b in range(1, 101):
r = sum( [ int(n) for n in list(str(a**b))] )
if r > max :
print("find a larger: ", a,b,r)
max = r
print(max)

print( max([ sum( [ int(n) for n in list(str(a**b))] ) for a in range(1,101) for b in range(1, 101) ]))

972

9995

# Problem 55 Lychrel numbers

## Problem 55: Lychrel numbers

https://projecteuler.net/problem=55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

## 分析

47 逆序得到 74， 47 + 74 = 121 是一个回文数。 349 需要迭代 3 次：349 + 943 = 1292, 1292 + 2921 = 4213，4213 + 3124 = 7337 才能得到一个回文数。

## 方法1 使用字符串解决大数问题 [适用于C++]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 123 => [1,2,3]
// n >= 0
std::vector<char> int2vector(int n)
{
std::vector<char> digits;
if(n == 0){
digits.push_back('0');
return digits;
}

while(n > 0){
digits.push_back( n % 10 + '0' );
n /= 10;
}

std::reverse(digits.begin(), digits.end());

return digits;
}

/***********************************************************
* a+b
* a >= 0
* b >= 0
* return a+b
************************************************************/
std::vector<char> add(const std::vector<char>& a, const std::vector<char>& b)
{
// 存放和（逆序）
std::vector<char> sum;

// 从低位到高位，依次相加
int i = 0, j = 0, acc = 0; // acc 进位
for(i = a.size()-1, j = b.size()-1; i >= 0 && j >= 0; i--, j --){
int v = (int) (a[i] - '0') + (int) (b[j] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// a.size > b.size, b已经加完，a剩余
for(; i >= 0; i--){
int v = (int) (a[i] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// a.size < b.size, a已经加完，b剩余
for(; j >= 0; j--){
int v = (int) (b[j] - '0') + acc;
acc = v / 10;
sum.push_back( (char) ( (v % 10) + '0' ) );
}

// 补上 acc
if( acc > 0){
sum.push_back( (char) ( acc + '0' ) );
}

// 对sum进行逆序
std::reverse(sum.begin(), sum.end());
return sum;
}

bool isEqual(const std::vector<char>& v1, const std::vector<char>& v2)
{
for(int i = 0; i < v1.size(); i++){
if(v1[i] != v2[i]){
return false;
}
}
return true;
}

bool isLychrelNumber(int n)
{
std::vector<char> number = int2vector(n);
std::vector<char> reversed;
std::reverse_copy(number.begin(), number.end(), std::back_inserter(reversed));

// 最多迭代50次
for (int iterator = 1; iterator <= 50; iterator++ ) {
std::vector<char> sum = add(number, reversed);
std::vector<char> sumReversed;
std::reverse_copy(sum.begin(), sum.end(), std::back_inserter(sumReversed));

if( isEqual(sum, sumReversed)) { // 回文
return false;
}

number.swap(sum);
reversed.swap(sumReversed);
}

return true;
}

int main()
{
int cnt = 0;
for (int i = 1; i < 10000; i++) {
if (isLychrelNumber(i)) {
//printf("%d\n", i);
cnt++;
}
}

printf("cnt:%d\n", cnt);
return 0;
}

## 方法2 使用库函数解决大数问题 [适用于 Golang]

package main

import (
"fmt"
"math/big"
)

// 1234 -> 4321
func Reverse(n *big.Int) *big.Int {
r := big.NewInt(0)
strN := n.String()
for i := len(strN) - 1; i >= 0; i-- {
r.Mul(r, big.NewInt(10))                // r *= 10
r.Add(r, big.NewInt(int64(strN[i]-48))) // 字符转数字：s-48
}
return r
}

func isLychrelNumber(n int) bool {

number := big.NewInt(int64(n))
reversed := Reverse(number)

// 最多迭代50次
for iterator := 1; iterator <= 50; iterator++ {
sum := big.NewInt(0).Add(number, reversed)
sumReversed := Reverse(sum)
if sum.String() == sumReversed.String() {
return false
}

number, reversed = sum, sumReversed
}

return true
}
func main() {

var lychrelNumbers []int
for i := 1; i < 10000; i++ {
if isLychrelNumber(i) {
lychrelNumbers = append(lychrelNumbers, i)
}
}

fmt.Println(len(lychrelNumbers))
}

## 方法3 无需考虑大数问题，直接计算 [适用于 Python]

def isLychrelNumber(n):
for iterator in range(1,51): # 最多50次迭代
reversed = int( str(n)[::-1] )
sum = n + reversed
if str(sum) == str(sum)[::-1] : # 判断是否回文
return False
n = sum

return True

lychrelNumbers = []
for i in range(1, 10000):
if isLychrelNumber(i):
lychrelNumbers.append(i)

print(len(lychrelNumbers))
#print(lychrelNumbers)

249

# Problem 54 Poker hands

## Problem 54: Poker hands

https://projecteuler.net/problem=54

download poker.txt

## 分析

• 高牌，即大散牌(High Card): Highest value card.
• 一对(One Pair)
• 两对(Two Pairs)
• 三条(Three of a Kind)
• 顺子(Straight)
• 同花(Flush)
• 葫芦，即三条+一对(Full House)
• 四条(Four of a Kind)
• 同花顺(Straight Flush)
• 皇家同花顺(Royal Flush) : 10, J, Q, K, A 的同花顺

poker.txt 中包含了1000手随机的两个玩家的手牌，文件中每一行包含10张牌，以空格分割，前5个是玩家1的手牌，后5个是玩家2的手牌。保证所有的手牌都是有效的(没有无效的字符或者重复的卡牌)。

## 方法

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>

// 一张牌
class Card{
public:

Card(char value, char suit){
m_value = traslateCardValue(value);
m_suit = suit;
}

Card(const Card& c){
m_value = c.GetValue();
m_suit = c.GetSuit();
}

Card(){}
~Card(){}

int GetValue() const {
return m_value;
}

char GetSuit() const {
return m_suit;
}

// 比较两张牌的大小，只比较面值，不比较花色。
// 返回：1 表示比c大，0 表示和c相等，-1 表示比c小
int Compare(const Card& c) const {
if(m_value > c.GetValue()) return 1;
if(m_value == c.GetValue()) return 0;
return -1;
}

private:
int traslateCardValue(char c){
if(c == '2') return 2;
if(c == '3') return 3;
if(c == '4') return 4;
if(c == '5') return 5;
if(c == '6') return 6;
if(c == '7') return 7;
if(c == '8') return 8;
if(c == '9') return 9;
if(c == 'T') return 10;
if(c == 'J') return 11;
if(c == 'Q') return 12;
if(c == 'K') return 13;
if(c == 'A') return 14;

return 0;
}

int m_value; // 卡牌的面值，2, 3, 4, 5, 6, 7, 8, 9, 10(Ten), 11(Jack), 12(Queen), 13(King), 14(Ace)
char m_suit; // 卡牌的花色，C/D/H/S, C 梅花 clubs (♣), D 方片 diamonds (♦), H 红桃 hearts (♥) and S 黑桃 spades (♠)
};

// 一手牌
class Hand{
public:
Hand(const std::vector<Card>& cards){
for(int i = 0; i < 5; i++){
m_cards[i] = cards[i];
}

// 将手牌从小到大排序，便于后面的比较
std::sort(m_cards, m_cards+5, cardCompare);

// 计算手牌的等级
m_rank = calcRank();
}

// 1, 高牌，即大散牌(High Card)
// 2, 一对(One Pair)
// 3, 两对(Two Pairs)
// 4, 三条(Three of a Kind)
// 5, 顺子(Straight)
// 6, 同花(Flush)
// 7, 葫芦，即三条+一对(Full House)
// 8, 四条(Four of a Kind)
// 9, 同花顺(Straight Flush)
// 10, 皇家同花顺(Royal Flush) : 10, J, Q, K, A 的同花顺
int GetRank() const {
return m_rank;
}

Card GetCardAt(int i) const {
return m_cards[i];
}

// 如果是四条，返回四条的起始手牌位置
int GetFourCardsIndex() const {
return m_fourCardsIndex;
}

// 如果是葫芦或三条，返回三条的起始手牌位置
int GetThreeCardsIndex() const {
return m_threeCardsIndex;
}

// 葫芦时，一对的起始手牌位置，两对时，较大的对子的起始手牌位置，一对时，对子的起始手牌位置
int GetPairIndex() const {
return m_pairIndex;
}

// 如果是两对，返回较小对子的起始手牌位置
int GetSmallerPairIndex() const {
return m_smallerPairIndex;
}

// 比较两手牌的大小，不比较花色(即花色之间无大小区分)
// 返回：1 表示比h大，0 表示和h相等，-1 表示比h小
int Compare(const Hand& h) const {
// (1) 比较等级
if( m_rank > h.GetRank() ) return 1;
if( m_rank < h.GetRank() ) return -1;

// (2) 同等级，比较牌面值

// 都是皇家同花顺，相等
if( m_rank == 10 ) return 0;

// 都是同花顺，比较面值
if( m_rank == 9 ){
return m_cards[0].Compare( h.GetCardAt(0) );
}

// 都是四条，先比较四条，如果四条相等，再比较单牌
if( m_rank == 8 ){

// 比较四条
int cmp = m_cards[m_fourCardsIndex].Compare( h.GetCardAt(h.GetFourCardsIndex()) );
if(cmp != 0) return cmp;

// 四条也相等，比较单牌
int ownHighCardIndex = (m_fourCardsIndex == 0) ? 4 : 0;       // 自己手牌的单张位置
int peerHighCardIndex = (h.GetFourCardsIndex() == 0) ? 4 : 0; // 对手手牌的单张位置

return m_cards[ownHighCardIndex].Compare(h.GetCardAt(peerHighCardIndex));
}

// 都是葫芦，先比较三条，再比较对子
if( m_rank == 7 ){

// 先比较三条
int cmp = m_cards[m_threeCardsIndex].Compare( h.GetCardAt(h.GetThreeCardsIndex()) );
if(cmp != 0) return cmp;

// 再比较对子
return m_cards[m_pairIndex].Compare(h.GetCardAt(h.GetPairIndex()));
}

// 都是同花，从高到低依次比较
if( m_rank == 6 ){
for(int i = 4; i >= 0; i--){
int cmp = m_cards[i].Compare(h.GetCardAt(i));
if(cmp != 0) return cmp;
}
return 0;
}

// 都是顺子，直接比较
if( m_rank == 5 ){
return m_cards[0].Compare(h.GetCardAt(0));
}

// 都是三条，先比较三条，再比较剩下的两个单牌
if( m_rank == 4 ){

// 先比较三条
int cmp = m_cards[m_threeCardsIndex].Compare( h.GetCardAt(h.GetThreeCardsIndex()) );
if(cmp != 0) return cmp;

// 再比较剩下的两个单牌
for(int i = 4; i >= 0; i--){
if( i == m_threeCardsIndex || i == m_threeCardsIndex + 1 || i == m_threeCardsIndex + 2) continue; // 跳过三条

for(int j = 4; j >= 0; j--){
if( j == h.GetThreeCardsIndex() || j == h.GetThreeCardsIndex() + 1 || j == h.GetThreeCardsIndex() + 2) continue; // 跳过三条

cmp = m_cards[i].Compare( h.GetCardAt(j) );
if(cmp != 0) return cmp;
}
}

return 0;
}

// 都是两对，先比较两对，再比较单牌
if ( m_rank == 3 ){

// 先比较两对
int cmp = m_cards[m_pairIndex].Compare( h.GetCardAt(h.GetPairIndex()) );
if(cmp != 0) return cmp;

cmp = m_cards[m_smallerPairIndex].Compare( h.GetCardAt(h.GetSmallerPairIndex()) );
if(cmp != 0) return cmp;

// 再比较单牌
for(int i = 4; i >= 0; i--){
// 跳过两对
if( i == m_pairIndex || i == m_pairIndex + 1 ||
i == m_smallerPairIndex || i == m_smallerPairIndex + 1
){
continue;
}

for(int j = 4; j >= 0; j--){
// 跳过两对
if( j == h.GetPairIndex() || j == h.GetPairIndex() + 1 ||
j == h.GetSmallerPairIndex() || j == h.GetSmallerPairIndex() + 1
){
continue;
}

cmp = m_cards[i].Compare( h.GetCardAt(j) );
if(cmp != 0) return cmp;
}
}

return 0;
}

// 都是一对，先比较一对，再比较单牌
if( m_rank == 2 ){

// 先比较一对
int cmp = m_cards[m_pairIndex].Compare( h.GetCardAt(h.GetPairIndex()) );
if(cmp != 0) return cmp;

// 再比较单牌
for(int i = 4; i >= 0; i-- ){
if( i == m_pairIndex || i == m_pairIndex + 1) continue; // 跳过对子

for(int j = 4; j >= 0; j-- ){
if( j == h.GetPairIndex() || j == h.GetPairIndex() + 1) continue; // 跳过对子

cmp = m_cards[i].Compare( h.GetCardAt(j) );
if(cmp != 0) return cmp;
}
}

return 0;
}

// 都是高牌，即散牌，从高到低比较
for(int i = 4; i >= 0; i-- ){
for(int j = 4; j >= 0; j-- ){
int cmp = m_cards[i].Compare( h.GetCardAt(j) );
if(cmp != 0) return cmp;
}
}

return 0;
}

private:
static bool cardCompare (Card c1, Card c2) {
return c1.Compare(c2) < 0 ;
}

// 计算手牌的等级
int calcRank(){
if(hasRoyalFlush()) return 10;
if(hasStraightFlush()) return 9;
if(hasFourOfAKind()) return 8;
if(hasFullHouse()) return 7;
if(hasFlush()) return 6;
if(hasStraight()) return 5;
if(hasThreeOfAKind()) return 4;
if(hasTwoPairs()) return 3;
if(hasOnePair()) return 2;
return 1;
}

// [手牌已从小到大排序] 检查是否有一对
bool hasOnePair(){
for(int i = 0; i < 4; i++){
if( m_cards[i].GetValue() == m_cards[i+1].GetValue()){
m_pairIndex = i;
return true;
}
}
return false;
}

// [手牌已从小到大排序] 检查是否有两对
bool hasTwoPairs(){

int firstIndex = -1;
for(int i = 0; i < 4; i++){
if( m_cards[i].GetValue() == m_cards[i+1].GetValue()){ // 找到一对
if(firstIndex == -1 ) { // 第一对
firstIndex = i;
i++;
}else{ // 第二对
m_smallerPairIndex = firstIndex;
m_pairIndex = i;
return true;
}
}
}

return false;
}

// [手牌已从小到大排序] 检查是否有三条
bool hasThreeOfAKind(){
for(int i = 0; i < 3; i++){
if( m_cards[i].GetValue() == m_cards[i+1].GetValue() &&
m_cards[i].GetValue() == m_cards[i+2].GetValue()
){
m_threeCardsIndex = i;
return true;
}
}
return false;
}

// [手牌已从小到大排序] 检查是否有顺子
bool hasStraight(){
if( m_cards[1].GetValue() == m_cards[0].GetValue() + 1 &&
m_cards[2].GetValue() == m_cards[0].GetValue() + 2 &&
m_cards[3].GetValue() == m_cards[0].GetValue() + 3 &&
m_cards[4].GetValue() == m_cards[0].GetValue() + 4
){
return true;
}
return false;
}

// [手牌已从小到大排序] 检查是否有同花
bool hasFlush()
{
// 花色相同
if( m_cards[1].GetSuit() == m_cards[0].GetSuit() &&
m_cards[2].GetSuit() == m_cards[0].GetSuit() &&
m_cards[3].GetSuit() == m_cards[0].GetSuit() &&
m_cards[4].GetSuit() == m_cards[0].GetSuit()
){
return true;
}
return false;
}

// [手牌已从小到大排序] 检查是否有葫芦
bool hasFullHouse(){
// aaabb
if( m_cards[1].GetValue() == m_cards[0].GetValue() &&
m_cards[2].GetValue() == m_cards[0].GetValue() &&
m_cards[3].GetValue() == m_cards[4].GetValue()
){
m_threeCardsIndex = 0;
m_pairIndex = 3;
return true;
}

// aabbb
if( m_cards[0].GetValue() == m_cards[1].GetValue() &&
m_cards[3].GetValue() == m_cards[2].GetValue() &&
m_cards[4].GetValue() == m_cards[2].GetValue()
){
m_threeCardsIndex = 2;
m_pairIndex = 0;
return true;
}

return false;
}

// [手牌已从小到大排序] 检查是否有四条
bool hasFourOfAKind(){
for(int i = 0; i < 2; i++){
if( m_cards[i].GetValue() == m_cards[i+1].GetValue() &&
m_cards[i].GetValue() == m_cards[i+2].GetValue() &&
m_cards[i].GetValue() == m_cards[i+3].GetValue()
){
m_fourCardsIndex = i;
return true;
}
}
return false;
}

// [手牌已从小到大排序] 检查是否有同花顺
bool hasStraightFlush(){
return hasStraight() && hasFlush();
}

// [手牌已从小到大排序] 检查是否有皇家同花顺
bool hasRoyalFlush(){
return (m_cards[0].GetValue() == 10) && hasStraightFlush();
}

Card m_cards[5]; // 一手牌包括五张牌
int m_rank;      // 手牌的等级

// 一些关键信息，用于比较，在判断等级时就记录，避免后续重复判断手牌
int m_fourCardsIndex;   // 如果是四条，保存四条的起始手牌位置
int m_threeCardsIndex;  // 葫芦和三条时，保存三条的起始手牌位置
int m_pairIndex;        // 葫芦时，一对的起始手牌位置，两对时，较大的对子的起始手牌位置，一对时，对子的起始手牌位置
int m_smallerPairIndex; // 两对时，较小对子的起始手牌位置
};

int main()
{
int player1WinCnt = 0;

// 从文件中读取每一行的两手牌
std::ifstream f("poker.txt");
char line[64] = {0};
while( f.getline(line, 64)){
// 将每一行分割成 10 张牌，分别给 玩家1 和 玩家2
std::vector<Card> cards1;
std::vector<Card> cards2;

std::string s = line;
std::istringstream iss(s);
std::string item;
while (std::getline(iss, item, ' ')) {
//std::cout << item << std::endl;
Card c(item[0], item[1]);
if(cards1.size() < 5){ // 前 5 张牌给玩家1
cards1.push_back(c);
} else{                // 后 5 张牌给玩家2
cards2.push_back(c);
}
}

// 比较玩家1 和 玩家2 的手牌
Hand player1(cards1);
Hand player2(cards2);
if(player1.Compare(player2) > 0){
player1WinCnt ++;
}
}
f.close();

std::cout<<player1WinCnt<<std::endl;
return 0;
}

376

# Problem 53 Combinatoric selections

## Problem 53: Combinatoric selections

https://projecteuler.net/problem=53

## 分析

C(n,r) = n! / r!(n-r)!，计算过程中，可以先做约分，再计算最终结果。假设 max = max(r,n-r). 可以先约去 max!。 min = min(r,n-r).

   n!        (约去max)     (max+1)(max+2)...(n-2)(n-1)n
-----------     =     ------------------------------------
max!*min!                 1*2*3...*(min-2)*(min-1)*min

## 方法 通过约分，避免大数

### CPP

#include <iostream>
#include <vector>

#define MAX_C 1000000

// 辗转相除法 求最大公约数
int gcd(int a, int b){
int r=1;        // 余数,赋初值为1
while(r != 0){  // 如果a<b,亦无需颠倒ab，在计算中商0余除数本身，在下次运算中自可颠倒回来
r = a % b;
a = b;
b = r;
}
return a;
}

// 判断 C(n,r) 是否大于 MAX_C
bool C(int n, int r)
{
// 获取 r 和 n-r 中较大的数和较小的数，保存在 max,min 中
int max = r, min = n-r;
if(r < n-r){
max = n-r;
min = r;
}

//C(n,r) = n! / (max! * min!)

// 分别统计分子和分母的所有乘数

std::vector<int> numerator; // 保存分子的所有乘数 (max+1)(max+2)...(n-2)(n-1)n
for(int i = max + 1; i <= n; i++){
numerator.push_back(i);
}

std::vector<int> denominator; // 保存分母的所有乘数 1*2*3...*(min-2)*(min-1)*min
for(int i = 1; i <= min; i++){
denominator.push_back(i);
}

// 对分子分母做约分

// 从分子的最后一个乘数（因为最后一个乘数最大）开始，分别对分母的所有乘数做约分
for(int i = numerator.size() - 1; i >= 0; i--){
for(int j = denominator.size() -1; j >= 0; j--){
if(numerator[i] == 1 ) break;    // 分子的乘数无需再化简了
if(denominator[j] == 1) continue; // 分母的乘数无法再化简了，继续判断分母的下一个乘数

// 找到 numerator[i] 和 denominator[j] 的最大公约数，然后做约分
int g = gcd(numerator[i], denominator[j]);
//printf("i=%d, j=%d, %d, %d, %d\n", i, j, numerator[i], denominator[j], g);
numerator[i] /= g;
denominator[j] /= g;
}
}

// 因为C(n,r) 最终必然是整数，所以约分到最后，分母中所有乘数应该都是 1
// 所有直接计算分子的乘积即可

int mul = 1;
for(int i = 0; i < numerator.size(); i++){
mul *= numerator[i];

if(mul > MAX_C) return true;
}

return false;
}

int main()
{
int cnt = 0;
for(int n = 1; n <= 100; n++){
for(int r = 1; r <= n; r++){
if (C(n,r)) {
cnt ++;
}
}
}

printf("cnt=%d\n", cnt);
return 0;
}

### Golang

package main

import "fmt"

const MAX_C = 1000000

// 辗转相除法 求最大公约数
func gcd(a, b int) int {
r := 1       // 余数,赋初值为1
for r != 0 { // 如果a<b,亦无需颠倒ab，在计算中商0余除数本身，在下次运算中自可颠倒回来
r = a % b
a = b
b = r
}
return a // 此时b的值已经在a中了，所以输出的a就是最大公约数
}

// 判断 C(n,r) 是否大于 MAX_C
func C(n, r int) bool {

// 获取 r 和 n-r 中较大的数和较小的数，保存在 max,min 中
max, min := r, n-r
if r < n-r {
max = n - r
min = r
}

// C(n,r) = n! / (max! * min!)

// 分别统计分子和分母的所有乘数

var numerator []int // 保存分子的所有乘数 (max+1)(max+2)...(n-2)(n-1)n
for i := max + 1; i <= n; i++ {
numerator = append(numerator, i)
}

var denominator []int // 保存分母的所有乘数 1*2*3...*(min-2)*(min-1)*min
for i := 1; i <= min; i++ {
denominator = append(denominator, i)
}

// 对分子分母做约分

// 从分子的最后一个乘数（因为最后一个乘数最大）开始，分别对分母的所有乘数做约分
for i := len(numerator) - 1; i >= 0; i-- {
for j := len(denominator) - 1; j >= 0; j-- {
if numerator[i] == 1 { // 分子的乘数无需再化简了
break
}

if denominator[j] == 1 { // 分母的乘数无法再化简了，继续判断分母的下一个乘数
continue
}

// 找到 numerator[i] 和 denominator[j] 的最大公约数，然后做约分
g := gcd(numerator[i], denominator[j])
numerator[i] /= g
denominator[j] /= g
}
}

// 因为C(n,r) 最终必然是整数，所以约分到最后，分母中所有乘数应该都是 1
// 所有直接计算分子的乘积即可

mul := 1
for i := 0; i < len(numerator); i++ {
mul *= numerator[i]

if mul > MAX_C {
return true
}
}

return false
}

func main() {

cnt := 0
for n := 1; n <= 100; n++ {
for r := 1; r <= n; r++ {
if C(n, r) {
cnt++
}
}
}

fmt.Printf("cnt=%d\n", cnt)
}


### Python

def factorial(n):
mul = 1
for i in range(1,n+1):
mul *= i
return mul

def C(n,r):
return factorial(n) / (factorial(r) * factorial(n-r))

cnt = 0
for n in range(1,101):
for r in range(1, n+1):
if C(n,r) > 1000000:
cnt += 1
print(cnt)

4075

# Problem 52 Permuted multiples

## Problem 52: Permuted multiples

https://projecteuler.net/problem=52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

## 方法 遍历求解

• (1) 判断 x 和 6x 的位数是否相同；如果不相同跳转到 (2)，如果相同跳转到 (3)
• (2) 不相等时，在 x 位数不变的情况下，随着 x 的增大，两者更不可能相等, 所以，此时需要给 x 增加位数。 如 x = 17，6x = 102，此时 18~99 都可以直接跳过了，直接跳到下一个位数的起始点 x = 100。 增加位数后，再跳转会(1)
• (3) 依次获取 x, 2x, 3x, 4x, 5x, 6x 的所有排序好的数字列表，判断是否都相等，如果全都相等，则找到了答案，输出，结束。 如果不全相等，x++ 继续 步骤 (1)。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int getLen(int n)
{
int len = 0;
while(n > 0){
len++;
n /= 10;
}

return len;
}

std::vector<int> getDigitsSorted(int n)
{
std::vector<int> digits;
while(n > 0){
digits.push_back(n % 10);
n /= 10;
}
std::sort(digits.begin(), digits.end());

return digits;
}

bool hasSameDigits(const std::vector<int>& v1, const std::vector<int>& v2)
{
if(v1.size() != v2.size()) return false;

for(int i = 0; i < v1.size(); i++){
if( v1[i] != v2[i]) return false;
}

return true;
}

int main()
{
int x = 11;
while(true){
// 判断 x 和 6x 的位数是否相等
int lenX = getLen(x);
int len6X = getLen(6*x);

// 如果不相等，在 x 位数不变的情况下，随着 x 的增大，两者更不可能相等
// 所以，此时需要给 x 增加位数
// 如， x = 17，6x = 102，此时 18~99 都可以直接跳过了，直接跳到下一个位数的起始点 x = 100，再继续处理
if(len6X > lenX){
x = (int) pow(10, lenX) ;
continue;
}

// 如果相等，继续判断 x, 2x, 3x, 4x, 5x, 6x 是否包含相同的数字

// 获取 x 的所有数字
std::vector<int> digitsX = getDigitsSorted(x);

bool bHasSameDigits = true;
for(int i = 2; i <= 6; i++){
// 获取 i*x 的所有数字
std::vector<int> digitsIX= getDigitsSorted(i*x);
if( ! hasSameDigits(digitsX, digitsIX)){
bHasSameDigits = false;
break;
}
}

// 找到了一个满足条件的解
if(bHasSameDigits){
printf("find answer: %d, %d, %d, %d, %d, %d\n", x, 2*x,3*x, 4*x, 5*x, 6*x);
return 0;
}

// 继续查找下一个数
x++;
}

return 0;
}

### Golang

package main

import (
"fmt"
"math"
"sort"
)

func getDigitsSorted(n int) []int {
var digits []int
for n > 0 {
digits = append(digits, n%10)
n /= 10
}

sort.Slice(digits, func(i, j int) bool {
return digits[i] < digits[j]
})

return digits
}

func hasSameDigits(v1, v2 []int) bool {

if len(v1) != len(v2) {
return false
}

for i := 0; i < len(v1); i++ {
if v1[i] != v2[i] {
return false
}
}

return true
}

func main() {
x := 11
for {
// 判断 x 和 6x 的位数是否相等
lenX := len(fmt.Sprintf("%d", x))
len6X := len(fmt.Sprintf("%d", 6*x))

// 如果不相等，在 x 位数不变的情况下，随着 x 的增大，两者更不可能相等
// 所以，此时需要给 x 增加位数
// 如， x = 17，6x = 102，此时 18~99 都可以直接跳过了，直接跳到下一个位数的起始点 x = 100，再继续处理
if len6X > lenX {
x = int(math.Pow(10, float64(lenX)))
continue
}

// 如果相等，继续判断 x, 2x, 3x, 4x, 5x, 6x 是否包含相同的数字

// 获取 x 的所有数字
digitsX := getDigitsSorted(x)

bHasSameDigits := true
for i := 2; i <= 6; i++ {
// 获取 i*x 的所有数字
digitsIX := getDigitsSorted(i * x)

if !hasSameDigits(digitsX, digitsIX) {
bHasSameDigits = false
break
}
}

// 找到了一个满足条件的解
if bHasSameDigits {
fmt.Printf("find answer: %d, %d, %d, %d, %d, %d\n", x, 2*x, 3*x, 4*x, 5*x, 6*x)
return
}

// 继续查找下一个数
x++
}
}


### Python

x = int(11)

while True:
# 判断 x 和 6x 的位数是否相等
lenX = len(str(x))
len6X = len(str(6*x))

# 如果不相等，在 x 位数不变的情况下，随着 x 的增大，两者更不可能相等
# 所以，此时需要给 x 增加位数
# 如， x = 17，6x = 102，此时 18~99 都可以直接跳过了，直接跳到下一个位数的起始点 x = 100，再继续处理
if len6X > lenX :
x = 10**lenX
continue

# 如果相等，继续判断 x, 2x, 3x, 4x, 5x, 6x 是否包含相同的数字
# 获取 x 的所有数字
digitsX = list(str(x))
digitsX.sort()

bHasSameDigits = True
for i in range(1,7):
# 获取 i*x 的所有数字
digitsIX = list(str(i*x))
digitsIX.sort()

if digitsX != digitsIX :
bHasSameDigits = False
break

# 找到了一个满足条件的解
if bHasSameDigits :
print("find answer: ", x, 2*x, 3*x, 4*x, 5*x, 6*x)
exit(0)

# 继续查找下一个数
x = x + 1

## 答案

142857

find answer: 142857, 285714, 428571, 571428, 714285, 857142

# Problem 51 Prime digit replacements

## Problem 51: Prime digit replacements

https://projecteuler.net/problem=51

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

## 方法

• (1) 分解得到其所有位上的数字 digits[]，如 n = 123, 则 digits = [1,2,3]
• (2) 然后，获取从 digits.size() 个位置中，选出 cnt = 1~digits.size() 个位置的选法，这个cnt个位置用于后面做0~9的替换，通过 getChoices(digits.size(), cnt) 返回所有的选法。如 n = 123, digits = [1,2,3]，digits.size() = 3， getChoices(3, 1) 表示从3个位置中，选择1个位置，返回 [[0],[1],[2]]，表示有三种选法，即分别选第0位，第1位，第2位。getChoices(3, 2) 表示从3个位置中，选择2个位置，返回 [[0,1],[0,2],[1,2]]，表示有三种选法，即分别选第0位和第1位，第0位和第2位，第1位和第2位。
• (3) 对于(2) 中获得每一种选法，使用 0~9 来替换选中的位置，生成一个family，使用replace(digits, choice) 函数实现。如 n=123, replace([1,2,3], [0,1]) 表示将 digits的第0位和第1位 依次使用 0~9 替换，返回 113,223,333,443,553,663,773,883,993。注意：003 需要被剔除。
• (4) 判断返回的family 是否包含8个质数，如果包含，则找到了答案，结束

### CPP

#include <iostream>
#include <vector>
#include <algorithm>

bool isPrime(int n)
{
if(n <= 1 ) return false;
if(n == 2 || n == 3) return true;
if(n % 2 == 0) return false;
if(n % 6 != 1 && n % 6 != 5 ) return false;
for(int i=5; i * i <= n; i++){
if( n % i == 0 ) return false;
}
return true;
}

// 从 flag[start~len) 中，选择 cnt 个位置，填充为1
// choices: 如果找到了一种选法，则保存到 choices 中
// flag: 待填充的数组，flag[i] = 1，表示选中 i 位置，0 表示不选择该位置
// len: flag数组的长度
// start: 开始的位置
// cnt: 要填充的个数
void select(std::vector<std::vector<int> >& choices, int flag[], int len, int start, int cnt)
{
// 找到了一种选法，保存到 choices 中
if(cnt == 0){
std::vector<int> choice;
for(int i = 0; i < len; i++){
if(flag[i] == 1) choice.push_back(i);
}
choices.push_back(choice);
return;
}

// flag 已经遍历完，直接返回
if(start >= len) return;

// 填充某个中间位置，分两种情况：填充和不填充

// (1) 填充
flag[start] = 1;
select(choices, flag, len, start + 1, cnt - 1);

// (2) 不填充
for(int i = start; i < len; i++){ // 重置(1)中的修改
flag[i] = 0;
}
select(choices, flag, len, start + 1, cnt);

return;
}

// select cnt from len
// 返回所有的可能的选择方法
std::vector<std::vector<int> > getChoices(int len, int cnt)
{
std::vector<std::vector<int> > choices;
int flag[100] = {0};
select(choices, flag, len, 0, cnt);
return choices;
}

// 分别用 0~9 替换 digits 中 choice 包含的位置，获得一组数字
std::vector<int> replace(std::vector<int> digits, std::vector<int> choice)
{
std::vector<int> family;
for(int digit = 0; digit <= 9; digit++ ){

for(int k = 0; k < choice.size(); k++){
digits[ choice[k] ] = digit;
}

// convert digits to int
int v = 0;
for(int k = 0; k < digits.size(); k++){
v *= 10;
v += digits[k];
}

// 如果 0 出现在开头，则位数不同。所以需要剔除 0 出现在开头的情况
if(digit == 0 && choice[0] == 0) continue;

family.push_back(v);
}

return family;
}

int main()
{
// 从小到大遍历所有的质数，判断能否替换其中几位的数字，生成一组质数
for(int n = 11; ; n++){
if(!isPrime(n)) continue;

// 分解得到 i 的每一位数字
std::vector<int> digits;
int cpy = n;
while(cpy > 0){
digits.push_back( cpy % 10 );
cpy /= 10;
}

// 分解得到的是逆序的。需要再逆序回来
std::reverse(digits.begin(), digits.end());

// 依次替换 digits 中 1 ~ digits.size() 个位置，判断能否生成 8 prime value family
for(int cnt = 1; cnt <= digits.size(); cnt++){

// 替换 cnt 个位置
// 从 digits.size() 个位置中，选 cnt 个位置，使用 0~9 替换；即 select cnt from digits.size()
std::vector<std::vector<int> > choices = getChoices(digits.size(), cnt);
for(int h = 0; h < choices.size(); h++){

std::vector<int> family = replace(digits, choices[h]);
int primeCnt = 0;
for(int i = 0; i < family.size(); i++){
if(isPrime(family[i])) primeCnt ++;
}

if( primeCnt == 8){
printf("find family: ");
for(int i = 0; i < family.size(); i++){
if(isPrime(family[i])) printf("%d ", family[i]);
}
printf("\n");
return 0;
}
}
}
}

return 0;
}

// select cnt from len
// 返回所有的可能的选择方法
std::vector<std::vector<int> > getChoices(int len, int cnt)
{
// 从 len 中选择 cnt 个位置，相当于对数组 [0,0,0...1,1,1] 做全排列
std::vector<std::vector<int> > choices;

// 总长 len, 末尾 cnt 个 1，开头 len-cnt 个 0
std::vector<int> flag;
for(int i = 0; i < len; i++){
if( i < len-cnt ) flag.push_back(0);
else{
flag.push_back(1);
}
}

// 对 flag 进行全排列
do{
std::vector<int> choice;
for(int i = 0; i < len; i++){
if(flag[i] == 1) choice.push_back(i);
}
choices.push_back(choice);
}while ( std::next_permutation(flag.begin(), flag.end()));

return choices;
}

### Golang

package main

import (
"fmt"
)

func isPrime(n int) bool {
if n <= 1 {
return false
}

if n == 2 || n == 3 {
return true
}

if n%2 == 0 {
return false
}

if n%6 != 1 && n%6 != 5 {
return false
}

for i := 5; i*i <= n; i++ {
if n%i == 0 {
return false
}
}

return true
}

// 从 flag[start~len) 中，选择 cnt 个位置，填充为1
// choices: 如果找到了一种选法，则保存到 choices 中
// flag: 待填充的数组，flag[i] = 1，表示选中 i 位置，0 表示不选择该位置
// len: flag数组的长度
// start: 开始的位置
// cnt: 要填充的个数
func select1(choices *[][]int, flag []int, len, start, cnt int) {

// 找到了一种选法，保存到 choices 中
if cnt == 0 {
var choice []int
for i := 0; i < len; i++ {
if flag[i] == 1 {
choice = append(choice, i)
}
}
*choices = append(*choices, choice)
//fmt.Println("append:", choices)
return
}

// flag 已经遍历完，直接返回
if start >= len {
return
}

// 填充某个中间位置，分两种情况：填充和不填充

// (1) 填充
flag[start] = 1
select1(choices, flag, len, start+1, cnt-1)

// (2) 不填充
for i := start; i < len; i++ { // 重置(1)中的修改
flag[i] = 0
}
select1(choices, flag, len, start+1, cnt)

return
}

// select cnt from len
// 返回所有的可能的选择方法
func getChoices(len, cnt int) [][]int {
var choices [][]int
var flag []int
for i := 0; i < len; i++ {
flag = append(flag, 0)
}
select1(&choices, flag, len, 0, cnt)
//fmt.Println("getChoice: ", choices)
return choices
}

// 分别用 0~9 替换 digits 中 choice 包含的位置，获得一组数字
func replace(digits []int, choice []int) []int {

var cpy []int
cpy = append(cpy, digits...)

var family []int
for digit := 0; digit <= 9; digit++ {

for k := 0; k < len(choice); k++ {
cpy[choice[k]] = digit
}

// convert digits to int
v := 0
for k := 0; k < len(cpy); k++ {
v *= 10
v += cpy[k]
}

// 如果 0 出现在开头，则位数不同。所以需要剔除 0 出现在开头的情况
if digit == 0 && choice[0] == 0 {
continue
}

family = append(family, v)
}

return family
}

func main() {

// 从小到大遍历所有的质数，判断能否替换其中几位的数字，生成一组质数
for n := 11; ; n++ {
if !isPrime(n) {
continue
}

// 分解得到 i 的每一位数字
var digits []int
cpy := n
for cpy > 0 {
digits = append(digits, cpy%10)
cpy /= 10
}

// 分解得到的是逆序的。需要再逆序回来
for i := 0; i < len(digits)/2; i ++ {
digits[i],digits[len(digits)-i-1] = digits[len(digits)-i-1], digits[i]
}

// 依次替换 digits 中 1 ~ len(digits) 个位置，判断能否生成 8 prime value family
for cnt := 1; cnt <= len(digits); cnt++ {

// 替换 cnt 个位置
// 从 len(digits) 个位置中，选 cnt 个位置，使用 0~9 替换；即 select cnt from len(digits)
choices := getChoices(len(digits), cnt)
for h := 0; h < len(choices); h++ {
family := replace(digits, choices[h])
primeCnt := 0
for i := 0; i < len(family); i++ {
if isPrime(family[i]) {
primeCnt++
}
}

if primeCnt == 8 {
fmt.Printf("find family: ")
for i := 0; i < len(family); i++ {
if isPrime(family[i]) {
fmt.Printf("%d ", family[i])
}
}
fmt.Println("")
return
}
}
}
}
}


// 获取perm的下一个序列
// std::next_permutation
// 未使用
func nextPermutation(perm []int) bool {
// 长度不超过1，直接返回
if len(perm) <= 1 {
return false
}

// 从后往前，找到第一个 perm[i] < perm[i+1]
// e.g perm=1238[57]64, perm[i]=5
i := -1
for i = len(perm) - 2; i >= 0; i-- {
if perm[i] < perm[i+1] {
break
}
}

// 找不到，说明整个 perm 是递减的，已是最大，没有next
if i == -1 {
return false
}

// 从后往前 [末尾, i+1]，找到第一个比 perm[i] 大的数，然后交换
// e.g. perm=1238[5]7[6]4, 交换 5 和 6
for k := len(perm) - 1; k >= i+1; k-- {
if perm[k] > perm[i] {
// 交换 perm[k] 和 perm[i]
perm[k], perm[i] = perm[i], perm[k] // golang 支持这样交换
break
}
}

// i+1 到末尾目前是降序的，改为升序
// e.g perm=12386[754] => perm=12386[457]
for k := i + 1; k < len(perm); k++ {
last := len(perm) + i - k
if k >= last {
break
}

// 交换 perm[k] 和 perm[last]
perm[k], perm[last] = perm[last], perm[k] // golang 支持这样交换
}

return true
}

// select cnt from len
// 返回所有的可能的选择方法
func getChoices(len, cnt int) [][]int {

// 从 len 中选择 cnt 个位置，相当于对数组 [0,0,0...1,1,1] 做全排列
var choices [][]int

// 总长 len, 末尾 cnt 个 1，开头 len-cnt 个 0
var flag []int
for i := 0; i < len; i++ {
if i < len-cnt {
flag = append(flag, 0)
} else {
flag = append(flag, 1)
}
}

// 对 flag 进行全排列
for ok := true; ok; ok = nextPermutation(flag) {
var choice []int
for i := 0; i < len; i++ {
if flag[i] == 1 {
choice = append(choice, i)
}
}
choices = append(choices, choice)
}

return choices
}

### Python

import math

def isPrime(n):
if n <= 1 : return False
if n == 2 or n == 3 : return True
if n % 2 == 0 : return False

# 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
# 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
# 即大于等于5的质数一定满足 n%6==1 or n%6==5
# https://blog.csdn.net/songyunli1111/article/details/78690447
if n % 6 != 1 and n % 6 != 5 : return False

# 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i in range(5, int(math.sqrt(n)) + 1):
if n % i == 0 : return False

return True

# 获取perm的下一个序列
# std::next_permutation
def nextPermutation(perm) :
# 长度不超过1，直接返回
if len(perm) <= 1 :
return False

# 从后往前，找到第一个 perm[i] < perm[i+1]
# e.g perm=1238[57]64, perm[i]=5
i = len(perm) - 2
while i >= 0 :
if perm[i] < perm[i+1] :
break
i = i - 1

# 找不到，说明整个 perm 是递减的，已是最大，没有next
if i == -1 :
return False

# 从后往前 [末尾, i+1]，找到第一个比 perm[i] 大的数，然后交换
# e.g. perm=1238[5]7[6]4, 交换 5 和 6
for k in range(len(perm) - 1, i, -1) :
if perm[k] > perm[i] :
# 交换 perm[k] 和 perm[i]
perm[k], perm[i] = perm[i], perm[k] # python 支持这样交换
break

# i+1 到末尾目前是降序的，改为升序
# e.g perm=12386[754] => perm=12386[457]
for k in range(i + 1, len(perm)) :
last = len(perm) + i - k
if k >= last :
break

# 交换 perm[k] 和 perm[last]
perm[k], perm[last] = perm[last], perm[k] # python 支持这样交换

return True

# select cnt from len
# 返回所有的可能的选择方法
def getChoices(len, cnt) :
# 从 len 中选择 cnt 个位置，相当于对数组 [0,0,0...1,1,1] 做全排列
choices = []

# 总长 len, 末尾 cnt 个 1，开头 len-cnt 个 0
flag = []
for i in range(0, len) :
if i < len-cnt:
flag.append(0)
else:
flag.append(1)

# 对 flag 进行全排列
while True:
choice = []
for i in range(0, len):
if flag[i] == 1:
choice.append(i)
choices.append(choice)

if not nextPermutation(flag):
break
return choices

def replace(n, choice):

family = []
chars = ['0', '1','2','3','4','5','6','7','8','9']
for digit in chars:
digits = list(str(n))
for k in range(0, len(choice)):
#print(digits, k, choice[k])
digits[ choice[k] ] = digit

f = int(''.join(digits))

if len(str(f)) < len(digits):
continue

family.append(f)
return family

# 从小到大遍历所有的质数，判断能否替换其中几位的数字，生成一组质数
n = 11
while True:
if not isPrime(n):
n += 2
continue
sz = len(str(n))

# 依次替换 n 中 1 ~ sz 个位置，判断能否生成 8 prime value family
for cnt in range(1, sz+1):
# 替换 cnt 个位置
# 从 sz 个位置中，选 cnt 个位置，使用 0~9 替换；即 select cnt from sz
choices = getChoices(sz, cnt)
#print("n=", n, "cnt=", cnt, "choices=", choices)
for c in choices:
family = replace(n, c)
#print("family", family)
primeCnt = 0
for f in family:
if isPrime(f):
primeCnt = primeCnt + 1
#print("primeCnt", primeCnt)
if primeCnt == 8 :
print("find family: ", end="")
for f in family:
if isPrime(f):
print(f, end=" ")
print("")
exit(0)
n += 2

## 答案

121313

family: 121313 222323 323333 424343 525353 626363 828383 929393

# Problem 50 Consecutive prime sum

## Problem 50: Consecutive prime sum

https://projecteuler.net/problem=50

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

## 方法1 遍历统计

### CPP

#include <iostream>
#include <vector>

bool isPrime(int n)
{
if(n <= 1 ) return false;
if(n == 2 || n == 3) return true;
if(n % 2 == 0) return false;

// 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
// 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
// 即大于等于5的质数一定满足 n%6==1 or n%6==5
// https://blog.csdn.net/songyunli1111/article/details/78690447
if(n % 6 != 1 && n % 6 != 5 ) return false;

// 从 [5, sqrt(n)] 遍历寻找是否是其因数
for(int i=5; i * i <= n; i++){
if( n % i == 0 ) return false;
}
return true;
}

int main()
{
// 获取小于1,000,000的所有质数
std::vector<int> primes;
primes.push_back(2);
for(int i = 3; i < 1000000; i+=2 ){
if(isPrime(i)){
primes.push_back(i);
}
}

int curMaxLength = 0;  // 当前的最大长度
int curStartPrime = 0; // 当前的最大长度时，起始的质数
int curMaxSum = 0;     // 当前的最大长度时，连续质数的和

// 遍历寻找
for(int i = 0; i < primes.size(); i++){
int len = 1, primeSum = primes[i], sum = primes[i];

for(int j = i+1; j < primes.size() ;j++){
sum += primes[j];
if(sum > 1000000) break;
if(isPrime(sum)){
len = j - i + 1;
primeSum = sum;
}
}

// 如果找到更长的链，记录
if(len > curMaxLength){
curMaxLength = len;
curStartPrime = primes[i];
curMaxSum = primeSum;

printf("find a longer one, start at %d, length is %d, sum is %d\n", curStartPrime, curMaxLength, curMaxSum);
}
}

return 0;
}

### Golang

package main

import "fmt"

func isPrime(n int) bool {
if n <= 1 {
return false
}

if n == 2 || n == 3 {
return true
}

if n%2 == 0 {
return false
}

// 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
// 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
// 即大于等于5的质数一定满足 n%6==1 or n%6==5
// https://blog.csdn.net/songyunli1111/article/details/78690447
if n%6 != 1 && n%6 != 5 {
return false
}

// 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i := 5; i*i <= n; i++ {
if n%i == 0 {
return false
}
}

return true
}

func main() {

// 获取小于1,000,000的所有质数
primes := []int{2}
for i := 3; i < 1000000; i += 2 {
if isPrime(i) {
primes = append(primes, i)
}
}

curMaxLength := 0  // 当前的最大长度
curStartPrime := 0 // 当前的最大长度时，起始的质数
curMaxSum := 0     // 当前的最大长度时，连续质数的和

// 遍历寻找
for i := 0; i < len(primes); i++ {
length, primeSum, sum := 1, primes[i], primes[i]

for j := i + 1; j < len(primes); j++ {
sum += primes[j]
if sum > 1000000 {
break
}
if isPrime(sum) {
length = j - i + 1
primeSum = sum
}
}

// 如果找到更长的链，记录
if length > curMaxLength {
curMaxLength = length
curStartPrime = primes[i]
curMaxSum = primeSum

fmt.Printf("find a longer one, start at %d, length is %d, sum is %d\n", curStartPrime, curMaxLength, curMaxSum)
}
}
}


### Python

import math

def isPrime(n):
if n <= 1 : return False
if n == 2 or n == 3 : return True
if n % 2 == 0 : return False

# 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻
# 即大于等于5的质数一定是 6x-1 和 6x+1，6x+2 ~ 6x+4 一定不是质数
# 即大于等于5的质数一定满足 n%6==1 or n%6==5
# https://blog.csdn.net/songyunli1111/article/details/78690447
if n % 6 != 1 and n % 6 != 5 : return False

# 从 [5, sqrt(n)] 遍历寻找是否是其因数
for i in range(5, int(math.sqrt(n)) + 1):
if n % i == 0 : return False

return True

# 获取小于1,000,000的所有质数
primes = [2]
for i in range(3, 1000000, 2) :
if isPrime(i) :
primes.append(i)

curMaxLength = 0  # 当前的最大长度
curStartPrime = 0 # 当前的最大长度时，起始的质数
curMaxSum = 0     # 当前的最大长度时，连续质数的和

# 遍历寻找
for i in range(0, len(primes)) :
length, primeSum, sum = 1, primes[i], primes[i]
for j in range(i + 1, len(primes)) :
sum += primes[j]
if sum > 1000000 :
break
if isPrime(sum) :
length = j - i + 1
primeSum = sum

# 如果找到更长的链，记录
if length > curMaxLength :
curMaxLength = length
curStartPrime = primes[i]
curMaxSum = primeSum
print("find a longer one, start at", curStartPrime, "length is", curMaxLength, "sum is", curMaxSum)

## 答案

997651

find a longer one, start at 2, length is 536, sum is 958577
find a longer one, start at 5, length is 539, sum is 978037
find a longer one, start at 7, length is 543, sum is 997651

# Problem 44 Pentagon numbers

## Problem 44: Pentagon numbers

https://projecteuler.net/problem=44

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

## 方法1 遍历五边形数D，对每个D，寻找两个五边形数pk和pj，满足 pk-pj = D,pk+pj 也是五边形数，找到则停止，输出D

x1 = (1 + sqrt(1+6n)) / 6
x2 = (1 - sqrt(1+6n)) / 6

// 判断 n 是否是 PentagonNumber
// 即，存在正整数 x，使得 n = x(3x-1)/2
bool isPentagonNumber(int64_t n)
{
double x = (1 + sqrt(1+24*n)) / 6 ;
if(x > 0 && (x - int64_t(x)) == 0){ // (x - int64_t(x)) == 0 表明x是整数
return true;
}

return false;
}

for(i = 1; ; i++){
D = i*(3*i-1)/2;
// 找到两个五边形数 pk, pj，满足 pk - pj = D，且 pk + pj 也是五边形数。
// 即遍历 pk， 判断 pj 和 pk+pj 是否是五边形数
}

for(i = 1; ; i++){
D = i*(3*i-1)/2;
// 找到 pk, pj，满足 pk - pj = D，且 pk + pj 也是五边形数。

int64_t n = (D+2)/3 + 1; //  D <= 3n-2 => n

for(int64_t k = i+1; k <= n; k++){
int64_t pk = k*(3*k-1)/2;
int64_t pj = pk - pi; // pj = pk - pi
if(isPentagonNumber1(pj) && isPentagonNumber1(pj+pk) ) {
printf("find: P(k)=%lld, P(j)=%lld, D=P(i)=%lld\n", pk, pj, pi);
return 0;
}
}
}


### CPP

#include <stdio.h>
#include <stdint.h>
#include <math.h>

// 判断 n 是否是 PentagonNumber
// 即，存在正整数 x，使得 n = x(3x-1)/2
bool isPentagonNumber(int64_t n)
{
double x = (1 + sqrt(1+24*n)) / 6 ;
if(x > 0 && (x - int64_t(x)) == 0){ // (x - int64_t(x)) == 0 表明x是整数
return true;
}

return false;
}

int main()
{
for(int64_t i = 1; ; i++){

// 找到两个五边形数 pk, pj，满足 pk - pj = D，且 pk + pj 也是五边形数。
// 即遍历 pk， 判断 pj 和 pk+pj 是否是五边形数
int64_t D = i*(3*i-1)/2; // D = pi

// 方程[2]
int64_t n = (D+2)/3 + 1; // 3n-2 = D => n = (D+2)/3

// 假设 pk - pj = pi = D 则： k = i~n，j=1~n-1
// 即遍历 pk， 判断 pj 和 pk+pj 是否是五边形数
for(int64_t k = i+1; k <= n; k++){

int64_t pk = k*(3*k-1)/2;
int64_t pj = pk - D; //

if(isPentagonNumber(pj) && isPentagonNumber(pj+pk) ) {
printf("find: P(k)=%lld, P(j)=%lld, D=P(i)=%lld\n", pk, pj, D);
return 0;
}
}
}

return 0;
}

## 方法2 论坛中其它网友的答案

solved = False
pentagonalist = set()

i = 0
while solved != True:
i += 1
psum = int(i*(3*i-1)/2)
pentagonalist.add(psum)
for pj in pentagonalist:
pk = psum - pj
if pk in pentagonalist and (pk - pj) in pentagonalist:
print("the answer is:", abs(pk-pj))
solved = True

#include <stdio.h>
#include <stdint.h>
#include <math.h>

// 判断 n 是否是 PentagonNumber
// 即，存在正整数 x，使得 n = x(3x-1)/2
bool isPentagonNumber(int64_t n)
{
double x = (1 + sqrt(1+24*n)) / 6 ;
if(x > 0 && (x - int64_t(x)) == 0){ // (x - int64_t(x)) == 0 表明x是整数
return true;
}

return false;
}

int main()
{
//
for(int64_t k = 1; ; k++){
int64_t pk = k*(3*k-1)/2;

for(int64_t j = 1; j < k; j++){
int64_t pj = j*(3*j-1)/2;

// 判断 pk - pj 和 pk + pj 是否是五边形数
if(isPentagonNumber(pk-pj) && isPentagonNumber(pk+pj)){
printf("find: P(k)=%lld, P(j)=%lld, D=P(i)=%lld\n", pk, pj, pk-pj);
return 0;
}
}
}
return 0;
}

## 答案

5482660

P(k)=7042750, P(j)=1560090, D=P(i)=5482660