CPhill

avatar
BenutzernameCPhill
Punkte130555
Membership
Stats
Fragen 56
Antworten 43469

 #2
avatar+130555 
+6
28.06.2015
 #1
avatar+130555 
+15

There are probably easier ways to do this.....but....here's my reasoning.......

 

The "filling" scoop has to operate an odd number of times, because 46,899 *  an odd will produce an odd. And the "removing"  scoop always removes an even number of candies. So, the difference between an odd and an even is always an odd......

 

Let's say the flling scoop operates once and the removing scoop operates 3 times......then the number of candies left in the vat is just  46899 mod (3*13576) =  6171

 

Now...let's say that the filling scoop operates 3 times = 140697 candies added to the vat ....and that the removing scoop operates 10 times = 135760 candies removed from the vat

 

Then 140697 mod 135760 = 4937 ....  and 6171 - 4937 = 1234

 

Lastly....let the filling scoop operate 5 times = 234495 candies added to the vat, and let the "removing" scoop operate 17 times = 230792 candies removed from the vat

 

Then 234495 mod 230792 = 3703   =  6171 x 2(1234)

 

Notice the patern.....for every 2n - 1 times the "filling" scoop operates and for every 3 + 7(n-1) times the "removing" scoop operates, the mod remainder after the first time (where n = 1) = (6171) ... and this is reduced by 1234 for each successive integer value of "n"

 

So.....  6171/1234 = 5

 

This means that, when the "filling" scoop operates n = 5 more times after the first operation, i.e., 2(6) - 1 = 11 total times, the number of candies put into the vat is 11*46899  = 515889.  And the removing scoop will have operated 3 + 7(6-1)  = 38 times  in which 38 * 13576 = 515888 candies have been removed from the vat.....so..... 515889 added - 515888 removed = 1 remaining candy in the vat.....

 

[I'm pretty sure that there is some sort of algorithm for solving this......but....I'm not familiar with what it might be....!!! ]

 

P.S. - I believe this can also be solved by using something known as a"Diophantine" Equation.....I'm not familiar with this technique, but I'm reading about it here.....http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

 

 

 

28.06.2015
 #7
avatar+130555 
+10

 

 

 

 

Euler's Totient Function briefly explained.......I'm certainly no expert, but, after reading some about this, here is a "quick and dirty" explanation of "why it works".......

 

Let  p be some prime number.......then the number of positive integers that are not relatively prime to pk   is just  .... p, 2p, 3p, 4p......pk-1p

 

Then, there must be pk-1 positive integers that are not relatively prime to pk ......{Notice that the last integer is just pk itself}.......So, if this is true.....the number of positive integers that are relatively  prime  to pk must just be  pk - pk-1.....or.....expressed another way......

 

pk - pk-1  =     pk ( 1 - 1/p )........let's look at a simple example.....

 

Let's find φ(1000).........we are aking...."How many positive integers are relatively prime to 1000??"

 

Note that 1000  = 23 * 53  ...so........  φ(1000)  = φ(23 * 53)  = φ(23) * φ(53)......then.....applying our "formula".....we have.......

 

φ(23)  = 23(1 - 1/2)  =  8(1/2)  = 4.........note that this is true......the number of positive integers that are relatively prime to 23 =  (8)  are 1, 3, 5 and 7........seen another way.....pk - pk-1  =  23 - 2(3-1)  = 8 - 4  = 4

 

Now......look at φ(53)......our  "formula"  gives us  53(1 - 1/5)  = 125(4/5)  = 100.....this means that there are 100 positive integers that are relatively prime to 125.....this is easy to see.......the one's that aren't relatively prime to 125 are.....all multiples of 5 from 1-125  =  25 of them.......that means that 100 positive integers are relatively prime to 125  !!!

 

So.....the number of positive integers that are relatively prime to 1000 is just 4 * 100 = 400......Again, this is easy to see.......no even positive integers are relatively prime to 1000......this leaves a possible 500 that are......but all odd multiples of 5 aren't relatively prime to 1000, either, and there are 10 in each 100........for a total of 100 in all......so....   500 - 100 = 400 positive integers that are relatively prime to 1000  !!!

 

Thanks again to Heureka for letting us in on this "trade secret"........this is a pretty neat theorem.....!!!

 

 

28.06.2015