算数、いや数学を習いました。

数学はどうやらおもしろいらしいという話を聞きました。
完全文系のわたしは高校で数1Aまでしかやっておらず、また完全に覚えていません。そのくらいのレベル感です。

なにしたの

問題を出してもらい、それをやりました。
結局解けず解説を聞いて理解したところをまとめます。

なお、ネタとしては「等差数列」というものらしいです🙏

動作環境

問題

全文を掲載します。皆さんもぜひやってみてください。

from unittest import TestCase, main
​
​"""
★  python -m unittest sample.py  でテスト実行できます.
​
​
数字の並び 5, 11, 17, 23, 29, 35 .... を作りたい.
​
index 0番目は要素5
index 1番目は要素11
index 2番目は要素17
...省略...
​
​
問1. index番号がidx(数値型)を引数として取り、
対応する要素を求める関数 chinoppy_festival を作成して、
TestsChinoppyFestivalテストを通してください.
​
​
問2. 合計を求める関数、chinoppy_carnivalを作成して、
TestsChinoppyCarnival テストを通してください.
"""


def chinoppy_festival(idx: int) -> int:
    """indexに対応する要素を求める関数"""
    # 問題1. ここにコードを記述


def chinoppy_carnival(idx: int) -> int:
    """idxまでの、要素の合計(sum)を求める関数."""
    # 問題2. ここにコードを記述


class TestsChinoppyFestival(TestCase):
    """indexに対応する要素を求める関数のテスト."""

    def test1(self):
        input_ = 0
        expected = 5
        self.assertEqual(chinoppy_festival(input_), expected)

    def test2(self):
        input_ = 5
        expected = 35
        self.assertEqual(chinoppy_festival(input_), expected)

    def test3(self):
        import time

        s = time.time()
        input_ = 50_100_000
        result = chinoppy_festival(input_)
        f = time.time()

        expected = 300_600_005
        self.assertEqual(result, expected)
        self.assertTrue(f - s < 0.0001, "速さが足りない！！")


class TestsChinoppyCarnival(TestCase):
    """idxまでの、要素の合計(sum)を求める関数のテスト."""

    def test1(self):
        input_ = 0
        expected = 5
        self.assertEqual(chinoppy_carnival(input_), expected)

    def test2(self):
        input_ = 5
        expected = 120
        self.assertEqual(chinoppy_carnival(input_), expected)

    def test3(self):
        import time

        s = time.time()
        input_ = 50_100_000
        result = chinoppy_carnival(input_)
        f = time.time()

        expected = 7_530_030_400_800_005
        self.assertEqual(result, expected)
        self.assertTrue(f - s < 0.0001, "速さが足りない！！")


if __name__ == "__main__":
    main()

問題を見て、「5, 11, 17, 23, 29, 35」と順番に6ずつ増えていくんだな、ということが分かります。

誤答

「問1. 対応する要素を求める関数」はテストを通すことができました。しかし、「問2. 合計を求める関数」の最後テストを通すことができませんでした。
0.0001 がassertの条件のため、「ループは回さずに解けるはず」と思いましたが、テストを通すことはできませんでした。

以下がわたしの問1の答えです。

def chinoppy_festival(idx: int) -> int:
    """indexに対応する要素を求める関数"""
    # 問題1. ここにコードを記述
    return 5 * (idx + 1) + idx

初期値の「5」に対し、 index+1 を掛け、indexの値を足します。
indexが0の場合、 5 * (0 + 1) + 0 = 5 となります。
indexが1の場合、 5 * (1 + 1) + 1 = 11 となります。
indexが5の場合、 5 * (5 + 1) + 5 = 35 となります。

一緒にやった算数仲間の問1の答えは以下。

def chinoppy_festival(idx: int) -> int:
    """indexに対応する要素を求める関数"""
    # 問題1. ここにコードを記述
    return (idx + 1) * 6 - 1

どちらも同じ答えになり、テストが通ることを確認しました。

続いて通らなかった問2の答えです。

def chinoppy_carnival(idx: int) -> int:
    """idxまでの、要素の合計(sum)を求める関数."""
    # 問題2. ここにコードを記述
    return sum(chinoppy_festival(i) for i in range(idx + 1))

