質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.37%

0 <= n < Long.MAX_VALUE までの n に含まれる回文数の個数

解決済

回答 6

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,313

score 805

回文数 (Palindromic Number) 

数字の桁を逆から並べた数がもとの数に等しいものを回文数という。10進数以外にも回文数はあります。質問は10進数に限定します。

0,1,2,3,4,5,6,7,8,9,11,22,33, … , 111, 121, … , 999, …

回文数の判定のために以下を作成しました。 Long.MAX_VALUEまでは確認しています。

 /**
   * 整数 num から、各桁の数字を反転させた整数を返す。 
   * @param num 整数
   * @return 各桁の数字を反転させた整数
   */
  static long reverse(long num) {
    int sign = (num < 0) ? -1 : 1;
    BigInteger rem = BigInteger.valueOf(num).abs();
    int numDigits = getDigitCount(rem); // 桁数

    BigInteger result = BigInteger.ZERO;
    for (int i = 1; i <= numDigits; ++i) {
      result = result.add(BigInteger.TEN.pow(numDigits - i).multiply(rem.mod(BigInteger.TEN)));
      rem = rem.divide(BigInteger.TEN);
    }
    return result.longValue() * sign;
  }

  /**
   * スタックオーバーフローの以下の回答を引用します。(底の変換を利用)
   * https://stackoverflow.com/questions/18828377/biginteger-count-the-number-of-decimal-digits-in-a-scalable-method/18828536#18828536
   * 桁数を数える
   * @param number 数
   * @return 桁数
   */
  public static int getDigitCount(BigInteger number) {
    double factor = Math.log(2) / Math.log(10);
    int digitCount = (int) (factor * number.bitLength() + 1);
    if (BigInteger.TEN.pow(digitCount - 1).compareTo(number) > 0) {
      return digitCount - 1;
    }
    return digitCount;
  }

回文数の個数

0 <= n < Long.MAX_VALUE までの n に含まれる回文数の個数を求めたい。以下のコードは遅くて使えません。

  long cnt = 0;
  for (long i=0; i < Long.MAX_VALUE; ++i) {
    if (i==reverse(i)) ++cnt;
  }

質問

  • 回文数の個数を求める良いアルゴリズムがありませんか。
    桁数が固定されているなら、組み合わせ数を計算することで効率よく求められます。
    しかしLong.MAX_VALUE までとなると工夫が必要です。
  • 回文数判定の良いコードがあれば教えてください。

質問のどれかに答えていただいても、解法の一部でも、ヒントでも構いません。

 

桁数から回文数の個数を求める(追記)

ここまではわかっています。18桁までの回文数は以下の式で求められます。
組合せ数

  /**
   * 桁数nを与えて、1桁からn桁までの回文数の個数を返す。
   * @param n 桁数 (1以上)
   * @return 回文数の個数
   */
  static long countPalindromics_(int n) {
    if (n <= 0) {
      throw new IllegalArgumentException("nは1以上です。");
    }
    long acc = IntStream.rangeClosed(1, n).mapToLong(i -> (long) Math.pow(10, (i-1)/2) * 9l).sum();
    return acc + 1;
  }


この知識を前提にすれば、n のうち、1000000000000000000 <= m < Long.MAX_VALUE までの m に含まれる回文数の個数を求めたい。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

checkベストアンサー

+2

組み合わせ数の数え方を工夫します。

例:3141592までの回文数のカウント
3141592の桁数を調べる。7桁なので、7桁未満の回文数の数を計算する、つまり
0:1 1桁の自然数:9 2桁:9 3桁:9*10 4桁:9*10 5桁:9*10*10 6桁:9*10*10
7桁の自然数のうち、1と2で始まる回文数の数を計算する、つまり2*10*10*10
7桁の自然数のうち、30で始まる回文数の数を計算する、つまり1*10*10
7桁の自然数のうち、310、311、312、313で始まる回文数の数を計算する、つまり4*10
7桁の自然数のうち、3140で始まる回文数の数を計算する、つまり1
7桁の自然数のうち、3141で始まる回文数が3141592以下か調べる、今回は以下なのでカウントを1増やす

この日本語をJ訳してください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/04/19 22:29

    正確で簡潔な記述ありがとうございます。0 をひとつだけよけるのはセンスが光ります。最初に読んだ時にJ訳の意味が分かりませんでした。

    キャンセル

  • 2020/04/20 07:51

    すみません。まだ回答してくださる方がいらっしますので、ベストアンサーをいったん外します。

    キャンセル

+2

考え方を整理するために、まずn桁の回文数が何個あるかを計算してみます。例として4桁の場合を計算してみます。

4桁の数は1000から9999までありますが、回文数を作るために、まず最初の2桁を選びます。例えば35とします。35xxとなる回文数は、35を逆転して接続した3553になります。73だったら、7337になります。この例から分かることは、最初の2桁を決めれば、自動的に回文数が一つ作れ、しかも、必ず一つしかない、ということです。つまり、4桁の回文数の個数は、10から99までの個数と同じ、90個です。

