The missing step is showing that the greedy-algorithm candidate doesn't have more digits than the non-greedy one. Andy On Sat, Jun 4, 2016 at 11:10 AM, Marc LeBrun <mlb@well.com> wrote:
Maybe something roughly like this will prove it: say the Greedy algorithm returns G but a Hypothetical optimal algorithm returns H. Both G and H must be the same length and their digits will be non-decreasing left-to-right.
Between any two such candidate values the most right-heavy set of digits will be the most left-light, and hence the smallest. But, for H to be different from G, Hypothetical must at some step have picked a lighter digit than Greedy. Hence its result will be right-lighter, so... contradiction?
="David Wilson" <davidwwilson@comcast.net>
To find smallest base-b number with digit product p.
The greedy method would be to repeatedly divide p by the largest base-b digit divisor until 1 is reached, then concatenate the divisor digits in reverse order. (If 1 is not reached, the number is not a product of base-b digits).
For example, to find the smallest base 10 number with digit product p = 3628800
3628800/9 = 403200 403200/9 = 44800 44800/8 = 5600 5600/8 = 700 700/7 = 100 100/5 = 20 20/5 = 4 4/4 = 1
So, ostensibly, the smallest base-10 number with digit product 3628800 is 45578899(10).
Is the greedy algorithm correct for this problem? Could it be possible that dividing by a smaller digit at some step leads to an smaller result? For example, in base 20, for some large p, might it be better to divide first by digit 16 rather than digit 18?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com