//: [Previous](@previous)
// Xcode で Editor メニュー > Show Render Markup でお読みください
//import UIKit
import Foundation
/*:
 # 中学３年の数学
 */
/*:
 ## 式の計算
 */
/*:
 ### (𝑎 + 𝑏)^𝑛, (𝑎 − 𝑏)^𝑛 の展開

 係数は「二項係数」になる。これは、先に「組み合わせの数」で示した「パスカルの三角形」に他ならない

 𝑎 の指数が 𝑛 - 𝑘、𝑏 の指数が 𝑘 となる
 
 * (𝑎 + 𝑏)⁰ = 1
 * (𝑎 + 𝑏)¹ = 𝑎 + 𝑏
 * (𝑎 + 𝑏)² = 𝑎² + 2𝑎𝑏 + 𝑏²
 * (𝑎 + 𝑏)³ = 𝑎³ + 3𝑎²𝑏 + 3𝑎𝑏² + 𝑏³
 * (𝑎 + 𝑏)⁴ = 𝑎⁴ + 4𝑎³𝑏 + 6𝑎²𝑏² + 4𝑎𝑏³ + 𝑏⁴
 * (𝑎 + 𝑏)⁵ = 𝑎⁵ + 5𝑎⁴𝑏 + 10𝑎³𝑏² + 10𝑎²𝑏³ + 5𝑎𝑏⁴ + 𝑏⁵
 * (𝑎 + 𝑏)⁶ = 𝑎⁶ + 6𝑎⁵𝑏 + 15𝑎⁴𝑏² + 20𝑎³𝑏³ + 15𝑎²𝑏⁴ + 6𝑎𝑏⁵ + 𝑏⁶
 * (𝑎 + 𝑏)⁷ = 𝑎⁷ + 7𝑎⁶𝑏 + 21𝑎⁵𝑏² + 35𝑎⁴𝑏³ + 35𝑎³𝑏⁴ + 21𝑎²𝑏⁵ + 7𝑎𝑏⁶ + 𝑏⁷

 ４乗あたりまで覚えておくと、展開だけでなく、因数分解にも役立つ

 𝑏 を −𝑏 に置き換えれば、(𝑎 − 𝑏)^𝑛 も得られる
 
 * (𝑎 − 𝑏)⁰ = 1
 * (𝑎 − 𝑏)¹ = 𝑎 − 𝑏
 * (𝑎 − 𝑏)² = 𝑎² − 2𝑎𝑏 + 𝑏²
 * (𝑎 − 𝑏)³ = 𝑎³ − 3𝑎²𝑏 + 3𝑎𝑏² − 𝑏³
 * (𝑎 − 𝑏)⁴ = 𝑎⁴ − 4𝑎³𝑏 + 6𝑎²𝑏² − 4𝑎𝑏³ + 𝑏⁴
 * (𝑎 − 𝑏)⁵ = 𝑎⁵ − 5𝑎⁴𝑏 + 10𝑎³𝑏² − 10𝑎²𝑏³ + 5𝑎𝑏⁴ − 𝑏⁵
 * (𝑎 − 𝑏)⁶ = 𝑎⁶ − 6𝑎⁵𝑏 + 15𝑎⁴𝑏² − 20𝑎³𝑏³ + 15𝑎²𝑏⁴ − 6𝑎𝑏⁵ + 𝑏⁶
 * (𝑎 − 𝑏)⁷ = 𝑎⁷ − 7𝑎⁶𝑏 + 21𝑎⁵𝑏² − 35𝑎⁴𝑏³ + 35𝑎³𝑏⁴ − 21𝑎²𝑏⁵ + 7𝑎𝑏⁶ − 𝑏⁷

 𝑏 が奇数個の積の項がマイナスで、偶数個の積の項がプラス、それらは交互となる
 */

