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 次方

求: 有多少个 n 位的正整数,它也是某个数的 n 次方。

思路:可以用穷举法解决,但是需要知道穷举的边界。

如果 xn 是一个 n 位数,则 10n-1 ≤ xn < 10n,x 必然小于10,所以 10n-1 的增速比 xn 快,所以在某个时刻,10n-1 大于 xn 后,后面就不可能找到满足上面不等式的解了。

所以,遍历 x = 1~9,然后穷举 x^n ,如果发现 x^n 是 n 位数,则cnt++;如果发现 x^n 小于 10^(n-1),则结束,继续搜索下一个x。最终输出cnt.

方法

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

使用大数包 math/big

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

使用我们自己封装的大数运算函数(add, mul),详见 Problem 16 Power digit sum

基于 add,mul 实现 pow() 函数,如此,就能和 python\golang 一样处理本题的大数问题了

#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

这 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的立方)

事实上,41063625 是最小的、可以排列出3个立方数的立方数。

找到最小的立方数,它通过数字重排列可以得到 5 个立方数。

方法 按位数遍历

一个数对应的排列的位数,肯定和它的位数相等,即8位数的排列,必然也是8位数
我们从1位数开始,先找到所有位数为 1 的立方数,判断其中是否有5个立方数包含的数字相同,如果有则输出,结束。如果没有,则继续判断2位数。依次类推,直到结束。

这里的关键在于:如何判断一组数中,有5个数包含的数字相同,并且获取这5个数。方法如下:

(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

这5个数为:127035954683, 352045367981, 373559126408, 569310543872, 589323567104

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 这样的格式。

找到 6 个 4 位的数,他们满足上述的循环格式(即前一个数的后两位数字,是后一个数的前两位,末尾的数的后两位是第一个数的前两位),并且,他们分别是三角形数,四边形数,五边形数,六边形数,七边形数,八边形数。

满足条件的 6 个数只有一组,求这个 6 个数的和。

方法 遍历判断

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

然后,将所有的数保存到 set 中完成去重,并且排序,用于后续的遍历。

假设最终的6个数为 x1,x2,x3,x4,x5,x6,x1 从 set 中遍历,然后找出所有 set 中所有前两位数字等于 x1 后两位数字的数,作为 x2 的备选集合, 然后再遍历 x2 的备选集合,找到set中所有前两位数字等于 x2 后两位数字的数,作为 x3 的备选集合,依次类推。可以找到一组 x1,x2,x3,x4,x5,x6,满足前一个的后两位是后一个的前两位。 再判断 x6 的后两位是否是 x1 的前两位,如果是,则 x1~x6 满足循环的要求。

题目要求最终的6个数,必须包含三角形数,四边形数,五边形数,六边形数,七边形数,八边形数。但因为一个数可能是多种类型的,那么就需要判断各种情况下,能否满足每种类型的数都存在。 采用 containsAllKinds(nums, kinds) 递归实现。

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.

分析

找到 5 个质数,他们任意两个拼接在形成的数(如 3和7 拼接成37,73),也是质数。找到这样的 5 个质数,它们的和最小。

方法1 尝试 + 穷举

如果使用穷举的方法,我们并不知道穷举的界限在哪。所以,可以先尝试穷举 10000 以内的所有质数,看看能否找到符合条件的 5 个质数。

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)

遍历发现,(13 5197 5701 6733 8389) 满足条件,它们的和是 26033。 但我们不能确定 26033 就是满足条件的最小的数。

因为 26033 的发现,我们便能得到遍历的界限,即我们最多只要遍历全 26033 以内的质数就可以了,因为超过了 26033 之后,即便找到了满足条件的 5 个质数,它们的和也必然比26033大,不是最小的了,不满足要求。

如果直接穷举 26033 的所有质数,运算速度还是太慢。所以需要做进一步的优化:[优化点1] 每一步都判断当前几个数的和是否超过了 26033,如果超过了,则不用继续往后了

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)

在我的机器上,运行时间约为 80s,勉强可以接受。

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

在我的机器上,运行时间约为 20s

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;
}

在我的机器上,运行时间约为 8s

答案

26033

符合条件的 5 个质数为:13, 5197, 5701, 6733, 8389

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。

理论上,秘钥的长度和明文的长度相等是最稳妥的。但实际上,我们都是使用简短易记的密码作为加密秘钥,该密码会被循环往复的用于明文的加密。

本题的任务是:p059_cipher.txt 中保存了加密后的 ASCII codes, 已知秘钥是3位的小写字母,明文中必须包含常用的英语单词,解密文件中的密文,然后统计明文中所有字符的 ASCII 值的总和。

