----------------------------------- XXX111 Wed Apr 07, 2010 12:51 pm generating least positive integer (mod function) help ----------------------------------- What is it you are trying to achieve? Write a computer program that finds the least positive integer meeting each of the following conditions: * dividing by 7 gives a remainder of 4 * dividing by 8 gives a remainder of 5 * dividing by 9 gives a remainder of 6 What is the problem you are having? I know how to use the mod function to find the remainder (ex. 60 mod 7 = remainder 4), but I'm stuck on finding a way to generate the lowest positive integer possible Describe what you have tried to solve this problem manually found lowest possible integer Post any relevant code (You may choose to attach the file instead of posting the code if it is too long) % Possible Answers (but they are manual, not program-generated) put 11 mod 7 put 60 mod 7 Please specify what version of Turing you are using Turing 4.0.5 ----------------------------------- apomb Wed Apr 07, 2010 1:14 pm RE:generating least positive integer (mod function) help ----------------------------------- In a loop, calculate all values from 1 - a set value when divided by your required values (7,8,9). Then simply decide which values give the lowest integer. ----------------------------------- XXX111 Wed Apr 07, 2010 1:24 pm Re: RE:generating least positive integer (mod function) help ----------------------------------- In a loop, calculate all values from 1 - a set value when divided by your required values (7,8,9). Then simply decide which values give the lowest integer. Thanks for the quick reply apomb. Can you explain exactly what you mean by "a set value"? Also, how would I exit the loop? if statement? Sorry for the many questions, I'm still very new at turing. ----------------------------------- Brightguy Wed Apr 07, 2010 1:39 pm Re: generating least positive integer (mod function) help ----------------------------------- This is one of those timeless number theory problems. http://en.wikipedia.org/wiki/Method_of_successive_substitution Although, I don't think things like modular inverses are usually taught in high school, so brute force may be expected in HS. ----------------------------------- copthesaint Wed Apr 07, 2010 3:34 pm Re: generating least positive integer (mod function) help ----------------------------------- Just putting this out there, Their is also a rem function in turing that gives you the remainder just like mod, whats the difference between rem and mod? lol They do the exact same thing : var number : real get number put number, " div 8 is ", number div 8 put "You have ", number rem 8, " remaining" put "You have ", number mod 8, " remaining" Edit: nvm, rem can take opposite sign values and give the remainder and mod cannot. ----------------------------------- XXX111 Wed Apr 07, 2010 4:04 pm Re: generating least positive integer (mod function) help ----------------------------------- Just putting this out there, Their is also a rem function in turing that gives you the remainder just like mod, whats the difference between rem and mod? lol They do the exact same thing : var number : real get number put number, " div 8 is ", number div 8 put "You have ", number rem 8, " remaining" put "You have ", number mod 8, " remaining" Edit: nvm, rem can take opposite sign values and give the remainder and mod cannot. Thanks copthesaint, but I am trying to acomplish the opposite function. Instead of asking the user to input the number, the program must generate it itself (no user interaction at all). I think apomb is on the right track but can anyone elaborate further? Thanks ----------------------------------- Brightguy Wed Apr 07, 2010 4:41 pm Re: generating least positive integer (mod function) help ----------------------------------- What kind of solution are you looking for? Do you know how to solve it by hand? This is a textbook [url=http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem]Chinese remainder theorem problem. ----------------------------------- jbking Wed Apr 07, 2010 5:34 pm Re: generating least positive integer (mod function) help ----------------------------------- Assuming the divisors are co-prime, couldn't one reduce to solve this? For example, just taking the last pair of required values. While this may seem like a brute force idea, there may be optimizations to be made in some way. For example, 9 mod 8 is 1 so this means that 9k+6 will be 6+k mod 8 so to get 5 mod 8, simply let k=7 as we'd have to cycle all the way around from 6, so this produces 69 mod 72 for the values that will yield both 5 mod 8 and 6 mod 9. There is a cavaet with some of this as 6*6*6 mod 9 = 0, so some Chinese Remainder Theorem work around may be needed. Notice that one could reverse the process in a way. 8 mod 9 is also -1 so it deducts one each time so starting at 5 to cycle around to 6 mod 9, use 8 as a multiplier which produces the same 69 as before. There may be ways to optimize this if one can make some assumptions about the input. ----------------------------------- XXX111 Wed Apr 07, 2010 5:45 pm Re: generating least positive integer (mod function) help ----------------------------------- What kind of solution are you looking for? Do you know how to solve it by hand? This is a textbook Maybe I'm just interpreting my own question wrong but wouldn't the answers for each question look something like this? dividing by 7 gives a remainder of 4= 11 (11/7=1 with remainder 4) dividing by 8 gives a remainder of 5= 13 (13/8=1 with remainder 5) dividing by 9 gives a remainder of 6=15 (15/9=1 with remainder 6) since all of the terms are as low as they can be while still providing the correct remainder amount, would these be correct? Is there any way to tell turing to find the lowest positive integer (my answers above) for each case or must it be manually entered? Thanks to everyone who's helped ----------------------------------- Brightguy Wed Apr 07, 2010 6:05 pm Re: generating least positive integer (mod function) help ----------------------------------- since all of the terms are as low as they can be while still providing the correct remainder amount, would these be correct? Those are not as small as possible: 4/7=0 with remainder 4, 5/8=0 with remainder 5, and 6/9=0 with remainder 9. But the question is to find a single x which satisfies: x=4 mod 7 x=5 mod 8 x=6 mod 9 The brute force method: check all x between 1 and 504=7*8*9 to find the one that works. It will be unique. Assuming the divisors are co-prime, couldn't one reduce to solve this? Yes, see the first link posted. But when the divisors are coprime you can just use CRT directly. ----------------------------------- XXX111 Wed Apr 07, 2010 7:15 pm Re: generating least positive integer (mod function) help ----------------------------------- thanks brightguy for the correction (didn't account for the zeros). With regards to the range of numbers, (1..504) is there any reason why you stopped at 504? Just trying to clarify your solution. EDIT: Never mind I can't believe I didn't see it the first time :shock: ----------------------------------- XXX111 Thu Apr 08, 2010 4:44 pm Re: generating least positive integer (mod function) help ----------------------------------- I almost have the code completed except for one small problem. The program now generates all the possible integers, but is there any way to stop after the first one (also the lowest) and have it display? Thanks [code] for i:1..504 if i mod 7=4 then put "The lowest positive integer that returns a remainder of 4 when divided by 7 is ", i end if end for [/code] ----------------------------------- apomb Thu Apr 08, 2010 4:53 pm Re: generating least positive integer (mod function) help ----------------------------------- This would require comparing the numbers... using a conditional inside a loop eg. [code]lowest = n for i: 1 .. (#of generated integers) if x < lowest then lowest = x end if end for[/code] ----------------------------------- XXX111 Thu Apr 08, 2010 4:59 pm Re: generating least positive integer (mod function) help ----------------------------------- This would require comparing the numbers... using a conditional inside a loop eg. apomb, I'm slightly confused about your code. Could you explain what the x variable would mean in this circumstance (also, what does lowest=n refer to?) thanks so much for your help ----------------------------------- TheGuardian001 Thu Apr 08, 2010 5:13 pm Re: generating least positive integer (mod function) help ----------------------------------- In this case, n is the initial lowest value, IE whatever number you want to check if the other numbers are below. So [code] lowest=n [/code] Is just giving an initial value for you to check other values against. n can be any number you want, so long as you realize that only numbers under the value of n will be seen as possible "low" numbers. x, on the other hand, represents whatever number you happen to be checking against the current lowest number. If it turns out to be lower than the current lowest number (if x < lowest then), then the program will reset the value of lowest to the value stored in x, meaning that x is now the new lowest number. ----------------------------------- apomb Thu Apr 08, 2010 5:18 pm RE:generating least positive integer (mod function) help ----------------------------------- Sorry, ya TheGuardian is right... Thank you TheGuardian for clearing that up for me. ----------------------------------- XXX111 Thu Apr 08, 2010 6:35 pm Re: generating least positive integer (mod function) help ----------------------------------- Thanks apomb and guardian for your excellent help ----------------------------------- Brightguy Thu Apr 08, 2010 7:31 pm Re: generating least positive integer (mod function) help ----------------------------------- I almost have the code completed except for one small problem. The program now generates all the possible integers, but is there any way to stop after the first one (also the lowest) and have it display? Well, actually, you shouldn't have to stop. Since 7,8,9 are coprime (they share no prime divisors) the solution between 1 and 504 will be unique. Remember you want an x that satisfies each constraint, not just one. ----------------------------------- Zren Thu Apr 08, 2010 8:24 pm Re: generating least positive integer (mod function) help ----------------------------------- Exit works for FOR loops just as good as normal loops. var n : int := 1 loop exit when %Insert conditions here% exit when n > maxint n += 1 end loop put n for i : 1 .. maxint if %Insert conditions here% then put i exit end if end for Oh and 504 isn't a proper exit strategy since we're not talking about x rem y = 0 (aka a factor). Your just lucky that the answer is slightly below this though. Then again there might be a theory that says every combination of below that sum will have each combination of remainders... @Brightguy: is that what your Chinese remainder theorem was pointing at? ----------------------------------- Brightguy Thu Apr 08, 2010 9:18 pm Re: generating least positive integer (mod function) help ----------------------------------- Then again there might be a theory that says every combination of below that sum will have each combination of remainders... I'm having difficulty parsing this, but yes, the Chinese remainder theorem is the essential theory. It saves you the trouble of checking every possible case by giving you a formula for the answer: 4*8*9*(1/(8*9) mod 7)+5*7*9*(1/(7*9) mod 8)+6*7*8*(1/(7*8) mod 9) mod 7*8*9 However, this requires computing modular inverses, which may not be part of the high school curiculum.