Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Efficient enumeration of pandigital fractions

by bliako (Monsignor)
on Jul 21, 2018 at 02:15 UTC ( [id://1218979]=note: print w/replies, xml ) Need Help??


in reply to Efficient enumeration of pandigital fractions

... 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).

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1218979]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2024-04-24 13:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found