思路
首先需要找到秘钥,如果直接遍历所有可能的话,从 "aaa" 到 "zzz" 有 26*26*26 = 17575 中可能,不可能人为的去判断每种解密结果是否合理。需要一种方法,可以快速去除明显不对的解码。

因为明文肯定是可读的,那么在解密过程中,如果出现了不可显示的字符,即 ascii < 32 或者 ascii > 126 ,那么明显是错误的,直接排除

经过这样的筛选,最终仍有 360 种可能结果,但相比于 17575 种来说,360 种可能性,还是可以人为的去判断的。最终从 360 种结果中,发现密码为 "exp" 时,解密出来的明文是有意义的。

所以,可以使用 "exp" 来解密,得到明文,再统计其中 ASCII 码的总和。

方法 如分析中的思路

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%?

分析

统计对角线上的所有数中质数的占比。 求当正方形的长度时多少时,质数的占比会小于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) 表示第 n 层的边长,TR(n) (i.e. top-right) 表示第 n 层右上角的数字,同理有 TL(n), BL(n), BR(n)
则:

边长:Edge(n) = 2n-1
右上角数:TR(n)
左上角数:TL(n) = TR(n) + Edge(n) - 1 = TR(n)+2n-2
左下角数:BL(n) = TL(n) + Edge(n) - 1 = TR(n)+4n-4
右下角数:BR(n) = BL(n) + Edge(n) - 1 = TR(n)+6n-6

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

即:TR(n) = TR(n-1)+8n-14

其中 TR(1) = 1, TR(2) = 3, TR(3) = 13, TR(4) = 31, ...

至此,我们可以知道每层的四个角的数,继而可以遍历判断质数。

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

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/2 替换为 1/(2+1/2),所以

第 1 次扩展结果: fraction = 1 + 1/2
第 2 次扩展结果: fraction = 1 + 1/(2+1/2)
第 3 次扩展结果: fraction = 1 + 1/(2+1/(2+1/2))
第 4 次扩展结果: fraction = 1 + 1/(2+1/(2+1/(2+1/2)))
第 5 次扩展结果: fraction = 1 + 1/(2+1/(2+1/(2+1/(2+1/2))))
第 6 次扩展结果: fraction = 1 + 1/(2+1/(2+1/(2+1/(2+1/(2+1/2)))))
...

做 n 次拓展,相当于对 fraction 做 n 次替换。

接下来,就需要计算 fraction 的值。以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) 即可

重复上述步骤,直到找不到 1/(a+b/c) 格式的算式,此时 fraction 的格式必然为 1+a/b,即 (a+b)/b,分子为 a+b, 分母为b。 判断分子分母的长度。如果分子比分母长,则统计值+1。

对 1~1000 的每一个数,做上述处理,获取最终的统计值,即为答案

这里有个注意点: 上述过程中的 a,b,c,d 都可能是大数,必须做大数处理

方法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 才能得到一个回文数。
尽管没被证明,但有些数,比如 196,无论迭代多少次(次数 >= 1),都不会生成一个回文数,这样的数被称为 Lychrel number
注意:4994 虽然本身是回文数,但是它仍然是Lychrel number,因为它经过1~N次迭代,都是无法得到回文数的。

对于本题,如果一个数迭代50次之后,还没有得到回文数,则认为它是 Lychrel number,统计 10000 一下的所有Lychrel number的个数。

思路:存在大数问题

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

使用 vector 存储数字的每一位

#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

分析

扑克游戏

