... restate the problem as abcd = efgh * i
this can go a bit further:
abcd = efgh * i
a * 10^3 + b * 10^2 + c * 10^1 + d * 10^0 =
(e * 10^3 + f * 10^2 + g * 10^1 + h * 10^0) * i
=> (e*i-a)*10^3 + (f*i-b)*10^2 + (g*i-c)*10^1 + (h*i-d)*10^0 = 0
for the above to have a chance to be zero:
1)
((h*i-d) * 10^0) % 10^1 = 0 (e.g. must end in 0)
2)
The cumulative sum of the above at position J,
(i.e. from right to left, J=0 for the term (h*i-d) * 10^0 )
must also end in zeros as follows:
cum-sum at pos J=1 must end in 00
cum-sum at pos J=2 must end in 000
etc.
3)
The cumulative sum of the above at position J,
from right to left must also not be less than:
cum-sum at pos J+1 >= 100
cum-sum at pos J+2 >= 1000
etc.
As an example, for the fraction: 6952 / 1738 = 4 it is true that:
(8*4-2)*10^0=30
... (ends in 0),
((8*4-2)*10^0+(3*4-5)*10^1)=100
... (ends in 00 and is not less than 10^2)
((8*4-2)*10^0+(3*4-5)*10^1+(7*4-9)*10^2)=2000
... (ends in 00 and is not less than 10^3)
etc.
For base-10 the first rule skips 90% of the cases. And each subsequent rule 90% of the remaining. E.g. 362880 total cases -> 25920 -> 2880 (I used permutations and took the pivot as the missing digit. That can perhaps get better).
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|