実行結果は次のようになります。

py3.10.2 ❯ python -m unittest sample.py
..F...
======================================================================
FAIL: test3 (sample.TestsChinoppyCarnival)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jrfk/Documents/wk/sample.py", line 91, in test3
    self.assertTrue(f - s < 0.0001, "速さが足りない！！")
AssertionError: False is not true : 速さが足りない！！

----------------------------------------------------------------------
Ran 6 tests in 8.093s

FAILED (failures=1)

8.093sもかかっています。 0.001 までは遠すぎました。

ループなしで求めるために、求められる範囲の答えから規則性がないか、考えました。
0の場合5、1の場合11で16、1の場合17で23、といった具合です。

    # 0: 5
    # 1: 11 16
    # 2: 17 33
    # 3: 23 56
    # (4 + 3 + 2 + 1) * 6 - 4 = 56

(4 + 3 + 2 + 1) * 6 - 4 = 56 に仲間がたどり着いたのですが、結局 (4 + 3 + 2 + 1) のループが必要だ...というところで詰みました。

（蛇足）誤答なりの悪あがき

ムダだと分かっていましたが、ちょっと足掻いてみました。ムダなあがきです。
最近、Pythonのフォーマットツールである「Black」がmypycでビルドして高速化したという話を思い出しました。

