"142857" はエニアグラムやっていたら毎日目にする。エニアグラムは競プロの役に立つ！

問題へのリンク

問題概要（output only）

正整数 $X$ と文字列 $S$ の組であって以下の条件を全て満たすものを 1 つ挙げよ。

$10^{50} \le X \lt 10^{5000}$
$S$ は 0 から 9 までの数字からなる長さ 5000 以下の文字列
$i = 1, 2, \dots, 1000$ に対して、 $X \times i$ を 10 進表記して出来る文字列は $S$ の連続な部分文字列である

考えたこと

分母が 7 である分数（のうち分子が 7 の倍数でないもの）は、次のように、長さ 6 の循環節をもち、しかもその循環節は 142857 を circular shift したものであることがよく知られている！！

1/7 = 0.142857...
2/7 = 0.285714...
3/7 = 0.428571...
4/7 = 0.571428...
5/7 = 0.714285...
6/7 = 0.857142...

背景

このようになるカラクリを考えよう。まず、分母が 7 でなくても成り立つこととして、次のように、分数を 10 倍、100 倍、1000 倍、......していくと、循環節は巡回していく。

1/7      =     0.142857...
10/7     =     1.428571...
100/7    =    14.285714...
1000/7   =   142.857142...
10000/7  =  1428.571428...
100000/7 = 14285.714285...

これに対して、右辺の整数部分に相当する数を両辺から引くと、次のようになる。

1/7 = 0.142857...
3/7 = 0.428571...
2/7 = 0.285714...
6/7 = 0.857142...
4/7 = 0.571428...
5/7 = 0.714285...

左辺を見ると、見事に、分子が 1, 2, 3, 4, 5, 6 を一回ずつ行き渡るようになっている。この背景には次の性質がある。

$1, 10, 10^{2}, 10^{3}, 10^{4}, 10^{5}$ を 7 で割った余りは、 $1, 2, 3, 4, 5, 6$ をちょうど 1 個ずつ含む

一般化

ここまでの考察から、一般に、次のことが言えるだろう。 $p$ を素数とし、 $1, 10, 10^{2}, \dots, 10^{p-2}$ を $p$ で割った余りが、 $1, 2, \dots, p-1$ をちょうど 1 個ずつ含むとする。このとき、

分数 $1/p$ を循環小数で表したときの循環節をなす整数を $X$ とする（循環節の leading-zero はとってもよい）
その循環節（leading-zero するのを忘れずに）をなす文字列を $T$ として、 $S = T + T$ とする

とすれば、 $i = 1, 2, \dots, p-1$ に対して、 $X \times i$ を 10 進法表記してできる文字列は $S$ の連続な部分文字列である。

よって、上記を満たす素数 $p$ を $p \gt 1000$ の範囲で求める問題へと帰着された！

原始根

上の性質を満たす素数 $p$ は、実は「10 を原始根にもつ素数」に他ならない。原始根とは、次のようなものだ。

【原始根の定義】
$p$ を素数とする。 $r$ が $p$ の原始根であるとは、

$r^{x} \equiv 1 \pmod p$

を満たす最小の正の整数 $x$ が $p-1$ であることをいう。

Fermat の定理から、 $r^{p-1} \equiv 1 \pmod p$ であることは保証されるから、原始根は $p-1$ の最小性を要請するものと言える。たとえば、 $10$ は $p = 7$ の原始根である。実際

$1 \equiv 1$
$10 \equiv 3$
$10^{2} \equiv 2$
$10^{3} \equiv 6$
$10^{4} \equiv 4$
$10^{5} \equiv 5$
$10^{6} \equiv 1$

であり、 $10^{x} \equiv 1$ となる最小の正の整数 $x$ は $6 (= p - 1)$ である。原始根の定義から、次のことも直ちに示せる。

【原始根の定義】
$p$ を素数とし、 $r$ を $p$ の原始根とする。

このとき、[tex: 1, 10, 10^{2}, \dots, 10^{p²}] を $p$ で割った余りは、 $1, 2, \dots, p-1$ をちょうど 1 個ずつ含む。

よって、もとの問題は「10 を原始根にもつ、1000 より大きい素数を求める問題」へと帰着された。

10 を原始根にもつ素数

これはなんと、OEIS A001913 にある！

しかしながら、1000 未満の範囲でしか与えられていない......仕方ないので、自分の手で求めることにした。具体的には、位数を求めるライブラリを使って、1000 より大きい素数を小さい順に試して行った。そうすると $p = 1019$ が見つかった。

コード

多倍長整数を用いた。

#include <bits/stdc++.h>
using namespace std;

// 多倍長整数
struct bint : vector<long long> {
    static const int DEFAULT_SIZE = 125;  // DEFAULT_SIZE x BASE_DIGIT 桁を想定
    static const long long BASE = 100000000;
    static const int BASE_DIGIT = 8;
    int sign;

