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

Question

**回文数 (Palindromic Number) **

数字の桁を逆から並べた数がもとの数に等しいものを回文数という。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 に含まれる回文数の個数を求めたい。

Answer 1

考え方を整理するために、まず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桁までの回文数の個数を足せば、求める答えが得られます。

Comments

[xebme]

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

Answer 2

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

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

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

Comments

[xebme]

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

[xebme]

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

Answer 3

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
という数字のパターンなるので、そのパターンを生成するようにロジックを組んでいます)

Comments

[xebme]

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

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

Answer 4

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,2047+822,337,2033=8,223,372,037 通り

のような気がします。

Comments

[xebme]

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

Answer 5

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の範囲を超えるものを除外すればいいです。

Comments

[majiponi]

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

[swordone]

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

[swordone]

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

[xebme]

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

Answer 6

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

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

Comments

[xebme]

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