How to divide a big number into other smaller numbers ..

M

mehbub

New member
Joined
Oct 5, 2008
Messages
3
Hi all

I need an urgent help regarding this simple problem. How can I divide a big number (like 1324) into 3 smaller numbers (like, 7,8,10) so that the reminder is lowest. For example, I like to divide 1324 into multiples of 7, 8 and 10 like,
(7 X 52) + (8 X 52) + (10 X 52) = 1300 , now the remainder is, 1324 - 1300 = 24
My problem is, I need to divide it in such a way so that the final remainder from 1324 is the lowest, something like 0 or 1, not 24. From the above example you can see that if I increase 8 by 1 and 10 by 1 the remainder will be less than 24 :
(7 x 52) + (8 X 53) + (10 X 53) = 1318 . Now the remainder is 1324 - 1318 = 6 . But is it possible to refine it so that the remainder is less than 6 ? Is there a mathematical way to do this ? Please help me. Thanks in advance to all.


Mehbub
 
Nope...numerous solutions (using your example):
if 0 allowed, 1603 solutions leaving 0 remainder, from 0(7), 3(8), 120(10) to 188(7), 1(8), 0(10)
if not allowed, 1527 solutions leaving 0 remainder, from 2(7), 5(8), 127(10) to 184(7), 2(8), 2(10)

7a + 8b + 10c = 1324
c = (1324 - 7a - 8b) / 10

You'd need 2 more equations for a unique solution.
 
mehbub said:
Hi all

I need an urgent help regarding this simple problem. How can I divide a big number (like 1324) into 3 smaller numbers (like, 7,8,10) so that the reminder is lowest. For example, I like to divide 1324 into multiples of 7, 8 and 10 like,
(7 X 52) + (8 X 52) + (10 X 52) = 1300 , now the remainder is, 1324 - 1300 = 24
My problem is, I need to divide it in such a way so that the final remainder from 1324 is the lowest, something like 0 or 1, not 24. From the above example you can see that if I increase 8 by 1 and 10 by 1 the remainder will be less than 24 :
(7 x 52) + (8 X 53) + (10 X 53) = 1318 . Now the remainder is 1324 - 1318 = 6 . But is it possible to refine it so that the remainder is less than 6 ?

Looking at the problem you can tell that 24 exacly divides into 8 - so the remainder could be made to zero.

7*52 + 8*55 + 10*52 = 1324

Is there a mathematical way to do this ? Please help me. Thanks in advance to all.


Mehbub
Click to expand...
 
"looking" also shows: 130*10 = 1300; so 3*8 = 24; 0*7 + 3*8 + 130*10 = 1324
 
Denis and Khan.....thanks a lot. But actually I was looking for a mathematical formula to do that. So that I can divide one big number into other 3 or 4 or 5 smaller numbers. For example : 2345 into multiples of 6, 7, 4 or 432234 into multiples of 5, 7, 6, 9 or 3455 into multiples of 6, 9 etc.

7a + 8b + 10c = 1324
c = (1324 - 7a - 8b) / 10

You'd need 2 more equations for a unique solution.

Denis you provided some hint above. Can you help me to form a formula to do this task ? Or is it possible to have a formula to do this task step by step so the final remainder from the original big number is the lowest, not necessarily to be 0. Actually I am writing a program which will take 5 inputs :
Input 1 : A big number which has to be divided into other smaller numbers.
Input 2 : First smaller number
Input 3 : Second smaller number
Input 4 : Third smaller number
Input 5 : Fourth smaller number
After that, the program will divide the big number into the smaller numbers. But I am not getting any formula to do this. Is it possible to form a formula to do this? Thanks again for your help.

Mehbub
 
What is the objective of writing this program?

I am asking this question - because ther are multiple paths to get to one of the answers.

There are no "standard" formulas - but there are methods.

One of the methods would be to use MOD statement to calculate remainder of a division operation.

Are you familiar with that statement?
 
Hi all

I need an urgent help regarding this simple problem. How can I divide a big number (like 1324) into 3 smaller numbers (like, 7,8,10) so that the reminder is lowest. For example, I like to divide 1324 into multiples of 7, 8 and 10 like,
(7 X 52) + (8 X 52) + (10 X 52) = 1300 , now the remainder is, 1324 - 1300 = 24
My problem is, I need to divide it in such a way so that the final remainder from 1324 is the lowest, something like 0 or 1, not 24. From the above example you can see that if I increase 8 by 1 and 10 by 1 the remainder will be less than 24 : (7 x 52) + (8 X 53) + (10 X 53) = 1318 . Now the remainder is 1324 - 1318 = 6 . But is it possible to refine it so that the remainder is less than 6 ? Is there a mathematical way to do this ? Please help me. Thanks in advance to all.

The expression ax + by = c, "a" and "b" relatively prime, "c" > a(b), has positive integer solutions if d = g.c.d.(a,b) divides "c". If the g.c.d.(a,b) = d, d must divide c evenly for integral solutions.
Your problem is expressed by 7a + 8b + 10c = 1324.
With the coefficient of c being 10, the sum of 7a + 8b + 10c must be 1320, resulting in the smallest remainder of 4.

