generating least positive integer (mod function) help

[XXX111]

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)

Turing:

% 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]

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]

apomb @ Wed Apr 07, 2010 1:14 pm wrote:

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]

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]

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 :

Turing:

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]

copthesaint @ Wed Apr 07, 2010 3:34 pm wrote:

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 :

Turing:

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]

What kind of solution are you looking for? Do you know how to solve it by hand? This is a textbook Chinese remainder theorem problem.

[jbking]

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]

Brightguy @ Wed Apr 07, 2010 4:41 pm wrote:

What kind of solution are you looking for? Do you know how to solve it by hand? This is a textbook Chinese remainder theorem problem.

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]

XXX111 @ Wed Apr 07, 2010 5:45 pm wrote:

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.

jbking @ Wed Apr 07, 2010 5:34 pm wrote:

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]

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

[XXX111]

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

[apomb]

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

[XXX111]

apomb @ Thu Apr 08, 2010 4:53 pm wrote:

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

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]

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

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.