4つの数字「2」であらゆる整数を作る

 (eli.thegreenplace.net)
1 ポイント 投稿者 GN⁺ 2025-02-24 | 1件のコメント | WhatsAppで共有
  • 4つの「2」だけで数を作るパズルは、許可する演算をどこまで広げるかによって、四則演算パズルから高度な数学遊びへと発展する
  • 分数と四則演算だけでも1から6までは作れ、指数・階乗を加えると18、28、256、65536のような大きな数も構成できる
  • 2をつなげて22や222と見なしたり、複素数と絶対値を使ったりすると、単純な計算では難しい数までさまざまな方法で表現できる
  • 7は作りにくい数として知られているが、ガンマ関数のような道具を許可すれば、4つの2ですぐに作れる
  • Paul Diracの一般解は、入れ子の平方根と底が2の対数を使って任意の数を表現し、2 = √(2+2) という置換でちょうど4つの2に合わせる

4つの2で数を作る基本ルール

  • パズルの条件は、数字 2を正確に4回 使い、ほかの数字を使わず数学演算だけで目標の数を作ること
  • 四則演算と分数だけでも、小さな数は比較的簡単に作れる
    • 1 = (2+2)/(2+2)
    • 2 = 2/2 + 2/2
    • 3 = 2·2 - 2/2
    • 4 = 2+2+2-2
    • 5 = 2·2 + 2/2
    • 6 = 2·2·2 - 2
  • 指数と階乗を許可すると、表現できる範囲が大きく広がる
    • 18 = 2^(2^2) + 2
    • 28 = (2+2)! + 2 + 2
    • 256 = (2+2)^(2+2)
    • 65536 = 2^(2^(2^2))
  • 数字をつなげる方法も、このパズルでよく使われるトリック
    • 26 = 22 + 2 + 2
    • 11 = 22 / √(2+2)
    • 444 = 222 · 2
  • 特に7は作るのが難しい数だが、ガンマ関数を使えば 7 = Γ(2) + 2 + 2 + 2 と表現できる
  • Math StackExchangeのスレッドには、積分、循環小数、組合せ演算子などを活用した例がある
  • 複素数と絶対値を使えば、12 = |2 + 2√-2|² のような表現も可能

Diracの一般解

  • Paul Diracは、すべての数に適用できる一般解を見つけ、その中核となる仕掛けは入れ子の平方根だった
  • 2に平方根を繰り返し適用すると、次のように指数形式で整理できる
    • √2 = 2^(1/2) = 2^(2^-1)
    • √√2 = 2^(1/4) = 2^(2^-2)
    • √√√2 = 2^(1/8) = 2^(2^-3)
  • 平方根をn回適用すると、√√...√2 = 2^(2^-n) という形になる
  • ここで底が2の対数を1回取ると 2^-n になり、さらに対数を取ると -n になる
  • したがって任意のnは、n = -log₂(log₂(√√...√2)) という形で表現できる
  • 元の式は数字の2を3回しか使わないため、2 = √(2+2) を使って1つの2を置き換えれば、ちょうど4つの2を使う式になる
  • たとえば7は、平方根を7回入れ子にして次のように表現できる 7 = -log_{√(2+2)}(log₂(√√√√√√√2))
  • 式の中の n は実際の表現に入る数字ではなく、平方根の反復回数を数えるための補助表記
  • 結局、すべての数を表現する道は開けるが、必要な数だけ平方根記号を正確に書く作業が残る

関連記事

