３桁の数の積で表される回文数の最大値を求める処理を、プログラミングで完結させたい。

Question

お世話になっております。
ネットでプログラミング数学というサイトの問題を解いてたときの話なのですが、

**問題**

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

という問題があり、プログラミングを使って解いていて、解けはしたのですが、プログラミングを上手く生かしきれず、最終的には出力結果とにらめっこしてマッチする値を探すという手段で答えを出したのですが、プログラミング的にはどうなのかと思い質問しました。

値が６桁の場合、[1][2][3][3][2][1]のような関係があるのは気付いたのですが、プログラミングでの記述方法がわかりませんでした。

↓は私が書いたコードなのですが、プログラミングでこの問題の処理を完結させて、答えを出力させることはできるのでしょうか？

public class hoge {
	public static void main( String[] args ){
		int a = 0;
		int c = 0;
		for( int i = 0; i < 90; i++ ){
			for( int j = 0; j < 90; j++ ){
				a = (999-j)*(999-i);
				String b = String.valueOf( a );
				if( b.matches( "^9.*" ) ){
					if( b.matches( ".*9$" ) ){
						c++;
						System.out.println( "【j=" + j + "】【i=" + i + "】" + a );
					}
				}else if( b.matches( "^8.*" ) ){
					if( b.matches( ".*8$" ) ){
						c++;
						System.out.println(  "【j=" + j + "】【i=" + i + "】" + a );
					}
				}
			}
		}
		System.out.println( "出力結果は" + c + "通りです。" );
	}
}

Answer 1

整数 n が回文数かどうかは以下の関数で判別することができます。

public static boolean isPalindrome(int n) {
    String string = String.valueOf(n);
    String reverse = new StringBuilder(string).reverse().toString();
    return string.equals(reverse);
}

これを使ってこんな風に求めることができます。

int max = -1, max1 = -1, max2 = -1;
for (int i = 100; i <= 999; ++i) {
    for (int j = i; j <= 999; ++j) {
        if (isPalindrome(i * j)) {
            if (i * j > max) {
                max = i * j;
                max1 = i;
                max2 = j;
            }
        }
    }
}
System.out.printf("max: %d = (%d * %d)%n", max, max1, max2);
-> 
max: 906609 = (913 * 993)

Comments

[退会済みユーザー]

結果に影響はないですが、３桁どうしの掛け算なので i < 999, j < 999 のところは
i <= 999, j <= 999 または　i < 1000, j < 1000にすべきだと思います。

[退会済みユーザー]

@Stars1024 さん ありがとうございます。

[退会済みユーザー]

@game-overさんへ
ソースコードを変更して頂き、ありがとうございました。

Answer 2

Problem 4 - Project Euler の問題ですね。

汎用性を持たせるなら任意のN桁について解けるようなロジックを考えるべきでしょう。

最大の数と言うことから、一番大きい数、999 * 999 = 998001から探していくというのが早いだろうということがわかります。しかし、二つの積の部分、999と999の二つを減らしていくとなると、組合せが膨大で、かつ、片方だけを減らしていっても、ちょうどうまい具合のものを見逃してしまいそうです。ですので、減らしていくのは9998001の方です。

9998001の減らしていくと言っても回文になるパターンは非常に少ないです。6桁の場合は1000分の1個しか回文になりません。それもそのはずです。単純に前の3桁が決まれば、対応する回文が決定されるからです。

998 -> 998899
997 -> 997799
996 -> 996699
...

という感じにです。つまり、減らしていくのは前3桁だけが必要です。前3桁さえ決まれば、後3桁も自動的に決まります。そして、重要なことは、前3桁の大小は回文になったときの大小と一致すると言うことです。つまり、998から減らしていって、条件を満たす数がみつかれば、その数が最大となるというわけです。(減らす限界は100までである。それ以下の場合は5桁になるため、この方法では回文が得られない。)

こうして、回文候補は大きい方から順に上げることが出来るようになりました。次は、それらが3桁同士の積になるかどうかです。

条件を満たすのであればn = a * b(nは回文になる数、a ≧ b)となる3桁の整数aとbが存在することになります。このときaは3桁なので999以下です。では逆にあり得る最小はいくつでしょうか？それは√nです。もし、aが√nより小さい場合、bはa以下であるため、a * bは√n * √n = nより小さくなってしまいます。つまり、もしaが存在するなら、aは999から√nの間の数となります。