Black is now compiled with mypyc for an overall 2x speed-up. 64-bit Windows, MacOS, and Linux (not including musl) are supported. (#1009, #2431)

Change Log - Black 23.11.0 documentation black.readthedocs.io

mypycでビルドして通してみましょう。mypycでビルドするには型ヒントが必要ですが、このコードにはすでに型ヒントがついています。

該当のソースコード。sample_mypyc.py

def chinoppy_festival(idx: int) -> int:
    """indexに対応する要素を求める関数"""
    # 問題1. ここにコードを記述
    return 5 * (idx + 1) + idx


def chinoppy_carnival(idx: int) -> int:
    """idxまでの、要素の合計(sum)を求める関数."""
    # 問題2. ここにコードを記述
    return sum(chinoppy_festival(i) for i in range(idx + 1))

ビルドします。

py3.10.2 ❯ pip install mypy
py3.10.2 ❯ mypyc sample_mypyc.py
running build_ext
building 'sample_mypyc' extension
...
copying build/lib.macosx-11.6-x86_64-3.10/sample_mypyc.cpython-310-darwin.so ->

sample.pyにインポートを追加します。

from sample_mypyc import chinoppy_festival, chinoppy_carnival

実行結果は次のようになります。

py3.10.2 ❯ python -m unittest sample.py
..F...
======================================================================
FAIL: test3 (sample.TestsChinoppyCarnival)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jrfk/Documents/wk/sample.py", line 91, in test3
    self.assertTrue(f - s < 0.0001, "速さが足りない！！")
AssertionError: False is not true : 速さが足りない！！

----------------------------------------------------------------------
Ran 6 tests in 0.694s

FAILED (failures=1)

8.093sから 0.694s まで改善されました。爆速です。ですが、0.0001まではまだまだ遠い。この解法ではないということが分かりました（分かっていました）。

ちなみにジェネレーター式を内包表記にした場合、次のような結果でした。

def chinoppy_carnival(idx: int) -> int:
    """idxまでの、要素の合計(sum)を求める関数."""
    # 問題2. ここにコードを記述
    return sum([chinoppy_festival(i) for i in range(idx + 1)])

ジェネレーター式の方がだいぶ早いですね。にしてもmypyc速い！

解法

さて本題です。
答えを求めるための考え方から、説明してもらいました。

考え方のポイントは以下のようなところ。

最終的にたどり着いていた配列の順序4番目を例にした次の式、これを元に考えてみました。
\( 56 = (4 + 3 + 2 + 1) \times 6 - 4 \)

求める必要があるのは、この4番目までの値 (4 + 3 + 2 + 1) の合計です。

考え方の1つ目である以下の考え方に合致しているように思います。

しかしこのままではループすることなく答えを求めることはできそうにありません。（なんせmypycを使ってもダメでしたから）

\( (4 + 3 + 2 + 1)\) の合計を1発で求めるには？
先生は言いました。
「順序は分かっているので、その順序に対してはなにをしてもいいですよね？たとえば逆さまにしても同じ答えになりますよね？」

\( S2 = 4 + 3 + 2 + 1 \)
\( S2 = 1 + 2 + 3 + 4 \)

当然同じ結果です。

「ではこれをくっつけても倍になるだけですよね？」
\( S2+S2 = (4+1) + (3+2) + (2+3)+(1+4) \)

当然です。同じ式を2つくっつけただけだから、2倍した結果になるだけです。

「これよく見ると ...」
\( S2+S2 = 5 + 5 + 5 + 5 \)

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

まるで魔法のようでした。

「この式って同じことになるんですよ」

\( S2+S2 = 5 + 5 + 5 + 5 \)
\( S2+S2 = 5 \times 4 \)

最初の値である 5 とインデックスである 4 を乗算して、半分にするだけ...
驚きの結果です。とてもとても簡単でした。

考え方のポイントの2つ目である

がぶっ刺さります。

さらに先生は続けます。

「これ \( (4 + 3 + 2 + 1) \) ここまで分解するのも素晴らしいのですが、分解せずにもいけるんです」

\(S = 5, 11, 17, 23\)
\(S = 23, 17, 11, 5\)

見えてきます。上と下を足すんです。そうすると見えてきます。
\( S2+S2 = 28 \times 4 \)

さて、この 28 これを求める必要があります。
ここで考え方のポイントの3つ目をも元に考えてみましょう。

具体的な値を書いてみます。 28 にあたる数字がなんなのか、0番目の配列に入っている5から、順に見ていきましょう。

0番目の時

\(S = 5 \)
\(S = 5 \)

必要なのは 10

1番目の時

\(S = 5, 11 \)
\(S = 11, 5 \)

必要なのは 16

2番目の時

\(S = 5, 11, 17\)
\(S = 17, 11, 5\)

必要なのは 23

3番目の時

\(S = 5, 11, 17, 23\)
\(S = 23, 17, 11, 5\)

必要なのは 28

順に見ていくと次の値のようです。

見えてきますね。初期値の10に対し、インデックスごとに6ずつ大きくなっています。
問題は 「idxまでの、要素の合計(sum)を求める関数」なので、 \( idx \times 6 \) で求められそうです。

\[10 + (idx \times 6)\]

これで 28 の部分が求められそうです。それにindexの値を乗算し、半分にすると答えが求まります。

\[ S2+S2 = 10 + (4 \times 6) \times 4 \]

\[ (10+(index) \times 6 ) \times (index)\frac{1}{2} \]

これがたどり着いた答えになります。コードに落としてみましょう。

def chinoppy_carnival(idx: int) -> int:
    """idxまでの、要素の合計(sum)を求める関数."""
    # 問題2. ここにコードを記述
    return (10 + (idx * 6)) * (idx + 1) / 2

実行してみましょう。

py3.10.2 ❯ python -m unittest sample.py
......
----------------------------------------------------------------------
Ran 6 tests in 0.000s

OK

通りました。 mypyc よりも早い。

さらにわたしの問1の答えをよく見ると ...

def chinoppy_festival(idx: int) -> int:
    """indexに対応する要素を求める関数"""
    # 問題1. ここにコードを記述
    return 5 * (idx + 1) + idx

初期値の「5」に対し、 index+1 を掛け、indexの値を足します。
indexが0の場合、 5 * (0 + 1) + 0 = 5 となります。
indexが1の場合、 5 * (1 + 1) + 1 = 11 となります。
indexが2の場合、 5 * (2 + 1) + 2 = 17 となります。
indexが3の場合、 5 * (3 + 1) + 3 = 23 となります。

  • 1番目の時、10
  • 2番目の時、16
  • 3番目の時、22
  • 4番目の時、28

問1 chinoppy_festival に初期値である5を加算すると、求めたかった値になることが分かりました。

def chinoppy_carnival(idx: int) -> int:
    """idxまでの、要素の合計(sum)を求める関数."""
    # 問題2. ここにコードを記述
    return (chinoppy_festival(idx) + 5) * (idx + 1) / 2

算数、いや数学、とてもおもしろいですね。次の問題が楽しみです。