func 階乗(n: Int) -> Int {
    var N = 1;
    for i in stride(from: n, through: 1, by: -1) {
        N *= i
    }
    return N
}
func 二項係数(n: Int, k: Int) -> Int {
    return 階乗(n: n)/(階乗(n: n-k)*階乗(n: k))
}
print("二項係数")
print(#"n\k\#t"#, terminator: "")
for k in 0...7 {
    print(k, terminator: "\t")
}
print("")
for n in 0...7 {
    print(n, terminator: "\t")
    for k in 0...n {
        print("\(二項係数(n: n, k: k))", terminator: "\t")
    }
    print("")
}
print("")
/*
n\k	0	1	2	3	4	5	6	7
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
 */ // 特にこれを「パスカルの三角形」と呼ぶ
print("(a + b)^n - 二項係数")
print("n")
for n in 0...7 {
    print(n, terminator: "\t")
    for k in 0...n {
        let 係数 = 二項係数(n: n, k: k)
        print("\(係数 == 1 && n != 0 ? "" : "\(係数)")\(n-k == 0 ? "" : n-k == 1 ? "a" : "a^\(n-k)")\(k == 0 ? "" : k == 1 ? "b" : "b^\(k)")", terminator: k == n ? "\n" : " + ")
    }
}
print()
/*
n
0	1
1	a + b
2	a^2 + 2ab + b^2
3	a^3 + 3a^2b + 3ab^2 + b^3
4	a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4
5	a^5 + 5a^4b + 10a^3b^2 + 10a^2b^3 + 5ab^4 + b^5
6	a^6 + 6a^5b + 15a^4b^2 + 20a^3b^3 + 15a^2b^4 + 6ab^5 + b^6
7	a^7 + 7a^6b + 21a^5b^2 + 35a^4b^3 + 35a^3b^4 + 21a^2b^5 + 7ab^6 + b^7
 */


/*:
 ### 素因数分解
*/
/*:
 #### 素数
 
 その数自身より小さい自然数(ここでは0は含めない)の積で表すことができない自然数のこと
 
 言い換えれば、その数自身と1のほかに約数がないもの
 
 よって、1は素数にふくめない
 */
func 素数列の生成(個数: Int) -> [UInt64] { // エラトステネスのふるい
    var 素数列 = [UInt64]()
    var x = UInt64(3) // 最初の奇数

    素数列.append(UInt64(2)) // 偶数で唯一の素数
    while 素数列.count < 個数 {
        if 素数列.firstIndex(where: { x % $0 == 0 }) == nil {
            素数列.append(x)
        }
        x += 2 // 次の奇数、4以上の偶数は明らかに素数ではないので、調べない
        //x += 1 // もし、このように偶数をも調べても動作はするが、無駄である
    }
    return 素数列
}
print("素数列")
print(素数列の生成(個数: 1000))
/*:
 #### 素因数分解
 
 積をつくっている１つ１つの自然数を、もとの数の「因数」という
 
 素数である因数を「素因数」という
 
 「素因数分解」とは、もとの数を小さい素数からわっていって素数の因数の積に分解することである
 */
func 素因数分解(数: UInt64) -> [(因数: UInt64, 指数: Int)] {
    var 素因数指数列 = [(因数: UInt64, 指数: Int)]()

    switch 数 {
    case 1:
        素因数指数列 = [] // (素因数: 1, 1) つまり 1^1 としたいところだが、1 は素数ではないので、空
    case 2:
        素因数指数列 = [(因数: 2, 指数: 1)]
    case 3:
        素因数指数列 = [(因数: 3, 指数: 1)]
    default:
        var n = 数
        let 最大値 = UInt64(floor(sqrt(Double(数))))

        for i in 2...最大値 {
            if n % i != 0 {
                continue
            }
            var j = 0
            repeat {
                j += 1
                n = n / i
            } while n % i == 0
            素因数指数列.append((因数: i, 指数: j))
        }
        if n > 最大値 {
            素因数指数列.append((因数: n, 指数: 1))
        }
    }
    return 素因数指数列
}
func 因数指数列合成(因数指数列: [(因数: UInt64, 指数: Int)]) -> UInt64 {
    var n = UInt64(1)
    for (j, k) in 因数指数列 {
        n *= UInt64(pow(Double(j), Double(k)))
    }
    return n
}
for n: UInt64 in 1...10/*8000*/ {
    let A = 素因数分解(数: n)
    print(n, 因数指数列合成(因数指数列: A), A)
}
/*:
 #### 最大公約数
 
 それぞれの自然数を素因数分解し、
 
 共通の因数の積が「最大公約数」である
 
 #### 最小公倍数
 
 そして、はみ出した素因数を最大公約数にかけると「最小公倍数」となる
 */
func 最大公約数(_ x: Int64, _ y: Int64) -> Int64 {
    var x = x, y = y
    while y != 0 { // x を y で割った余りと y を交換して、その余りが 0 になるまで続けたときの
        (x, y) = (y, x % y)
    }
    return x // 最後の x が最大公約数である
}
func 最小公倍数(_ x: Int64, _ y: Int64) -> Int64 {
    return x * y / 最大公約数(x, y)
}
func 最大公約数(_ x: [Int64]) -> Int64 {
    if var 公約数 = x.first {
        for y in x.dropFirst() {
            公約数 = 最大公約数(y, 公約数)
        }
        return 公約数
    }
    else {
        return 0
    }
}
func 最小公倍数(_ x: [Int64]) -> Int64 {
    if var 公倍数 = x.first {
        for y in x.dropFirst() {
            公倍数 = 最小公倍数(y, 公倍数)
        }
        return 公倍数
    }
    else {
        return 0
    }
}
for (x, y) in [
    (42, 54),
    ] {
    let x = Int64(x), y = Int64(y)
    print(x, y, "最大公約数: \(最大公約数(x, y)), 最小公倍数: \(最小公倍数(x, y))")
}
for x in [
    // 例題19
    [Int64]([ 42, 54 ]),
    [Int64]([ 16, 28, 40 ]),
    // 練習19
    [Int64]([ 28, 98 ]),
    [Int64]([ 36, 54, 135 ]),
    ] {
    print(x, "最大公約数: \(最大公約数(x)), 最小公倍数: \(最小公倍数(x))")
}

//: [Next](@next)