There are many integer solutions to 7a + 8b + 10c = 1320. The following will show you how to derive them.
1--7a + 8b + 10c = 1320
2--Assuming values c = 1, 2, 3, 4, 5,..., we can derive equations of the following form:
...7a + 8b = 1310
...7a + 8b = 1300
...7a + 8b = 1290
...7a + 8b = 1280 etc.
3--The greatest common divisor of 7 and 8 being 1, there are "many" solutions that will yield 7a + 8b + 10c = 1320 having the smallest remainder of 4.
4--Take 7a + 8b = 1310 (c = 1)
5--Dividing through by 7 yields a + b/7 = 187 + 1/7
6--(b - 1)/7 must be an integer k making b = 7k +1
7--Substituting back into (4) yields 7a + 56k + 8 = 1310 or a = 186 - 8k.
8--k..0....1....2....3....4...etc.
...a.186..178..170..162..154...etc.
...b..1....8...15...22...29...etc.(Solutions with remainder of 4)
9--Taking 7a + 8b = 1300 (c = 2)
10--Dividing through by 7 yields a + b + b/7 = 185 + 5/7
11--(b - 5)/7 must be an integer k making b = 7k + 5
12--Substituting back into (4) yields a = 180 - 8k
13--k..0....1....2....3....4...etc.
....a.180..172..164..156..148...etc.
....b..5...12...19...26...33...37c.
14--Similarly, for 7a + 8b = 1290 (c = 3), a = 182 - 8k and b = 7k + 2 or
15--k..0....1....2....3....4...etc.
....a.182..174..166..158..150...etc.
....b..2....9...16...23...30...etc.

As you can readily see, there are many solutions.

Another way to solve equations with 3 variables with integer solutions is shown in the following example

Joe came back from a stamp collectors gathering and told his sister, Jill, that he bought a hundred stamps. Joe said he bought the stamps at four different prices: $0.59, $1.99, $2.87, and $3.44 each. Jill asked, "How much did you pay altogether?" Joe replied, "One hundred dollars exactly." How many stamps did Joe buy at each
price?

Given: (1)--W + X + Y + Z = 100 and (2)--.59W + 1.99X + 2.87Y + 3.44Z = 100.
1--Multiply (2) by 100--->59W + 199X + 287Y + 344Z = 10000. (3)
2--Multiply (1) by 59----->59W + 59X + 59Y + 59Z = 5900. (4)
3--Subtract (4) from (3)--->140X + 228Y + 285Z = 4100. (5)
4--Divide (5) through by 140--->X + Y + 88Y/140 + 2Z + 5Z/140 = 29 + 40/140.
5--Solving for X = 29 - Y - 2Z - (88Y + 5Z - 40)/140. (6)
6--Set (88Y + 5Z - 40)/140 = u = an integer.
7--Rearranging, 140u = 88Y + 5Z - 40. (7)
8--Dividing (7) through by 5--->28u = 17Y + 3Y/5 + Z - 8. (8)
9--Solving for Z, Z = 28u - 17Y - 3Y/5 + 8. (9)
10--With 3Y/5 = integer, multiply by 2 yielding 6Y/5. (10)
11--Dividing (10) out yields 6Y/5 = Y + Y/5 where Y/5 must be an integer also.
12--Set Y/5 = v whence Y = 5v. (11)
13--Substituting (11) into (8)--->Z = 28u - 85v - 3v + 8 = 28u - 88v + 8. (12)
14--Substituting (11) and (12) into (6)--->X = 29 - 5v -56u + 176v -16 - (440v + 140u - 440v + 40 - 40)/140. (13)
15--Simplifying (13)--->X = 29 - 5v -56u + 176v - 16 - u = 13 + 171v - 57u. (13)
16--Substituting (11), (12), and (13) into (1)---> W + 13 + 171v - 57u + 5v + 28u - 88v + 8 = 100. (14)
17--Simplifying (14)---> W = 29u - 88v + 79. (14)
18--From (11) v =/> 1 and from (12) u =/> 3.
19--Trying v = 1 and u = 3, W = 78, X = 13, Y = 5, and Z = 4.
20--Checking--->78 + 13 + 5 + 4 = 100. Okay.
21--Checking--->78(.59) + 13(1.99) + 5(2.87) + 4(3.44) = 46.02 + 25.87 + 14.35 + 13.76 = 100. Okay.
22--Trying v = 2 and u = 3, X = 184 exceeding total of 100, therefore invalid.
23--Trying v = 1 and u = 4, X = negative number, therefore invalid.
24--All other values of u and v produce invalid results.
 
mehbub said:
Denis you provided some hint above. Can you help me to form a formula to do this task ? Or is it possible to have a formula to do this task step by step so the final remainder from the original big number is the lowest, not necessarily to be 0.
Click to expand...

1: there is NO FORMULA!

2: if the lowest remainder is not 0, say it's r, then you'll similarly have multiple solutions with remainder r.
 
Hi All

Finally I found some light.. :) Really grateful to you - TchrWill for your detailed explanation. I shall post my solution here once I am done writing my program.
khan, I know the MOD, and thats going to be an important part of my solution. Thanks again all for your help.

Mehbub
 
Since you know - MOD operation - I would write the program following way:

1. Add the prospective divisors = S = D(1) + D(2) + D(3) +D(4) +.....

2. Find the remainder of the division of N(the large input) by S ..... R = S MOD N

3. Then find the smallest remainder by dividing R by D(I) ... F(i) = D(i) MOD R ..... min of F(i) is one of your answers.
 
You must log in or register to reply here.
Top