1件のコメント

 
GN⁺ 2025-02-24
Hacker Newsのコメント

  • 関数を認めた瞬間、このゲームの趣旨を捨てたように感じる。
    たとえばガンマ関数は (n-1)! なので、これでは 2 を4つと 1 を1つで 7 を作っているようなものだ。
    関数呼び出しの中に数字を隠せるなら、常に成功できてしまい簡単すぎる。

    • +、-（二項/単項）、×、÷ も関数だし、べき乗も関数だ。なら、なぜそれらは認めるべきなのか。
      こういうパズルではいつも 初等関数 の範囲をめぐって意見が分かれうるが、平方根を禁止する必要はないと思う。
      ガンマ関数が (n-1)! だという話については、2 も結局は S(S(0)) にすぎない（https://en.wikipedia.org/wiki/Peano_axioms）。
      Paul Dirac の構成を自明と呼ぶのは難しいし、本当に自明だと思っているのか、それとももっと単純な構成を知っているのか気になる。
    • ガンマ関数が出てきた瞬間、最初に思ったことも同じだった。
      ガンマ関数は許すのに、なぜ他の関数はだめなのか。任意の関数を入れたらゲームを好き放題に解けてしまう。
      結局のところ、この記事は冒頭から ルールがきちんと定義されていない問題 だと思う。許される関数や演算の集合を明示すべきで、知識レベルに応じて問題がどう拡張されるかを示したい意図も、そう直しても保てるはずだ。
    • 結局は遊びなのだから、ガンマ関数と平方根 は十分に基本的なものと見なせる。
      その気があれば、異なる関数の部分集合に制限して、その中でどの数が可能か不可能かを証明してみてもよい。
      記事でも「数学的な道具」とは言っていたが、任意の関数とは言っていなかった。
    • 指摘には一理あるが、他の人たちが言うように「関数を許すこと」自体が問題なのではない。基本的な数学演算も関数だからだ。
      ただし、整数タプルを整数へ写す関数 ((Z, Z, ...) -> Z) だけを許せば、元のゲームの趣旨は保てる。
      こうすると平方根と対数は外れ、加算・減算・乗算は残るが除算は外れる。階乗 n! と非負整数指数へのべき乗も許容できる。
      この制約の中で一般解を作れるのか気になる。
    • Dirac の解法 にはガンマ関数は入っておらず、平方根 N 個と対数 2 個だけを使っている。

  • 「どんな数学演算でも使ってよい」なら簡単で、単に 後者関数 を使えばよい。
    S(n) = n+1
    6 = 2*2*2-2
    7 = S(2*2*2-2)
    8 = S(S(2*2*2-2))
    こんなふうにいくらでも続けられる。

    • 「他の数字を使わない」という制約を見ると、最初の行に 1 が入っているのは反則に感じる。
    • 学校で数学をかなり学び、エンジニアリングの仕事で毎日数学を使い、YouTube の数学チャンネルもたくさん登録しているが、この関数は生まれて初めて聞いた。
      このパズルに厳密なルールがあるわけではないにせよ、この関数がよく知られているとはまったく思えない。
    • 与えられた整数について 2 を4つで作る最短の式 を探すほうが、もっと面白い挑戦になりそうだ。
    • 同じことを思った。平方根も、記法の後ろに 2 を隠しているようなものだ。
      どの演算子を何回使ってよいかを具体的に定めないと、プロジェクト全体にあまり一貫性がない。
    • ラムダ計算 が会話に入り込んできた。

  • 関連して、1964 年に 26 歳の Donald Knuth が書いた「Representing numbers using only one 4」もある（https://www.jstor.org/stable/2689238）。
    これは彼の Selected Papers on Fun and Games の第 10 章にも再録されており、数字 4 を1つと 3 つの演算 √x（平方根）、⌊x⌋（床関数）、x!（階乗）だけを使う。
    すべての整数をこの方法で表せるかどうかは、いまだ未解決の予想として終わっている。
    2011 年の本に付いた付録では、さらに早い 1962 年の J. H. Conway と M. J. T. Guy による 1.5 ページの論文「π in Four 4's」も紹介されている。2 人が Cambridge の学生だった頃に書いた類似のアイデアだ: https://archive.org/details/eureka-25/page/18/mode/1up?view=...
    たとえば 5 = ⌊√√√√√(4!)!⌋ で、これは 24! が 5^32 と 6^32 の間にあるためだ。

  • 自分だけかもしれないが、sqrt(2*2) や sqrt(2^2) ではなく sqrt(2+2) を使った選択は妙に感じた。
    なぜ 2=sqrt(2+2) なのかが見える理由を、不必要に隠している。

    • いい指摘ではあるが、著者の奇妙な選択とだけは言い切れない。
      記事全体、各論証、全体の論旨、文、書式など、あらゆるものに 認知帯域 が使われていて、時間的なプレッシャーもあったのかもしれない。
      批判する側は余裕を持って一点だけに集中できるのだから、当然そう見えるのだろう :)
    • どこかに、低コストな演算を埋め合わせる ゴルフスコア のようなものがあるのかもしれない。
      「Dirac ハック」はかなり高得点になりそうだ。
    • 本当に？ なぜだろう？ 2+2、2*2、2^2 はどれも自明に 4 で、sqrt(4)=2 なのだから、+ だけが他より奇妙だという理由がわからない。

  • 個人的には 簡潔さ のほうが好み
    単一文字コマンドを使うスタックマシンを作っていて、この問題の変種を解く必要があった。数字は 0 から 9 までしかなく、文字 23 は 2 をプッシュしてから 3 をプッシュする意味だった。実際の数値 23 を表すには 45*3+ のような式を書く必要があった
    そのため、各整数を最小の文字数でエンコードする問題が残った
    使える道具は数字 0~9、P: Pi、*: (a * b)、/: (a / b)、-: (a - b)、+: (a + b)、s: sin(a)、c: cos(a)、q: sqrt(a)、l: log(a)、~: abs(a)、#: round(a)、$: Math.floor(a)、C: clamp(a)、<: min(a, b)、>: max(a, b)、^: pow(a, b)、a: atan2(a, b)、%: positiveMod(a, b)、!: (1 - a)、?: (a <= 0 ? 0 : 1)、o: a xor b scaled by c; ((a*c) xor (b*c))/c、d: スタック最上段の複製、:: 最上段 2 項目の交換、;: 最上段と 3 番目の項目の交換だった
    後でこのスタックマシンを 複素数スタック で作り直したら何ができるのか気になる
    次にこういうものを投稿するときは、スマホでは書かないつもり

    • 一般的な答えは計算不可能かもしれない
      https://en.wikipedia.org/wiki/Kolmogorov_complexity
    • 各数字を「10 を掛けてその数字を足す」命令で作り、空白のように 0 をプッシュする別コマンドを置くのはどうだろう？ そうすれば 23 を " 23" と表現できる
    • https://www.hacker.org/hvm/ (2008) を思い出す
    • かなり多くの数字が 9 進法や 10 進法 でエンコードされそう。たいていは digit + * digit + * のようなパターンの繰り返しか、それと同等の形になりそう

  • 「数字の 2 を 3 回しか使っていない」という小さな瑕疵ではあるが、根号表記が共通の値をデフォルトとして 1/2 乗 を隠しているという事実を無視すれば、という話
    隠れた 2 がかなり多い

    • 根号表記が何かを本当に隠しているとは言いにくい。1/2 乗とほぼ同じだというのは定理だ
      だとすると、2 も 1+1 を隠していると認めるべきで、ゲームは不可能になるのだろうか？
      高次多項式より二次多項式のほうがずっと一般的だという点で、平方根は任意の冪乗より基本的に感じられる
      派手な関数を許した時点でゲームがおかしくなるという指摘は多いが、個人的には具体的なルール制限がなくても満足のいく解法を探す面白さは大きいと思う

  • 関連して、ある リバースエンジニアリング/CTF の課題があった。名前はチート防止のため出さないが、私の解法はスタックポインタに特定の数を足すシェルコードを注入するものだった
    ただし、シェルコード全体、足す数まで含めて ASCII 英数字バイトしか使えなかった
    そこで SAT ソルバーを使って、禁止バイトを使わずに目的の値になるよう足し合わせる数の組み合わせを見つけた
    https://docs.google.com/presentation/d/19K7SK1L49reoFgjEPKCF...

  • モバイルゲーム Tchisla を思い出す。与えられた数字 1 つといくつかの演算子、平方根や ! などを使って、1000 または 10000 までのすべての数を作らなければならないゲーム
    かなり面白く、やっているうちに戦略も生まれ、ユーザー体験もシンプルで効率的。ただし、ものすごく時間を食うことは覚悟しておいたほうがいい
    [0] https://apps.apple.com/fr/app/tchisla-number-puzzle/id110062...

  • 古典的な 4つの4 問題があり、子どものころに "The Man Who Counted" という本で知った
    https://en.wikipedia.org/wiki/Four_fours
    https://en.wikipedia.org/wiki/The_Man_Who_Counted

    • 私が子どものころに教わったのもそのバージョン。私が作ったこのページも面白いかもしれない
      The Definitive Four Fours Answer Key
      https://dwheeler.com/fourfours/
    • まさにそれだった
      それで 偽りの帰納法 を学んだ。人々が一列に並び、背中に何かが貼られていて、それが何かを当てなければならない話も好きだった

  • すごいことはすごいけど、その sqrt 記号 の中に隠れている 2 が多すぎる