偶数桁の回文数は、すべて同じようにして求められます。6桁なら900個、8桁なら9000個です。

奇数桁の場合を考えてみます。例として3桁の回文数の個数を求めてみます。4桁と同じように、まず最初の2桁を選びます。このまま偶数桁と同じことをすると4桁になってしまいますが、実は、元の2桁の数の最後の桁と、逆転した数の最初の桁は同じで、重ねることができます (35xx -> 3553 -> 353)。つまり、奇数桁の回文数の個数は、一つ多い偶数桁の回文数の個数と同じになるわけです。5桁なら900個、7桁なら9000個になります。

これの考え方を応用すれば、MAX_VALUEまでの回文数の個数も求められます。あまり大きい桁だと説明が面倒になるので、ここでは16bitの符号なし整数の最大値、65535までの回文数の個数を求めてみます。

さて、4桁までの回文数の個数は、公式を用いれば簡単に求められるので、5桁の回文数の個数を計算してみます。上の考え方を使えば、100から655までが最初の3桁の候補になります。このうち、654までは確実に回文数があります。65535より大きくならないからです。

655の場合は、回文数が65535より大きくなるかどうか、確認する必要があります。655を逆転すると556で、これは元の65535の下三桁535より大きいので、MAX_VALUEの範囲からはみ出てしまいます。

以上より、5桁の回文数の個数は、100から654までの555個になります。これに4桁までの回文数の個数を足せば、求める答えが得られます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/04/19 22:36

    公式を作る時に、奇数桁と続く偶数桁の回文数が同じであることがわかりました。半分に折り畳むと考慮する数字の個数が同じだから。0を除外すると上のルールが完全に当てはまります。最後の桁の回文数の求め方は参考にさせていただきます。

    キャンセル

+1

桁数が固定されているなら、組み合わせ数を計算することで効率よく求められます。

これをLong.MAX_VALUEの桁数まで広げつつ繰り返せばいいのではないでしょうか。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/04/19 22:37

    ナイスチャレンジ。ありがとうございました。

    キャンセル

+1

longの最大値は9223372036854775807です。これをもとに考えます。
最高位が9なので、17桁の回文数(最高位0含む)の両側に1~8を付けたものはOKです。9を付けられるものを考えます。
上から2桁目が2なので、15桁の回文数に0か1を付けたものは使えます。3以上を付けたものは9を付けられません。2を付けたもので使えるものを数えます。

…というように、桁を狭めていけば数えられるのではないでしょうか。

(以下、全体の回文数カウントについて間違った私の回答)

回文数の前と後に0以外の1桁の数をつけたものも回文数になります。たとえば22の前後に数字をつけて、
1221,2222,3223,…,9229
という具合に。この考え方をすると、
3桁の回文数は1桁の回文数10個のそれぞれに対して9通りの数字のつけ方があるので90個。
4桁の回文数は2桁の回文数9個のそれぞれに対して9通りの数字のつけ方があるので81個。
というように数えていけます。
longは19桁まで表せるので、この方法で18桁までカウントできます。19桁になるものでlongの範囲を超えるものを除外すればいいです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/04/19 11:00

    4桁の回文数は1001から9999まで90個あるのですが…

    キャンセル

  • 2020/04/19 11:09 編集

    あ、そうか、間が全部0のケースを別に追加しないといけませんでした。
    ありがとうございます。

    キャンセル

  • 2020/04/19 11:11

    そう考えるといろいろ欠陥があった

    キャンセル

  • 2020/04/19 22:37

    ナイスチャレンジ。ありがとうございました。

    キャンセル

+1

9223372036854775807 が19桁なので、上9桁、中1桁、下9桁に分離して、
922337203_6_854775807 と記述するとして、

中1桁で場合分けして、

中1桁が0〜6の場合、100000000_X_000000001 〜 922337203_X_302733229 の形になるものが、
(922337203 - 100000000 + 1)×(Xが0〜6の7通り)個の、822,337,204×7 個

中1桁が7〜9の場合、100000000_X_000000001 〜 922337202_X_202733229 の形になるものが、
(922337202 - 100000000 + 1)×(Xが7〜9の3通り)個の、822,337,203×3 個

822,337,204*7+822,337,203*3=8,223,372,037 通り

のような気がします。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/04/19 22:37

    ナイスチャレンジ。ありがとうございました。

    キャンセル

+1