後はわかりますよね。999から√nまでの整数に対して、回文の数nが割り切れるかどうかを確認するだけです。もし、割り切れれば、bが存在し、その数はa以下であるため、3桁以内になります。(bが2桁以下であることは確認しなくても良い。最大のパターンでも999 * 99 = 98901と5桁になるため、6桁を前提しているときには2桁以下になることはない)

桁数を増やしても最大の数が9999、99999と増えていくだけ、同じ考え方で解くことが出来ます。

稚拙ですが、参考までにRubyでの実装例です。

def int2list(n)
  list = []
  while (n > 0)
    n, r = n.divmod(10)
    list << r
  end
  list
end

def list2int(list)
  list.each_with_index.map { |n, i| n * (10 ** i) }.sum
end

def palindrome(n)
  list = int2list(n)
  n * (10 ** list.size) + list2int(list.reverse)
end

def search_palindrome(digit)
  max_n = 10 ** digit - 1
  n = max_n ** 2 / 10 ** digit
  n.downto(10 ** (digit - 1)) do |i|
    pn = palindrome(i)
    max_n.downto(Integer.sqrt(pn)) do |j|
      if pn % j == 0
        return pn, j, pn / j
      end
    end
  end
  nil
end

printf("%d = %d * %d\n", *search_palindrome(2))
printf("%d = %d * %d\n", *search_palindrome(3))
printf("%d = %d * %d\n", *search_palindrome(4))
printf("%d = %d * %d\n", *search_palindrome(5))
printf("%d = %d * %d\n", *search_palindrome(6))
printf("%d = %d * %d\n", *search_palindrome(7))
printf("%d = %d * %d\n", *search_palindrome(8))

計算量は桁数の指数関数オーダー以上のようです(正確なものはよくわからない)。9桁は時間がかかりすぎてRubyでは求められませんでした。C++あたりで書き直せばできるかとも思います。

Comments

[Nerd_run.]

回答ありがとうございます。
そうです、そのサイトです。　英語が読めないので和訳版ですが。

