p 進コンテストをコンピュータに丸投げする

問題

#p進コンテスト
{2, 5, 8}だけを並べて10進法で自然数を作ります。この数の中で「2進的」にもっとも 0 に近い数を作った人が優勝です。つまり n を 2が割り切る回数を ord_2(n) としたときに、ord_2(n) が最も大きな n を探しましょう。

— tsujimotter (@tsujimotter) 2017年2月14日

小さい範囲の探索

今回の問題を解釈し直すと「$n=k\cdot 2^m$ を満たす $n$ を求めよ。ただし 10 進数表記で2,5,8だけ使うこと、$k$は奇数とする。」ということになるので、小さな範囲では虱潰しにやっていくのが簡単なようです。今回は各 ord について $k$ を小さい方から増やしていって 2,5,8 だけの数になるか確認しました。

#include <iostream>
using namespace std;
using uint64 = unsigned long long;

bool is258(uint64 n) {
  while (n) {
    uint64 d = n % 10;
    if (d != 2 && d != 5 && d != 8)
      return false;
    n /= 10;
  }
  return true;
}

int main() {
  for (int ord = 1; ord < 35; ++ord) {
    for (uint64 k = 1; k < 1000000000; k += 2) {
      uint64 n = k << ord;
      if (is258(n)) {
        cout << ord << ":" << n << "\n";
        break;
      }
    }
  }
  return 0;
}

一応結果は $ord \leq 27$ まで出て

1:2
2:28
3:8
4:528
5:288
6:52288
7:28288
8:5888
9:588288
10:8588288
11:22528
12:522252288
13:8855552
14:88588288
15:2558885888
16:222552588288
17:28552855552
18:285285285888
19:8258558885888
20:28582255525888
21:8285258252288
22:222828888588288
23:252255852822528
24:2885228888588288
25:5855582552588288
26:558558282252288
27:8855285858828288

これ以降は $2^m \cdot 10^9 > 2^{64}$ となりますし、$10^9$ を超えるループはとても時間がかかるので、最小の $n$ を順に探す作業は終了です。

数学的考察

ただもちろん問題としては $n$ が最小である必要はないので、もっと大きな $ord_2(n)$ は作れるはずです。

@yuui_nesya 例えば
8855285858828288は16桁
ord_2(8855285858828288)=27
ord_2(22528)=11なので
ord_2(225288855285858828288)は28以上になる

つまりいくらでも大きくできる

— ねしゃ～ (@yuui_nesya) 2017年2月14日

@tsujimotter 紹介先と同様の議論により　2と5で作られるn桁の整数に限れば2^nで割り切れるものが一つだけ存在する　ということです

— nishimura (@icqk3) 2017年2月14日

後者の理論の方を単純に説明すると、$n$ が $k$ 桁の数で $ord_2(n) \geq k$ を満たしていれば、先頭に 2 か 5 をつけると $ord_2(n') \geq k+1$ が帰納的に成り立つということです。ただ 2 をつけるか 5 をつけるかを試していくのは大変面倒なのでコンピュータに任せてみましょう。

#!/usr/bin/python                                                                                      

def main():
  n = 0
  for k in xrange(140):
    d, b = 10 ** k, 2 ** (k + 1)
    m = 2 * d + n
    if m % b != 0:
      m = 5 * d + n
    n = m
    print '%d:%d' % (k + 1, n)

if __name__ == '__main__':
  main()

正確な $ord_2(n)$ でない可能性もありますが、とりあえずこれであっさりと計算はできます。#p進コンテスト のハッシュを入れたり $ord_2$ の値を入れたりして Tweet することを考えると　$ord_2(n)=127$ が最大値でしょうか。　

より小さな n の探索

ただこのままでは 8 が入る箇所が無いですし、$ord_2(n)$ が不正確なのでプログラムを改良しましょう。具体的には「$n=2$ か $n=8$ から始め、ランダムに先頭の数字をくっつけ、$ord_2(n)\geq k$ の確認を取るということを繰り返す」ということをひたすら繰り返します。

#!/usr/bin/python                                                                                      

import random

def ord_2(n, k=0):
  m = n / (2 ** k)
  while m % 2 == 0:
    m = m / 2
    k = k + 1
  return k


def main():
  N = 140
  leads = [2, 5, 8]

  out = [0, 0]
  while True:
    n = 0
    for k in xrange(N):
      d, b = 10 ** k, 2 ** (k + 1)
      random.shuffle(leads)
      for l in leads:
        m = l * d + n
        if m % b == 0:
          n = m
          break
      o = ord_2(n, k + 1)
      tweet = '%d:%d' % (n, o)
      if len(tweet) >= 132:
        continue
      if o > out[0] or (o == out[0] and n < out[1]):
        out = [o, n]
        print tweet


if __name__ == '__main__':
  main()

一晩走らせてみた結果、一番良かったのは

#p進コンテスト 555555255255552552885225552255255582585585225558858585585858585582822528552255285558585285858255858882555558858285852552855552:152

— Peria (@peria) 2017年2月15日

という感じでした。