扑克游戏中,一手牌包括5张卡牌,并且等级(rank)从低到高排序如下:

  • 高牌,即大散牌(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 的同花顺

卡牌的数值是:2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

如果两个玩家的手牌等级一样,则数值更高的玩家获胜,如 一对八 赢 一对五。 如果玩家的手牌等级打平,比如都有一对 Q,那么则比较散牌中的最大值,如果散牌最大值相等,则继续比较次大值,依次类推。

题中给出了一些手牌和比较的结果。

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

每个玩家的手牌没有特定的顺序,每手牌都有一个明显的赢家。

求: 玩家1 赢的次数

方法

题目比较简单,只是实现的代码较多。封装了两个类,CardHand 分别表示一张牌和一手牌。 依次读取文件的每一行,分成两手牌 player1 和 player2, 比较两手牌的大小即可。

手牌的比较,实现在 Hand.Compare() 中。

#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 个数选择方案的总数。 当 1 ≤ n ≤ 1000时, 统计有多少个 C(n,r) 的值超过了 1 百万。

思路很简单直接,难点是如果采用非python的实现,计算阶乘时存在大数问题。所以需要对 C(n,r) 的计算做优化,避免大数问题。

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

然后再对分子的每个乘数,依次和分母中的所有乘数做约分。因为C(n,r) 最终必然是整数,所以约分到最后,分母中所有乘数都可以被约分成1,直接计算分子的乘积即可。并且,计算分子乘积的过程中,为了避免大数问题,我们不需要计算最终的结果,只要计算判断 > 1000000 即可。

方法 通过约分,避免大数

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

可以复用上面的方法,也可以直接计算,因为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.

分析

找到最小的整数 x,满足 x, 2x, 3x, 4x, 5x, 6x 包含相同的数字

题目相对比较简单,可做简单的遍历即可。 但是为了提高遍历的效率,我们不用遍历每一个数。

方法 遍历求解

从 x = 11 往上遍历,对于每一个 x,做如下处理:

  • (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.

分析

使用同样的数字,替换一个数中的某些位(不一定是相邻位),可以生成一组质数,这组质数称为一个 family. 如果这组质数包含 n 个质数,则称为 n prime value family.

找到最小的一个质数,它可以生成一个 8 prime value family。

方法

从 n=11 往上遍历,对每一个n,做如下处理:

  • (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个质数,如果包含,则找到了答案,结束

这里的核心点在于:getChoices(len,cnt) 的实现方法,即获取从 len 个位置中,选出 cnt 个位置的所有选法。

方法(1): 可以使用递归的方式来实现 getChoices
方法(2): 也可以使用 std::next_permutaion 来实现; 从 len 中选择 cnt 个位置,相当于对数组 [0,0,0...1,1,1] 做全排列

对每个数,都需要调用 getChoices,所以可以事先把getChoices的结果保存下来,需要时,直接使用,而不是每次都调用。
本题解题速度还可以,故没有用这种优化。

CPP

方法(1) 使用递归实现的 getChoices

#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;
}

方法(2) 使用 std::next_permutaion 实现 getChoices

替换方法(1) 中的 getChoices 函数即可

// 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

方法(1) 使用递归实现的 getChoices

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
                }
            }
        }
    }
}

方法(2) 使用 nextPermutaion 实现 getChoices


// 获取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?

分析

找到小于1000000的一个质数,它能被写成连续的质数的和,并且这个连续的质数最长

方法1 遍历统计

保存1000000以下的所有质数到 primes,然后遍历 primes 统计最长的连续质数和

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?

分析

通过公式 Pn=n(3n−1)/2 生成的数称为五边形数(Pentagonal number)。

找到两个五边形数 Pj 和 Pk,他们的和是五边形数,他们的差也是五边形数,并且他们的差的绝对值最小。 求这个最小的差的绝对值。

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

核心点1,解决五边形数的判断问题

判断一个数 n 是否是五边形数,只要判断 n = x(3x-1)/2 的方程,有没有正整数解,即 n = x(3x-1)/2 => 3x^2 - x - 2n = 0 [1]
针对方程[1], 根据一元二次方程的求根公式 x1,x2 = (-b +- sqrt(b^2 - 4ac))/2a,带入带入 a=3,b=-1,c=-2n 得到

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

对于 x2,必然不会是正整数解,所以只需要判断 x1 即可。 实现算法如下:

// 判断 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;
}

核心点2,解决遍历的范围问题

从 D = 1,5,12... 开始遍历,判断是否存在两个五边形数 pk 和 pj,满足 pk - pj = D,且 pk + pj 也是五边形数,一旦找到满足条件的pk和pj,则结束。

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

那么如何确定 k 的范围呢?

因为 Pn - Pn-1 = 3n-2,所以随着n的增大,相邻两个五边形数的差值也就越大,相邻的最大差值不能超过D,如果超过了D,必然不满足条件。即 Pn - Pn-1 <= D,即 3n-2 <= D,即 n <= D+2/3 [2]

由方程[2] 就能确定 k 的范围了。 假设 D = pi,则 k 属于 [i+1, n]。 继而 pj = pk-D, 判断 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;
}

在我本机运行时,耗费了19s,才计算出答案。 所以该方法对于 golang/python 不太适用。

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

第一种,根据 pk+pj 最小来做遍历

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

代码可以看懂,即假设 psum = pk + pj。不断递增 psum,找满足条件的pk和pj. 不过有一点没明白,怎么确定找到的 pk-pj 就是最小的。

从代码看,程序返回时,只能确定 psum = pk+pj 最小,如果确定 pk-pj 也是最小的?

第二种,根据pk最小,来做遍历

#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;
}

和上面同样的问题,pk最小,怎么确定 pk-pj 就是最小的?

两种方法引用至此,但是我没有看懂。

答案

5482660

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