    // constructor
    bint(long long num = 0) : vector<long long>(DEFAULT_SIZE, 0), sign(1) {
        if (num < 0) sign = -1, num = -num;
        (*this)[0] = num;
        this->normalize();
    }
    bint(int size, long long num) : vector<long long>(size, num), sign(1) {}
    bint& normalize() {
        long long c = 0;
        bool exist = false;
        for (int i = 0;; ++i) {
            if (i >= this->size()) this->push_back(0);
            if ((*this)[i] < 0 && i+1 >= this->size()) this->push_back(0);
            while ((*this)[i] < 0) {
                (*this)[i+1] -= 1;
                (*this)[i] += BASE;
            }
            long long a = (*this)[i] + c;
            (*this)[i] = a % BASE;
            if ((*this)[i]) exist = true;
            c = a / BASE;
            if (c == 0 && i == this->size()-1) break;
        }
        if (!exist) sign = 1;
        return (*this);
    }
    friend bint abs(const bint &x) {
        bint z = x;
        if (z.sign == -1) z.sign = 1;
        return z;
    }

    // operation
    bint operator - () const {
        bint res = *this;
        bool allzero = true;
        for (int i = 0; i < this->size(); ++i) {
            if (res[i] != 0) {
                allzero = false;
                break;
            }
        }
        if (!allzero) res.sign = -res.sign;
        return res;
    }
    bint& operator += (const bint& r) {
        while (size() < r.size()) this->emplace_back(0);
        if (sign == r.sign) {
            for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
        }
        else {
            if (sign == 1 && abs(*this) < abs(r)) sign = -1;
            else if (sign == -1 && abs(*this) <= abs(r)) sign = 1;
            if (abs(*this) >= abs(r)) {
                for (int i = 0; i < r.size(); ++i) (*this)[i] -= r[i];
            }
            else {
                for (int i = 0; i < size(); ++i) (*this)[i] = -(*this)[i];
                for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
            }
        }
        return this->normalize();
    }
    bint& operator -= (const bint& r) {
        while (size() < r.size()) this->emplace_back(0);
        if (sign == -r.sign) {
            for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
        }
        else {
            if (sign == 1 && abs(*this) < abs(r)) sign = -1;
            else if (sign == -1 && abs(*this) <= abs(r)) sign = 1;
            if (abs(*this) >= abs(r)) {
                for (int i = 0; i < r.size(); ++i) (*this)[i] -= r[i];
            }
            else {
                for (int i = 0; i < size(); ++i) (*this)[i] = -(*this)[i];
                for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
            }
        }
        return this->normalize();
    }
    bint& operator *= (long long r) {
        if ( (sign == 1 && r >= 0) || (sign == -1 && r < 0) ) sign = 1;
        else sign = -1;
        if (r < 0) r = -r;
        for (int i = 0; i < size(); ++i) (*this)[i] *= r;
        return this->normalize();
    }
    bint& operator *= (const bint& r) {
        int tx = (int)size()-1, ty = (int)r.size()-1;
        for (tx = size()-1; tx >= 0; --tx) if ((*this)[tx] > 0) break;
        for (ty = r.size()-1; ty >= 0; --ty) if (r[ty] > 0) break;
        bint res(0);
        res.resize(tx+ty+2);
        if (sign == r.sign) res.sign = 1;
        else res.sign = -1;
        for (int i = 0; i <= tx; ++i) {
            for (int j = 0; j <= ty && i+j < (int)res.size()-1; ++j) {
                long long val = (*this)[i] * r[j] + res[i+j];
                res[i+j+1] += val / bint::BASE;
                res[i+j] = val % bint::BASE;
            }
        }
        return (*this) = res.normalize();
    }
    friend bint pow(const bint& a, long long n) {
        bint res(1), b = a;
        while (n > 0) {
            if (n & 1) res = res * b;
            b = b * b;
            n >>= 1;
        }
        return res;
    }
    bint operator + (const bint& r) const { return bint(*this) += r; }
    bint operator - (const bint& r) const { return bint(*this) -= r; }
    bint operator * (long long r) const { return bint(*this) *= r; }
    bint operator * (const bint& r) const { return bint(*this) *= r; }

