StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I don't think I'd start by tackling what is known to be a 'hard' problem, computing the prime decomposition. By <em>I don't think</em> I mean <em>my gut feeling, rather than any rigorous computation of complexity, tells me</em>. </p> <p>Since you are ultimately only interested in the single-digit divisors of <code>p</code> I'd start by dividing <code>p</code> by <code>2</code>, then by <code>3</code>, then <code>4</code>, all the way up to <code>9</code>. Of course, some of these divisions won't produce an integer result in which case you can discard that digit from further consideration.</p> <p>For your example of <code>p = 24</code> you'll get <code>{{2},12}, {{3},8}, {{4},6}, {{6},4}, {{8},3}</code> (ie tuples of divisor and remainder). Now apply the approach again, though this time you are looking for the 2 digit numbers whose digits multiply to the remainder. That is, for <code>{{2},12}</code> you would get <code>{{2,2},6},{{2,3},4},{{2,4},3},{{2,6},2}</code>. As it happens all of these results deliver 3-digit numbers whose digits multiply to <code>24</code>, but in general it is possible that some of the remainders will still have 2 or more digits and you'll need to trim the search tree at those points. Now go back to <code>{{3},8}</code> and carry on.</p> <p>Note that this approach avoids having to separately calculate how many permutations of a set of digits you need to consider because it enumerates them all. It also avoids having to consider <code>2*2</code> and <code>4</code> as separate candidates for inclusion.</p> <p>I expect you could speed this up with a little memoisation too.</p> <p>Now I look forward to someone more knowledgeable in combinatorics telling us the closed-form solution to this problem.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload