高橋の数の算出について


各桁を並び替えてできる最大の数と  
各桁を並び替えてできる最小の数（ただし、 **最高位は0以外** にする）の差が  
自身と一致するとき、高橋の数と呼びます。  
（[http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6](http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6)）

以下のコードで、9桁までの高橋の数を  
求めようとしたのですが、  
9桁の高橋の数の算出に何時間も  
かかっています。  
もっと高速に求める方法があれば、ご教示ください。

[code]

    def takahashi_number(m)
      (10 ** (m - 1)..10 ** m - 1).each{|n|
        ary = n.to_s.split('').map(&:to_i)
        min_ary = ary.sort
        max = min_ary.reverse.join.to_i
        # 最高位を0以外にする←カプレカ数との違い
        i = 0
        while min_ary[i] == 0
          i += 1
        end
        min_ary[0], min_ary[i] = min_ary[i], min_ary[0]
        min = min_ary.join.to_i
        p [m, n] if n == max - min 
      }
    end
    
    (2..9).each{|m| takahashi_number(m)}
    
[/code]

出力結果  
[3, 495]  
[4, 6174]  
[6, 549945]  
[6, 631764]  
[6, 660852]  
[8, 63317664]  
[8, 66308652]  
[9, 554999445]  
[9, 864197532]

（追記）  
（どの言語を用いるにせよ）今のところ、高橋の数は９の倍数であることと  
yoh2さんのアイデアを用いていたコードが一番速いものと思われます。  
このRuby版のコードを作ったので、回答に載せました。  
皆様の参考になれば幸いです。




ある数について、それぞれ高橋の数か？
と判定していくのではなく、各桁について、ある数が何回出現したかという出現数の組から、その組は高橋の数を構成できるか、という判定をしていけば、かなり数を減らせます。  
この方法なら、完全に力技で判定しても、n桁での組み合わせは、C(9 + n, 9) 通り。9桁なら 48,620 通りしかありません。

判定の手順は以下の通り。

  1. 出現数の組で構成できる最小数を求める。
  2. 出現数の組で構成できる最大数を求める。
  3. 2 - 1 を求め、その各桁について出現数を求める。
  4. 3 の結果が、最初の出現数の組と一致しているなら、その出現数の組に対応する高橋の数は 2 - 1。一致していなければ、その出現数の組に対応する高橋の数はない。

以下ふたつばかり例を。  
`count[n]` は、その数における `n` の出現数です。

### 例1

  * 0, 3, 8, 7 が一回ずつ出現する場合、`conut = [1, 0, 0, 1, 0, 0, 0, 1, 1, 0]`。
  * ここから構成できる最小数: 3078
  * ここから構成できる最大数: 8730
  * 差は 5652 で、各桁を数えた結果 `[0, 0, 1, 0, 0, 2, 1, 0, 0, 0]` ≠ `count` なので、この出現数の組では高橋の数は構成できない。

### 例2

  * 1, 4, 6, 7 が一回ずつ出現する場合、`conut = [0, 1, 0, 0, 1, 0, 1, 1, 0, 0]`。
  * ここから構成できる最小数: 1467
  * ここから構成できる最大数: 7641
  * 差は 6174 で、各桁を数た結果 `[0, 1, 0, 0, 1, 0, 1, 1, 0, 0]` = `count` なので、6174は高橋の数。

ruby はできないのですが、面白そうなので C で 1〜18
桁の高橋の数を求める[プログラムを組んでみました](https://gist.github.com/yoh2/970839faf5819326d8f4)。  
このプログラムを使ったところ、 Core i5 2520M で5秒程度で結果を求めることができました。  
既出の枝刈りを行えば、もっと速くできるかもしれません。

→ [高橋の数は 9
の倍数であるという性質を利用した枝刈りを入れてみました](https://gist.github.com/yoh2/970839faf5819326d8f4#file-
takahashi_num_opt_1_18-c)。その結果、1〜18桁すべてを列挙するのに 0.5 秒程度まで縮まりました。




ある数について、それぞれ高橋の数か？
と判定していくのではなく、各桁について、ある数が何回出現したかという出現数の組から、その組は高橋の数を構成できるか、という判定をしていけば、かなり数を減らせます。  
この方法なら、完全に力技で判定しても、n桁での組み合わせは、C(9 + n, 9) 通り。9桁なら 48,620 通りしかありません。

判定の手順は以下の通り。

  1. 出現数の組で構成できる最小数を求める。
  2. 出現数の組で構成できる最大数を求める。
  3. 2 - 1 を求め、その各桁について出現数を求める。
  4. 3 の結果が、最初の出現数の組と一致しているなら、その出現数の組に対応する高橋の数は 2 - 1。一致していなければ、その出現数の組に対応する高橋の数はない。

以下ふたつばかり例を。  
`count[n]` は、その数における `n` の出現数です。

### 例1

  * 0, 3, 8, 7 が一回ずつ出現する場合、`conut = [1, 0, 0, 1, 0, 0, 0, 1, 1, 0]`。
  * ここから構成できる最小数: 3078
  * ここから構成できる最大数: 8730
  * 差は 5652 で、各桁を数えた結果 `[0, 0, 1, 0, 0, 2, 1, 0, 0, 0]` ≠ `count` なので、この出現数の組では高橋の数は構成できない。

### 例2

  * 1, 4, 6, 7 が一回ずつ出現する場合、`conut = [0, 1, 0, 0, 1, 0, 1, 1, 0, 0]`。
  * ここから構成できる最小数: 1467
  * ここから構成できる最大数: 7641
  * 差は 6174 で、各桁を数た結果 `[0, 1, 0, 0, 1, 0, 1, 1, 0, 0]` = `count` なので、6174は高橋の数。

ruby はできないのですが、面白そうなので C で 1〜18
桁の高橋の数を求める[プログラムを組んでみました](https://gist.github.com/yoh2/970839faf5819326d8f4)。  
このプログラムを使ったところ、 Core i5 2520M で5秒程度で結果を求めることができました。  
既出の枝刈りを行えば、もっと速くできるかもしれません。

→ [高橋の数は 9
の倍数であるという性質を利用した枝刈りを入れてみました](https://gist.github.com/yoh2/970839faf5819326d8f4#file-
takahashi_num_opt_1_18-c)。その結果、1〜18桁すべてを列挙するのに 0.5 秒程度まで縮まりました。