応用は聞かないのを書き直して見たらめちゃくちゃ処理が重く、ｐｃ的に無理そうなのができました(´o｀；

public class hoged {
public static void main( String[] args ){
int a = 999 * 999 / 1000;
for( int i = 0; i < 10; ){
for( int j = 0; j < 10; j++ ){
int b = ( 999 - i ) * ( 999 - j );
String aa = String.valueOf( b );
for( int l = 0; l < 100; l++ ){
int c = a - l;
String bb = String.valueOf( c );
if( aa.matches( "^bb.*" ) ){
System.out.println( bb );
}
}
}
}
}
}

[raccy]

二つの積の両方をループで回せば最大値に対する2乗のオーダーの計算量になるので遅くなりますよ。いかに片方だけをいくつまで回せば確認が完了できるか考えるのかが重要です。

[Nerd_run.]

あ、重いのは無限ループでした。
んー、難しい。

[退会済みユーザー]

> いかに片方だけをいくつまで回せば確認が完了できるか考えるのかが重要です。

ん？最も重要なのは、いかに回文を作り出すかでは？

[raccy]

> ん？最も重要なのは、いかに回文を作り出すかでは？

え？引っかかる所ってそっちなの？私が競プロに毒されているだけ？

[退会済みユーザー]

> 重要なことは、前3桁の大小は回文になったときの大小と一致すると言うことです。

回文が作れることに気がつくことと、上記が最重要かなぁと思ったので。
でも言い換えると、`いかに片方だけを回せば`ってことになるから、あんまり意味のない指摘でしたね。失礼＾＾；

Answer 3

「3桁の数の積」の最大値は
(1000-1)^2=998001
なので、これ以下で回分数になる数を求めるなり作るなりして、
回分数を素因数分解などして3桁×3桁にできるかチェックしていくというのはどうでしょう？

Comments

[Nerd_run.]

回答ありがとうございます。
回文数の部分はプログラムで求めることはできないのでしょうか？

[swordone]

[1][2][3][3][2][1]のようになっているということは、
(100000+1)*[1]+(10000+10)*[2]+(1000+100)*[3]のような計算で求められるということになります。この考えで順次ループさせて作ることができます。

Answer 4

今更ですが、答えが6桁であることを前提にすると、abccbaと表すことができて、
abccba = 100001 * a + 10010 * b + 1100 * c

ここで100001、10010、1100はすべて11の倍数です。なので6桁の回文数は11の倍数であると分かります。

回文数を生成して3桁の数の積であらわせるかをチェックする戦略と、3桁の数の積を生成して回文数であるかをチェックする戦略が考えられますが、どちらにおいても、この「11の倍数である」であるという性質を利用すれば多少高速化できると思います(計算量のオーダーは変わりませんが)。

Answer 5

回答してくださった皆様、ありがとうございます。
拙いコードですが、一発で結果を出力することができました。

public class hoged {
	public static void main( String[] args ){
		for( int i = 1000; i > 900; i-- ){
			for( int j = 1000; j > 900; j-- ){
				int a = i * j;
				String str = String.valueOf( a );
				StringBuffer sb = new StringBuffer( str );
				String str_2 = sb.reverse().toString();
				if( str.matches( str_2 ) ){
					System.out.println( str + " =    " + i +" x " + j );
					return;
				}				
			}
		}
	}
}

Answer 6

まあ　回文数になるプログラム（コピペを避けるために別言語で）

<?php
 
$k = 0;
for ( $i = 101; $i < 1000; $i++) {
    for ( $j = 101; $j < 1000; $j++) {
        $x = $i * $j;
 
        $str = ($x."");
        $rev = strrev($x.""); // 文字列反転
 
        if ($str == $rev) { // 反転結果と一致してるかどうか
            // echo sprintf("%4d", $i);
            // echo sprintf("%4d", $j);
            // echo " ";
            echo $str . PHP_EOL;
            $k++; // 件数を確認
             // ここで最大値判定をする
        }
    }
}
// echo $k . "件" .PHP_EOL;

というように文字列反転して比較してしまえばいいのです。

Comments

[Nerd_run.]

回答ありがとうございます。
一番シンプルでわかりやすかったです。
件数は出力とにらめっこできるレベルか見るために表示してたものなんですが、
丁寧にありがとうございますｗ

Answer 7

値が６桁の場合、[1][2][3][3][2][1]のような関係があるのは気付いたのですが、プログラミングでの記述方法がわかりませんでした。

この部分ですが、複数の問題に分割すれば簡単に記述可能かと思います。
コードそのものを書くと考える余地が無くなってしまいますので、問題分割の概要のみの回答とさせて頂きます。

1. 数値の桁数を求める。
2. 各桁の数値を取り出す。
3. 回文数かどうか判定する。

まず1.ですが、これは10を底とするlogを計算し、結果を切り上げれば実現可能です。java.lang.Mathクラスにはlog10(double)メソッドとceil(double)メソッドが有りますので、これを使えば簡単かと。

2.に関しては、簡単な数学の問題です。例えば数値aの3桁目の値は「aを100で割って、その値を10で割った余り」です。

3.に関しては、特に解説は不要かと思います。先頭と末尾から順番に判定すれば良いだけですので。

Comments

[Nerd_run.]

難しい(*_*)

[rtr1950x]

一個一個の問題は比較的簡単なので、まずは手計算で概要を掴んで、それから実装してみてはどうでしょうか？

他の方の回答にある様に文字列に変換して比較するのが「楽」ではありますが。
ただ、今後のスキルアップを目標にするなら、頑張って実装してみてはどうかと思います。

[Nerd_run.]

ありがとうございます。
他の方もわかりやすく書いてくださっているので参考にうまくいくまでやって見ます。

Answer 8

3桁の数の積で表される可能性のある回文は
[1][0][0]/[0][0][1]
から
[9][9][9]/[9][9][9]
つまり100-999の組み合わせで記述できます。

ので、先に全回文を作って、それを3桁の数字で割ってみるのがワリと手っ取り早い気がします。3桁の数字のでかい方から割れば、最大値はサクッと見つかるのでは？

追記
php で書いてみました。
上記以外に、ちょっと条件が必要でした＾＾；

<?php
function make_palindrome_array(){
    $palindrome_array = [];
    for ($i = 999; $i >= 100; --$i){
        $palindrome = (string)$i . strrev((string)$i);
        $palindrome_array[] = (int)$palindrome;
    } 
    return $palindrome_array;
}
$palindrome_array = make_palindrome_array();
foreach($palindrome_array as $palindrome){
    for($j = 999; $j >= 100; --$j){
        if($palindrome % $j === 0){
            if($palindrome / $j <= 999){
                echo '最大の回文は'.$palindrome.PHP_EOL;
                echo '組み合わせは ' . $j . ' と ' . $palindrome / $j . PHP_EOL;
                break 2;
            }
        }
    }
}