    // divide
    bint& operator /= (long long r) {
        if (r < 0) sign *= -1, r = -r;
        long long c = 0, t = 0;
        for (int i = (int)size()-1; i >= 0; --i) {
            t = bint::BASE * c + (*this)[i];
            (*this)[i] = t / r;
            c = t % r;
        }
        this->normalize();
        return (*this);
    }
    long long operator %= (long long r) {
        if (r < 0) sign *= -1, r = -r;
        long long c = 0, t = 0;
        for (int i = (int)size()-1; i >= 0; --i) {
            t = bint::BASE * c + (*this)[i];
            (*this)[i] = t / r;
            c = t % r;
        }
        return c;
    }
    bint operator / (long long r) const {
        return bint(*this) /= r;
    }
    long long operator % (long long r) const {
        return bint(*this) %= r;
    }
    friend pair<bint, bint> divmod(const bint &a, const bint &r) {
        bint zero = 0, s = 0, t = 0;
        if (abs(a) < abs(r)) return {zero, a};
        bint ar = abs(r);
        s.resize((int)a.size()), t.resize((int)r.size());
        int tx = (int)a.size()-1;
        for (;tx >= 0; --tx) if (a[tx] > 0) break;
        for (int i = tx; i >= 0; --i) {
            t = t * bint::BASE + a[i];
            long long lo = 0, hi = bint::BASE;
            if (t >= ar) {
                while (hi - lo > 1) {
                    int mid = (hi + lo) / 2;
                    if (ar * mid > t) hi = mid;
                    else lo = mid;
                }
                t -= ar * lo;
            }
            s[i] = lo;
        }
        if (a.sign == r.sign) s.sign = 1, t.sign = 1;
        else s.sign = -1, t.sign = 1;
        return make_pair(s.normalize(), t.normalize());
    }
    bint operator / (const bint& r) const {
        return divmod((*this), r).first;
    }
    bint operator % (const bint& r) const {
        return divmod((*this), r).second;
    }
    bint& operator /= (const bint& r) { return (*this) = (*this) / r; }
    bint& operator %= (const bint& r) { return (*this) = (*this) % r; }

    // equality
    friend bool operator < (const bint &x, const bint& y) {
        if (x.sign < y.sign) return true;
        else if (x.sign > y.sign) return false;
        else {
            int tx = (int)x.size()-1, ty = (int)y.size()-1;
            for (tx = x.size()-1; tx >= 0; --tx) if (x[tx] > 0) break;
            for (ty = y.size()-1; ty >= 0; --ty) if (y[ty] > 0) break;
            if (tx < ty) return true;
            else if (tx > ty) return false;
            else if (x.sign == 1) {
                for (int i = tx; i >= 0; --i)
                    if (x[i] != y[i]) return x[i] < y[i];
                return false;
            }
            else {
                for (int i = tx; i >= 0; --i)
                    if (x[i] != y[i]) return x[i] > y[i];
                return false;
            }
        }
    }
    friend bool operator > (const bint& x, const bint& y) { return y < x; }
    friend bool operator <= (const bint& x, const bint& y) { return !(x > y); }
    friend bool operator >= (const bint& x, const bint& y) { return !(x < y); }
    friend bool operator == (const bint &x, const bint& y) {
        if (x.sign != y.sign) return false;
        int tx = (int)x.size()-1, ty = (int)y.size()-1;
        for (tx = x.size()-1; tx >= 0; --tx) if (x[tx] > 0) break;
        for (ty = y.size()-1; ty >= 0; --ty) if (y[ty] > 0) break;
        if (tx != ty) return false;
        for (int i = tx; i >= 0; --i)
            if (x[i] != y[i]) return false;
        return true;
    }
    friend bool operator != (const bint& x, const bint& y) { return !(x == y); }
};

bint toBint(const string &is) {
    string s = is;
    if (s[0] == '-') s = s.substr(1);
    while (s.size() % bint::BASE_DIGIT != 0) s = "0" + s;
    int N = (int)s.size();
    bint res(N/bint::BASE_DIGIT, 0);
    for (int i = 0; i < (int)s.size(); ++i) {
        res[(N-i-1)/bint::BASE_DIGIT] *= 10;
        res[(N-i-1)/bint::BASE_DIGIT] += s[i] - '0';
    }
    if (is[0] == '-') res.sign = -1;
    return res;
}

string toStr(const bint &r) {
    stringstream ss;
    if (r.sign == -1) ss << '-';
    int d = (int)r.size()-1;
    for (; d >= 0; --d) if (r[d] > 0) break;
    if (d == -1) ss << 0;
    else ss << r[d];
    for (int i = d-1; i >= 0; --i) {
        ss.width(bint::BASE_DIGIT);
        ss.fill('0');
        ss << r[i];
    }
    return ss.str();
}

istream &operator >> (istream &is, bint &x) {
    string s; is >> s;
    x = toBint(s);
    return is;
}

ostream &operator << (ostream &os, const bint &x) {
    if (x.sign == -1) os << '-';
    int d = x.size()-1;
    for (d = x.size()-1; d >= 0; --d) if (x[d] > 0) break;
    if (d == -1) os << 0;
    else os << x[d];
    for (int i = d-1; i >= 0; --i) {
        os.width(bint::BASE_DIGIT);
        os.fill('0');
        os << x[i];
    }
    return os;
}


int main() {
    int p = 1019;  // 10 を原始根にもつ 1000 以上の素数
    string s(p-1, '9');
    bint v = toBint(s);
    v /= p;

    string res = toStr(v);
    res = string(p-1-res.size(), '0') + res;
    res = res + res;

    cout << v << endl;
    cout << res << endl;
}