Y箱

久し振りに進めました。

和と積が同じになる数列について、その個数ごとの最小のものをみつける問題。
仕事がいそがしかったせいもありますが、時間がかかりました。

苦労したので長ーい解説です。

kから考える

まず思いついたのが、いろいろな数をあてはめてみる方法。1,1,1 1,1,2 1,1,3 ... 1,2,2 1,2,3というような感じです。和と積なら積の方が大きくなりそうなものだけれど、同じになるということは、数列に1が沢山あるということだ。いくつの1があるんでしょうか？

1が最も少なくて済むのは、1以外の数が2だけの時です。
例えばk=17個の場合、1が13個であれば2が4個なので、和は21で積は16。1を12個にすると、和が22に対して積が32になってしまうので、1は13個以上あるということになる。

k個の数列の中に入っている2の数をx個とすると、

和 :
積 :

2を入れたときに和≧積にならなれけばならないので、




xについて解けないので、計算してみると、

x  
1 1
2 2
3 5
4 12
5 27
6 58
7 121
8 248
9 503
10 1014
11 2037
12 4084
13 8179
14 16370

1以外の数が5個になるのはkが27以上、10個になるのはkが1014以上必要ということがわかる。問題の上限の、kが12000個の数でも、1以外の数は13個であることが分ります。

13個ぐらいなら、全数アタックでも行けるかな？と思ったんですが、今度は調べていく数の上限がわからない。だいぶ考えたんだけど、だめ。

nから考える。

常套手段で、逆にnから考えてみます。

お題の中の n=8 なのは、

k=4: 8 = 1 1 2 4
k=5: 8 = 1 1 2 2 2

ですが、ここにある1以外の数「2 4」「2 2 2」は、8を積の形にしたものです。8の積による表現はもう一つ「8」がありますが、1を付けても和と積の値は同じにはなりません。そして、1は、和が積と同じになるために必要なものです。

では、12のkはなんでしょう。12は「2 2 3」「2 6」「3 4」「12」の4通りの積の形に表わせます。それぞれに1を付け加えていって、和と積が同じになるようにしてみます。

2 2 3 1 1 1 1 1  ; k=8
2 6 1 1 1 1      ; k=6
3 4 1 1 1 1 1    ; k=7

こうやってみると、いくつの1を加えるべきかがわかります。。 積-和です。kの値は、これに、リストの個数を加えたものです。なので、 「k=積-和+リストの個数」であることがわかります。

まず、これ、計算できるでしょうか？
nの範囲はどれくらいでしょうか？
予測ができません。
前の考察から、k=12000の場合でも、リストには13個以下しか数が入らないはずなので、溢れるようなら別の手を考えるということで進めます。
実際計算してみると、それほど大きな数にはなりませんでした。


 nの全ての積による表現を求めます。再帰的な定義です。

• nを素因数分解します。
• 素因数が1つであればそのリスト
• 素因数が複数の場合、
•   1つ取り出して(mとする)、残りの数についてのリストを求めます。
•   リストのそれぞれについて以下のものを作り、まとめたものが結果です。
•     それぞれのリストにmを追加したもの。
•     それぞれのリストのいずれか1つの要素にmを掛けたものすべて

分りにくいので、実践です。 
12を素因数分解します。 (2 2 3) です。
要素が1つでないので2 を取ってm1とします。のこりは(2 3)です。
要素が1つでないので2 を取ってm2とします。のこりは(3)です。
要素が1つなので、((3))です。
 (2 3)の結果はm2(2です)と((3))から、
   m2を追加したもの (2 3)
   m2を掛けたもの (6)
 を併せて、((2 3) (6)) となります。

 ((2 3) (6)) と m1(これも2)から、
     m1を追加したもの (2 2 3) (2 6)
     m1を掛けたもの (4 3) (2 6) (12)
 併せて重複を消すと、((2 2 3) (2 6) (3 4) (12)) となります。


さて、 これで一通り手順が揃いました。

以下がコードです。
20秒程度で結果が出ているので上々でしょう。


--

まずは、積表現の生成処理達です。

・  destribute-n
上の説明の(mを掛けたもの)を作る処理です。

・ add-n
(mを追加したもの)を作って(mを掛けたもの)をくっつけます。

・product-list
再帰的にリストを生成します。
小さな数の結果を使って大きな数の結果を得るために、メモ化しています。

ここからは、k関連の処理です。

・calc-k
積表現からkの値を計算します。

・all-k-data
本体です。
1から与えられた上限までのkのアレイを作って、nの値を埋めていきます。
生成されるkとnは重複していますが、小さい方を取るので、後からのものは破棄します。
全てのkに対するnのリストを出力します。

・pe88
回答にするために、2からにして、重複を取り除いて、足してます。


Clojure勉強会でtestを入れることを学びました。
機能の説明にもなっていて、「いいねこれ」です。