C#で組み合わせを求める

いわゆる_nC_k

　「色違いの5個のボールが袋に入っている。その袋から3つ取り出す場合の組み合わせの数を求めよ」
という中学数学に出てきそうな問題を解くためのやつ。
表記としては₅C₃と書く。

計算

　₅C₃では次のようになる。

₅C₃ = (5×4×3)/(3×2×1) = 10

　_nC_k = _nC_n-k なので、計算量が少ない方を選べばいい。

できたもの

/// <summary>
/// 組み合わせの数を求める
/// </summary>
/// <param name="n">要素数</param>
/// <param name="k">選ぶ数</param>
/// <returns>nCk</returns>
public BigInteger Count(long n, long k)
{
    if (k > n - k) k = n - k;

    var numerator = new BigInteger(1);
    var denominator = new BigInteger(1);
    var tmp = 1L;

    for (int count = 1; count <= k; count++)
    {
        numerator *= n;
        n--;

        denominator *= tmp;
        tmp++;
    }

    return numerator / denominator;
}

なんでおっさんはすぐBigIneger使うん？

　答えがすぐに爆発するからやで。

Count(600, 25) = 110400461164029879580081326850533034570953024

　こんなふうに、ちょっと大きい数字を与えただけでintの範囲を軽く超えてくる。
もうBigInteger使うしかないでしょ。

組み合わせとは

ja.wikipedia.org

Combinationの語源

www.etymonline.com

組合せ数学 (岩波科学ライブラリー)

組合せ論の精選102問 (数学オリンピックへの道)

ヴァン・リント&ウィルソン 組合せ論 上

Project Euler : Problem 55 『Lychrel numbers』

問題

projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?Problem+55

総当たりでいいんじゃない？

　しばらく考えていたが、10000以下を調べる程度なら総当たりで十分だと思った。

コード

using System;
using System.Linq;
using System.Numerics;

namespace test
{
    class Program
    {
        //最大計算回数
        static readonly int CalcMaxCount = 50;

        static readonly int StartNumber = 1;
        static readonly int CountNumber = 10000;

        static void Main(string[] args)
        {
            var count = CountLychrelNumbers();
            Console.WriteLine($"Count {count}");
        }

        /// <summary>
        /// リクレル数をカウント
        /// </summary>
        static int CountLychrelNumbers()
        {
            var count = 0;

            foreach (var num in Enumerable.Range(StartNumber, CountNumber))
            {
                if (IsLychrelNumber((BigInteger)num)) count++;
            }

            return count;
        }

        /// <summary>
        /// リクレル数か判定する
        /// </summary>
        static bool IsLychrelNumber(BigInteger n)
        {
            foreach (var i in Enumerable.Range(1, CalcMaxCount))
            {
                var rn = ReverseNumber(n);
                var sum = n + rn;

                if (IsPalindromicNumber(sum)) return false;
                else n = sum;
            }

            return true;
        }

        /// <summary>
        /// 回文数か判定する
        /// </summary>
        static bool IsPalindromicNumber(BigInteger n)
        {
            var s = n.ToString();
            var l = s.Length / 2;

            foreach (var i in Enumerable.Range(0, l))
            {
                if (s[i] != s[s.Length - 1 - i]) return false;
            }

            return true;
        }

        /// <summary>
        /// 数値を反転させる
        /// </summary>
        static BigInteger ReverseNumber(BigInteger n)
        {
            var rs = ReverseString(n.ToString());

            return BigInteger.Parse(rs);
        }

        /// <summary>
        /// 文字列を反転させる
        /// </summary>
        static string ReverseString(string s)
        {
            var rs = string.Empty;

            foreach (var i in Enumerable.Range(0, s.Length).Reverse())
                rs += s[i];

            return rs;
        }
    }
}

キリンねるねんりき (回文まんが絵本)

回文さがし だんぱつパンダの冒険

たのしい回文:くるくる回るアタマをつくろう

Project Euler : Problem 52 『Permuted multiples』

問題

projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2052

6倍した時桁上がりしない最上位桁

　6倍した時に1倍と同じ数字が使われているということは、最上位桁が桁上がりしない事と同じ意味。
仮に最上位桁が2だとすると、2×6=12で桁上がりするのでダメ。
2未満というと1しかないので、最上位桁は1

6倍した時に全体の桁が増えない最上位桁の次の桁

　1?…×6の時に最上位桁が桁上がりしないような?の最大値を知りたい。
仮に?が6だと16…×6=96…でいけるが、17×6は102…となってしまうことから?の最大値は6以下。

上限を求める

　16…x6=96…より、次の桁は6倍した時桁上がりしないように40未満になってほしい。
ということは6が最大値なので、値は166…になる。
見て分かるように以降6が続くので166…6が調べる上限。

下限を調べる

　探索の下限として1…を考える。
トップに1が含まれるということは、2～6倍するために桁のどこかに2～6が含まれないといけないはず。
つまり123456の6桁から探索を始めるべき…？(自信ない)

探索範囲の遷移は

　123456～166666→1123456～1666666という感じに変わっていく。

C#でのintの最大値

　int.MaxValueは2147483647で10桁あるからまぁ大丈夫でしょう多分。

同じ数字が使われているか確認する方法