package teratail;

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        //// n は 奇数桁数であること!
        long TEST[] = { 100, 200, 202, Byte.MAX_VALUE, Short.MAX_VALUE };
        for (long n : TEST) {
            System.out.println(kaibun1(new BigInteger("" + n)));
            System.out.println(kaibun0(n));
            System.out.println(kaibunZ(n));
        }
        System.out.println();
        System.out.println(kaibunY());
        System.out.println(kaibunZ(Long.MAX_VALUE));
        System.out.println();

        System.out.println(kaibunZ(Long.MAX_VALUE) - kaibunZ((long) Math.pow(10, 18)));
        System.out.println(kaibunZ(Long.MAX_VALUE) - countPalindromics_(18));
    }

    public static long kaibun1(BigInteger max) {
        long count = 0;
        for (BigInteger i = BigInteger.ZERO; max.compareTo(i) >= 0; i = i.add(BigInteger.ONE)) {
            String s = i.toString();
            String y = new StringBuilder(s).reverse().toString();
            // System.out.println(s + ":" + y);
            if (s.equals(y)) {
                ++count;
            }
        }
        return count;
    }

    public static long kaibun0(long max) {
        long count = 0;
        for (long i = 0; i <= max; i++) {
            String s = "" + i;
            String y = new StringBuilder(s).reverse().toString();
            if (s.equals(y)) {
                ++count;
            }
        }
        return count;
    }

    public static long countPalindromics_(int keta) {
        if (keta <= 0) {
            throw new IllegalArgumentException("ketaは1以上です。");
        }
        long ans = (long) (2 * Math.pow(10, keta / 2)) - 1;
        if (keta % 2 == 1) {
            ans = (long) (2 * Math.pow(10, keta / 2 + 1)) - 1;
            ans -= 9 * Math.pow(10, keta / 2);
        } else {
            ans = (long) (2 * Math.pow(10, keta / 2)) - 1;
        }
        return ans;
    }

    public static long kaibunY() {
        // Long.MAX_VALUE; // 9223372036854775807
        long count = 3 + 60 + 900 + 7000 + 20000 + 600000 + 6000000 + 70000000 + 700000000L;
        // Long.MAX_VALUE .. 10 ** 20 - 1 の間にある 回分数の数を求める
        // パターン (個数)
        // 922337203 6 854775807
        // 922337203 6 302733229 ()
        // 922337203 * 302733229 (3 つ)
        // 92233720* . .02733229 (6 * 10 ** 1)
        // 9223372*. . ..2733229 (9 * 10 ** 2)
        // 922337*.. . ...733229 (7 * 10 ** 3)
        // 92233*... . ....33229 (2 * 10 ** 4)
        // 9223*.... . .....3229 (6 * 10 ** 5)
        // 922*..... . ......229 (6 * 10 ** 6)
        // 92*...... . .......29 (7 * 10 ** 7)
        // 9*....... . ........9 (7 * 10 ** 8)
        // *........ . ......... (0 * 10 ** 9)
        return countPalindromics_(19) - count;
    }

    public static long kaibunZ(long max) {
        // kaibunY() を汎用的にして 10 ** 18 から max までを求めるようにした
        String s = "" + max;
        int keta = s.length();
        int nums[] = new int[keta / 2 + 1];
        for (int k = keta / 2; k >= 0; k--) {
            nums[k] = Integer.parseInt("" + s.charAt(keta / 2 - k));
        }
        ;

        long count = 0;
        String min_kaibun_str = "";
        for (int p = nums.length - 1; p >= 0; p--) {
            min_kaibun_str += nums[p];
        }
        for (int p = 1; p < nums.length; p++) {
            min_kaibun_str += nums[p];
        }
        if (Long.parseLong(min_kaibun_str) > max) {
            count++;
        }

        for (int k = 0; k <= keta / 2; k++) {
            // System.out.println("delta: " + (long)((9 - nums[k]) * Math.pow(10, k)));
            count += (long) ((9 - nums[k]) * Math.pow(10, k));
        }

        // System.out.println(
        // "" + countPalindromics_(keta + 1) + ", " + countPalindromics_(keta) + ", " +
        // count
        // );
        return countPalindromics_(keta) - count;
    }
}

実行結果
イメージ説明

いろいろかいていますが、 

System.out.println(kaibunZ(Long.MAX_VALUE) - kaibunZ((long) Math.pow(10, 18)));
System.out.println(kaibunZ(Long.MAX_VALUE) - countPalindromics_(18));


が、求めるものです。
kaibunZ(n)は 1.. n までの 回分数の数を求めるメソッドです。

1 番目のものは、 1 .. Long.MAX_VALUE までの回分数の数から 1 .. 10 ^ 18 までの 回分数の数を引いたものです。
1 .. 10** 18 までの 回分数の数は, countPalindromics_(18) で計算しても OK です。

kaibun1(n)、kaibun0(n) は、実際に 1.. n をループして回分数の数をかぞています。
Byte.MAX_VALUE, や Short.MAX_VALUE で
kaibun1(n)、kaibun0(n), kaibun0Z(n) の結果が一致することを確認してみています。

countPalindromics_(n) は、ちょっと書き換えてみました。
(n = 1, 2, 3 ... に対して z10, 19, 109, 199, 1099, 1999, 10999, 19999, 109999
という数字のパターンなるので、そのパターンを生成するようにロジックを組んでいます)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/04/21 22:24

    すべての質問に答えてくださりありがとうございましす。とても参考になりました。
    ・桁数から回文数の個数を求める計算が簡潔になりました。
    ・Long.MAX_VALUEから19桁の上限まで場合を数えるほうが楽なことがわかりました。

    ベストアンサーをさしあげたいのですが、一度質問をクローズしてしまったので、今回はご容赦ください。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.37%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る