ABC099<難問>

問題

AtCoder
ある数字Nが与えられる。
1,6,36(6²),216(6³)....,9,81(9²),729(9³)....
の総和で表すとき、項数をもっとも少なくする。項数を求めよ。

考察

N以下で最大の数を無理やり持って来ればいいのではないか。全探査のようにN以下で最大の6の累乗と9の累乗を取って来て比較して大きい方を採用する。これを繰り返せば行けそう。

public static int SelectMaxNumber(int n) {
        int sixMax = 0;
        int nineMax = 0;
        for (int i = 1; Math.pow(6, i) <= n; i++) {
            sixMax = (int) Math.pow(6, i);
        }
        for (int i = 1; Math.pow(9, i) <= n; i++) {
            nineMax = (int) Math.pow(9, i);
        }
        return sixMax <= nineMax ? nineMax : sixMax;
    }

なんども使いそうだったので新しく関数を作る。

        int count = 0;
        while (n >= 6) {
            int a = SelectMaxNumber(n);
            n = n - a;
            count++;
        }

これでcountに項数（和の回数）が蓄積されていき最後にn(1を何回か足す)ことで項数が求まる。

結果 -> 失敗

原因 n = 108 の場合
上記のやり方
108 = 81 + 9 + 9 + 9;
最小にするには
108 = 36 + 36 + 36;
手計算だと理解できるが、プログラムで書くとなると難しい。
やり方自体が間違っていそう.

別案

6^a = 3^a × 2^a
9^b = 3^b × 3^b
を用いることはできないだろうか。
共に3の倍数であるので3くくってみるとする。
N = 3 × ( ) + α
α 偶奇で場合分けする(頭をよぎった）6の累乗は常に偶数9の累乗は常に奇数である。
これが何かに使えるかと行かれたら微妙である。９の累乗の和は偶数になることができてしまう。