　値を文字列化→char配列化→ソート→SequenceEqualで判定
もっといい方法があるかも。

コード

using System;
using System.Diagnostics;
using System.Linq;

namespace eu
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();

            Problem52();

            sw.Stop();
            Console.WriteLine($"Time {sw.ElapsedMilliseconds}");
        }

        private static void Problem52()
        {
            int startNum = 123456;
            int addNum = 100000;
            int maxNum = 166666;

            for (int i = startNum; i <= maxNum; i++)
            {
                var s1 = i.ToString().ToCharArray();
                var s2 = (i * 2).ToString().ToCharArray();
                var s3 = (i * 3).ToString().ToCharArray();
                var s4 = (i * 4).ToString().ToCharArray();
                var s5 = (i * 5).ToString().ToCharArray();
                var s6 = (i * 6).ToString().ToCharArray();

                Array.Sort(s1);
                Array.Sort(s2);
                Array.Sort(s3);
                Array.Sort(s4);
                Array.Sort(s5);
                Array.Sort(s6);

                if (s1.SequenceEqual(s2) & s3.SequenceEqual(s4) & s5.SequenceEqual(s6))
                {
                    if (s2.SequenceEqual(s3) & s4.SequenceEqual(s5))
                    {
                        Console.WriteLine($"{i}");
                        Console.WriteLine($"{i * 2}");
                        Console.WriteLine($"{i * 3}");
                        Console.WriteLine($"{i * 4}");
                        Console.WriteLine($"{i * 5}");
                        Console.WriteLine($"{i * 6}");

                        break;
                    }
                }

                if (i == maxNum)
                {
                    //初期値の更新
                    addNum = addNum * 10;
                    startNum = startNum + addNum - 1;

                    //最大値の更新
                    maxNum = maxNum * 10 + 6;
                }
            }
        }
    }
}

答え

142857

Brute Force

同じ遺伝子の３人の他人(字幕版)

群れはなぜ同じ方向を目指すのか?

合同数を求めようと思った

tsujimotter.hatenablog.com
　この記事を読んで合同数を求めてみようと思った。

ja.wikipedia.org
Wikipediaをさらりと読んで参考にせずぺぺっと書いて動かしてみた

コード(C#)

using System;
using System.Collections.Generic;

namespace ConsoleApp2
{
    class Program
    {
        static void Main()
        {
            Edge a = new Edge();
            Edge b = new Edge();
            Edge c = new Edge();
            List<long> congruum = new List<long>();

            for (int s = 1; s < 100; s++)
            {
                for (a.m = 1; a.m <= 100; a.m++)
                {
                    for (a.c = 1; a.c <= 100; a.c++)
                    {
                        //面積を求める式を変形して辺bを求める
                        b.c = 2 * s * a.m;
                        b.m = a.c;

                        if (CalcEdge(a, b, c) == true)
                        {
                            if (congruum.Contains(s) == false)
                            {
                                Console.WriteLine($"{a.c}/{a.m}, {b.c}/{b.m}, {c.c}/{c.m}, {s}");

                                congruum.Add(s);
                            }
                        }
                    }
                }
            }


            congruum.Sort();

            foreach (var item in congruum)
            {
                Console.WriteLine(item);
            }
        }

        private static bool CalcEdge(Edge a, Edge b, Edge c)
        {
            //斜辺の長さを求める計算
            var cu = a.c * a.c * b.m * b.m + b.c * b.c * a.m * a.m;
            var mu = a.m * a.m * b.m * b.m;
            //2乗の値になっているのでルートを取る
            c.c = (long)(Math.Sqrt(cu));
            c.m = (long)(Math.Sqrt(mu));
            //ルートをとった結果が整数か
            long cf = cu - c.c * c.c;
            long mf = mu - c.m * c.m;

            return (cf == 0 & mf == 0);
        }
    }

    public class Edge
    {
        //分母と分子
        public long m;
        public long c;
    }
}

出力

3/2, 20/3, 41/6, 5
3/1, 12/3, 15/3, 6
24/5, 70/24, 674/120, 7
21/2, 56/21, 455/42, 14
4/1, 30/4, 34/4, 15
3/1, 40/3, 41/3, 20
12/1, 42/12, 150/12, 21
33/35, 1540/33, 53911/1155, 22
6/1, 48/6, 60/6, 24
48/5, 280/48, 2696/240, 28
5/1, 60/5, 65/5, 30
24/1, 68/24, 580/24, 34
5/2, 156/5, 313/10, 39
40/3, 246/40, 1762/120, 41
20/1, 90/20, 410/20, 45
9/1, 108/9, 135/9, 54
21/1, 112/21, 455/21, 56
8/1, 120/8, 136/8, 60
35/4, 504/35, 2359/140, 63
12/1, 130/12, 194/12, 65
15/1, 140/15, 265/15, 70
45/1, 156/45, 2031/45, 78
6/1, 160/6, 164/6, 80
7/1, 168/7, 175/7, 84
77/6, 1020/77, 8521/462, 85
66/35, 6160/66, 215644/2310, 88
12/1, 192/12, 240/12, 96

5
6
7
14
15
20
21
22
24
28
30
34
39
41
45
54
56
60
63
65
70
78
80
84
85
88
96

　歯抜け状態だけど合同数になるものは出力されてる。