StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First, you don't really need full prime decomposition, only decomposition to primes smaller than your base (I guess you mean 10 here but the problem can be generalized to any base). So we only need factorization into the first 4 primes: 2, 3, 5 and 7. If the rest (prime or not) factor is anything bigger than 1, then the problem has 0 solutions.</p> <p>Now, lets assume that the number <code>p</code> is factored into:</p> <pre><code>p = 2^d1 * 3^d2 * 5^d3 * 7^d4 </code></pre> <p>and is also composed from the <code>n</code> digits:</p> <p><code>p =</code> d<sub>(n-1)</sub>d<sub>(n-2)</sub>...d<sub>2</sub>d<sub>1</sub>d<sub>0</sub> </p> <p>Then, rearranging the digits, is will also be:</p> <pre><code>p = 2^q2 * 3^q3 * 4^q4 * 5^q3 * ... * 9^q9 </code></pre> <p>where <code>qi >= 0</code> and <code>q2 + q3 + ... q9 = n</code></p> <p>and also (due to the factorization):</p> <pre><code>for prime=2: d1 = q2 + 2*q4 + q6 + 3*q8 for prime=3: d2 = q3 + q6 + 2*q9 for prime=5: d3 = q5 for prime=7: d4 = q7 </code></pre> <p>So the <code>q5</code> and <code>q7</code> are fixed and we have to find all non-negative integer solutions to the equations:<br> (where the unknowns are the rest <code>qi</code>: <code>q2, q3, q4, q6, q8 and q9</code>)</p> <pre><code> d1 = q2 + 2*q4 + q6 + 3*q8 d2 = q3 + q6 + 2*q9 n - d3 - d4 = q2 + q3 + q4 + q6 + q8 + q9 </code></pre> <p>For every one of the above solutions, there are several rearrangements of the digits, which can be found by the formula:</p> <pre><code>X = n! / ( q2! * q3! * ... q9! ) </code></pre> <p>which have to be summed up.</p> <p>There may be a closed formula for this, using generating functions, you could post it at Math.SE</p> <hr> <p>Example for <code>p=24</code>, <code>n=3</code>:</p> <pre><code>p = 2^3 * 3^1 * 5^0 * 7^0 </code></pre> <p>and we have:</p> <pre><code>d1=3, d2=1, d3=0, d4=0 </code></pre> <p>The integer solutions to:</p> <pre><code>3 = q2 + 2*q4 + q6 + 3*q8 1 = q3 + q6 + 2*q9 3 = q2 + q3 + q4 + q6 + q8 + q9 </code></pre> <p>are <code>(q2, q3, q4, q6, q8, q9) =</code>:</p> <pre><code>(2, 0, 0, 1, 0, 0) (1, 1, 1, 0, 0, 0) </code></pre> <p>which give:</p> <pre><code>3! / ( 2! * 1! ) = 3 3! / ( 1! * 1! * 1! ) = 6 </code></pre> <p>and <code>3+6 = 9</code> total solutions.</p> <hr> <p>Example for <code>p=3628800</code>, <code>n=10</code>:</p> <pre><code>p = 2^8 * 3^4 * 5^1 * 7^1 </code></pre> <p>and we have:</p> <pre><code>d1=8, d2=4, d3=1, d4=1 </code></pre> <p>The integer solutions to:</p> <pre><code>8 = q2 + 2*q4 + q6 + 3*q8 4 = q3 + q6 + 2*q9 8 = q2 + q3 + q4 + q6 + q8 + q9 </code></pre> <p>are <code>(q2, q3, q4, q6, q8, q9)</code> (along with the corresponding digits and the rearrangements per solution):</p> <pre><code>(5, 0, 0, 0, 1, 2) 22222899 57 10! / (5! 2!) = 15120 (4, 0, 2, 0, 0, 2) 22224499 57 10! / (4! 2! 2!) = 37800 (4, 1, 0, 1, 1, 1) 22223689 57 10! / (4!) = 151200 (3, 2, 1, 0, 1, 1) 22233489 57 10! / (3! 2!) = 302400 (4, 0, 1, 2, 0, 1) 22224669 57 10! / (4! 2!) = 75600 (3, 1, 2, 1, 0, 1) 22234469 57 10! / (3! 2!) = 302400 (2, 2, 3, 0, 0, 1) 22334449 57 10! / (3! 2! 2!) = 151200 (2, 4, 0, 0, 2, 0) 22333388 57 10! / (4! 2! 2!) = 37800 (3, 2, 0, 2, 1, 0) 22233668 57 10! / (3! 2! 2!) = 151200 (2, 3, 1, 1, 1, 0) 22333468 57 10! / (3! 2!) = 302400 (1, 4, 2, 0, 1, 0) 23333448 57 10! / (4! 2!) = 75600 (4, 0, 0, 4, 0, 0) 22226666 57 10! / (4! 4!) = 6300 (3, 1, 1, 3, 0, 0) 22234666 57 10! / (3! 3!) = 100800 (2, 2, 2, 2, 0, 0) 22334466 57 10! / (2! 2! 2! 2!) = 226800 (1, 3, 3, 1, 0, 0) 23334446 57 10! / (3! 3!) = 100800 (0, 4, 4, 0, 0, 0) 33334444 57 10! / (4! 4!) = 6300 </code></pre> <p>which is <code>2043720</code> total solutions, if I haven't done any mistakes..</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