h a l f b a k e r yWe got your practicality ... right here.
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
What, no Game: Puzzle category?
The name of this puzzle derives from the word "modulus", which in mathematics is equivalent to the part of a divided number that is left over after doing division. For example, 10/3 has a whole-number quotient of 3 and a left-over part (also called the 'remainder')
of 1. When talking about the modulus one ignores the quotient entirely, and uses the word "mod" as the mathematical operator (or in some computer programming languages, the symbol "%"). So, 10 mod 3 = 1 (or 10 % 3 = 1). It is perfectly acceptable for a modulus to be zero, so obviously 9 mod 3 = 0.
Creating a Madulus puzzle is pretty simple. First, pick a range of numbers, such as 1000 to 10000. Note that there are 9001 numbers in that range (including the 1000 and the 10000), and note that half of that is 4501 (round up). Next, DON'T randomly pick some number in that range, which I will call "N" here. Then, randomly select some smallish numbers to be used as divisors, each usually less than 100, and all different. The quantity of these numbers will depend on how small they are. The product of these numbers, all multiplied together, must exceed half the range (must be more than 4501 in this case), but should not exceed the whole range (9001 in this case). For this example I'll choose 3, 8,17, and 22; their product is 8976, which fits the criteria just fine. Finally, make up some moduli, in a manner like this:
N mod 3 is 1
N mod 8 is 5
N mod 17 is 12
N mod 22 is 7
As long as the chosen moduli follow the mathematical rule that they be smaller than the divisors (and per an anno by [pertinax], the divisors should not be able to wholly divide each other), then it doesn't matter what whole-number values are chosen as moduli. At this point this Madulus puzzle is ready. The goal:
What is the value of N, such that it lies within the specified range (guaranteed in this case where the product of the divisors 3*8*17*22=8976)? Note that by ensuring the product is greater than half the range, we are USUALLY guaranteed the puzzle has only one answer, although sometimes there might be two answers.
This is a Half-Baked Idea because either (A) someone seeing it will think it is too hard, and not bother, or (B) someone seeing it will have an Insight regarding how to solve it, and then think it is too simple, and so not bother. Oh, well.... I should mention that as described here, this is a "solitare" puzzle. However a slight modification can allow two people to challenge each other. One person picks the range AND N and the divisors, and computes the moduli from those divisors. The other person is only given the range and the divisors and the moduli, and of course still has to find N. Note that while the first person doesn't have to choose divisors that cannot divide each other, it is necessary to choose enough divisors to be sure N is the only possible answer in the specified range.
I'll come back later and post the simple solving technique, and the answer to this particular puzzle. If someone else doesn't do it first.
:)
All your remainder are belong to this...
http://en.wikipedia...e_remainder_theorem
In essence this will give you all N, then exclude those out of the range. Viola! [4whom, Jan 19 2009]
Madulus on line
http://www.nemitz.net/games
One among several pastimes listed. Enjoy! [Vernon, Mar 16 2016, last modified Mar 31 2016]
Please log in.
If you're not logged in,
you can see what this page
looks like, but you will
not be able to add anything.
Annotation:
|
| |
OK - I'm not entirely sure I get this. Can you post an
example (I mean, set the puzzle as if it were for real)? |
|
| |
I have a feeling this game would be too easy for ubernerds and too hard for everyone else. |
|
| |
Suggested brute-force algorithm: |
|
| |
a) Pick the largest of the four small numbers (in this case, 22).
b) Find the lowest coefficient of 22 yielding a product which, after the modulus (7) is added, gives a figure within the target range. (I.e., do integer-division of (1000-7) by 22). Call this coefficient C0.
c) As a safety measure, also find the highest such coefficient. Call this coefficient Cmax.
d) For each value of integer C between C0 and Cmax, test 22C+7 against the other small numbers as a candidate for N.
e) If no value of C from C0 to Cmax satisfies the test, then I've stuffed up somewhere. |
|
| |
When *setting* such a puzzle, I suppose you'd have to careful, when picking the small numbers, that none of them was a multiple of any other - or, if so, that those two had consistent moduli. For example, "N mod 8 = 4 and N mod 2 = 1" cannot be true for any N, can it? |
|
| |
I wonder whether there are any other constraints on these apparently random small numbers? |
|
| |
[MaxwellBuchanan], I did describe a real-enough particular puzzle example. At the moment of writing this anno, I don't know what the value of "N" is (the intention here is to discover it by describing the discovery procedure), but in creating this Idea I did enough experimentation to be confident that there is no huge contradiction in its specifications, and that "N" will exist as described. |
|
| |
In the main description I merely indicated that much is optional, when creating a specific puzzle (the range of numbers is optional; the choice of small divisors is optional, and their quantity can vary; the choice of moduli is optional. [pertinax], yes, it is best to pick divisors that don't divide each other exactly, and I should have mentioned that in the main text. They can have some common factors, though (like 8 and 22 in this example are both divisible by 2). |
|
| |
[Spacecoyote], I think I said something like what you wrote, in the main text. |
|
| |
[po] and [UnaBubba], N will be a whole number, always. Also, for [rcarty] too, the puzzle stated that N must be between 1000 and 10000 ("What is the value of N, such that it lies within the specified range"?). |
|
| |
[pertinax], you are near the right track, but not on it. Yes, start with the largest specified divisor, 22 in this case. Next, add to it the specified modulus for it (7), which gives us 29. Take a moment to think about that: 29 mod 22 = 7. Now add another 22, to get 51: 51 mod 22 = 7. So, we can quickly conclude that inside the series of numbers 7+22, +22, +22, +22, ... (29, 51, 73, 95, ...), every one of them is a value X such that X mod 22 = 7. In this particular Madulus puzzle, the desired number N must be a member of this series. |
|
| |
Similar series of numbers can be generated such that every "X mod 17 = 12", or every "X mod 8 = 5", or every "X mod 3 = 1". The desired number N must be a member of each of those series. If we could draw these series as lines on a graph, they would all intersect at N. However, that can require a rather large graph, and is rather easier said than actually done. |
|
| |
There is additional trick that can help to quickly discover N. I'll describe it later in another annotation here. |
|
| |
Ah, OK, so the puzzle is to find N such that N mod 3=1, N
mod 8=5 etc? Hang on... |
|
| |
[MaxwellBuchanan], yes, 1525 appears to be a valid answer. The easy way to check it is, for each modulus (such as 7), to subtract it and then divide (by 22 in this example). If whole-number quotients are found for every specified modulus and divisor (which I did find), then the number is verified. |
|
| |
I see that 1525 is at first glance the only number in the range from 1000 to 10000, that fits the specified criteria. The next number that meets only the modulus requirements is, logically, as will be explained below, 1525 + 8976 = 10501. |
|
| |
Anyway, the method of finding that first N of 1525 fairly easily still needs to be described. Basically, the trick is to take advantage of the "cyclic" nature of moduli. As I mentioned in my previous anno, starting at 29, it and every 22nd number after it will be an X such that X mod 22 = 7. So it is a simple cycle of 22. When we combine the cycles we don't need to examine a lot of numbers to find N. |
|
| |
More specifically, the next-largest cycle in this particular puzzle is 17. Every 17th value will be an X that has any modulus we want to work with, in this case 12. I generalize that as follows: FOR ANY SIMPLE SERIES, every 17th value will be an X that will have a modulus of 12. The MOST simple series is 0 +1, +1, +1, +1, etc. But the above rule will also apply to the series 7 +22, +22, +22, etc. |
|
| |
It is a "lucky" thing, in this particular puzzle, that 29 mod 22 =7 and 29 mod 17 = 12 (I sure wasn't paying attention when I was picking arbitrary numbers in the main text). It means we don't have to hunt through seventeen of the numbers in the cycle-of-22 (that is, 29, 51, 73, 95, ...) to find the one which is X mod 17 = 12, because it just happened to be the first one. |
|
| |
Next, note that 22 * 17 = 374. Think of this as 17 cycles of the cycle-of-22. It means that 29 + 374 (or 403) is the NEXT number X such that X mod 22 = 7, and X mod 17 = 12. So now we have a new and nice large cycle-of-374, which is 29, +374, +374, +374, ... (or 29, 403, 777, 1151, ...). |
|
| |
In THAT cycle-of-374 we now want an X such that X mod 8 = 5. At most we only need to examine 8 numbers in the sequence to find it. So we start with the first member of the series: 29 mod 8 = 5 --WHAT??? How lucky can we get??? This won't do at all; I'm going to have to make up another Madulus puzzle, just to be able to properly describe the rest of the solving-trick! (Later!) |
|
| |
Anyway, now we multiply 8 * 374 =2992 to get the size of the next cycle we want to work with. Our last and smallest divisor is 3, so at most we only need to examine three members of the sequence 29, +2992, +2992, ... (29, 3021, 6013) to find the X such that X mod 3 = 1. The number 6013 fits the bill, and therefore 6013 qualifies as N, the answer to this particular Madulus puzzle (you can check it as described in the first part of this anno, to see that it does qualify). |
|
| |
Now, why did we find 6013 and not 1525? The answer relates to the fact that our specified divisors 8 and 22 have the common factor of 2. It means we could have multiplied 4 * 374 = 1496 instead of 8 * 374 = 2992. Then the sequence to examine per our divisor of 3 would have been 29, +1496, +1496, ... (that is, 29, 1525, 3021, ...), and 1525 would indeed have been found as our desired N. |
|
| |
Obviously the preceding procedure can be used regardless of how many divisors are specified. The cycles simply get bigger. A cycle-of-8976 results from multiplying 3 * 2992, and leads to the "at first glance" statement in the second paragraph of this anno. We now know, course, that a cycle-of-4488 (half of 8976, because of the common factor) would also work in this case. |
|
| |
Huh? I thought 29 mod 22 = 7 |
|
| |
[pertinax], thanks for catching that. Having too many different numbers on the brain at 4:30am can cause wrong ones to show up in almost any text. Fixed. |
|
| |
[up_on_cloud_nine], if you have an even simpler trick, feel free to post it. |
|
| |
[up_on_cloud_nine], thank you. I suppose the definition of "simple" should indicate whether something is simple with respect to grunt-work or with respect to brain-work. The method I described certainly can reduce the grunt-work. I tried to explain it so it was easy to understand. To the extent I succeeded in making it understandable, that is the extent to which the reader might call that method "simple". |
|
| |
I did say there was an additional trick that can help, when the first number one starts to work with (29 in the above example) doesn't happen to already be a member of 3 different cycles that one wants to examine. Again, it is more brainwork than gruntwork, so "simple" might be a matter of opinion. Only one way to find out, though.... |
|
| |
Here is a new Madulus puzzle:
Find N in this Range: 5,000 to 50,000
where N mod 41 = 25
and N mod 37 = 18
and N mod 27 = 23 |
|
| |
I haven't sought the solution for it yet, but did make sure there were no common factors, or that the "luckiness" of the previous puzzle didn't happen here. It is possible there are there are two answers, since 41*37*27=40959, and the range stretches across 45001 numbers. Note that if the range was shrunk to, say, 10,000-50,000 (40,001 numbers), it would be possible for N not to exist within the range at all. Better to risk two answers than none. |
|
| |
[miasere], I see we posted at about the same time. You did not specify a range, so presumably you just want the first N that fits the modulus specifications? If so, then N=6793 |
|
| |
[miasere], that's interesting. I just used a fairly ordinary calculator (it has 3 memory registers, though) to find yours. Let me see.... |
|
| |
Looks like your spreadsheet has a problem. Not enough rows, maybe? |
|
| |
[4whom], nice link, but the method for finding all those N appears to be obscured by abstruse terminology. Also, I was already aware that when you take all the specified divisors and multiply them together, the result is a difference between successive values of N. The main text here, of course, does not mention the word "coprime", and actually I had deliberately left it out; I was somewhat short on time and didn't want to take the time to write an explanation for it. But the effect of using non-coprime divisors was already demonstrated here, and I quote: |
|
| |
"A cycle-of-8976 results from multiplying 3 * 2992, and leads to the "at first glance" statement in the second paragraph of this anno. We now know, course, that a cycle-of-4488 (half of 8976, because of the common factor) would also work in this case." |
|
| |
Excel's mod function is not to be relied upon. |
|
| |
Time to get to that last solving trick. We already know we can start with the series 25+41, +41, +41, ..., or 66, 107, 148, ..., and we need to find some member X in that series such that X mod 37 = 18. We only need to compute the modulus for the first two numbers: 66 mod 37 = 29, and 107 mod 37 = 33. |
|
| |
The trick starts by noting that 33 - 29 = 4. Because we are dealing with a simple series (66, 107, 148, ...) we can be sure that the moduli will form a series, too. This particular modulus series is 29, +4, +4, +4, ..., or 29, 33, 37, 41, ... Of course, once we reach or pass 37, the "base" of these modulus computations, we should in theory subtract 37 and proceed from there: 29, 33, 0, 4, 8, 12, ... |
|
| |
We could keep adding 4 and subtracting 37, writing the results down with pencil and paper, until the number 18, the desired modulus, appears. Sometimes it might be simplest to do exactly that, especially if the desired modulus shows up after only a few additions. Let's pretend for the moment that the desired modulus was 8 instead of 18. We can COUNT 5 numbers in the series 29, 33, 0, 4, and 8. Take that 5 and go back to the cycle-of-41 in the first paragraph here. Compute 25 + (5 * 41) = 230. If 8 had been the desired modulus, then THIS 230 is our desired X, such that X mod 37 = 8 (and also X mod 41 = 25). |
|
| |
However, in this particular case the desired modulus is actualy 18, and that list 29,33, 0, 4, ..., will have to be extended quite a bit before we get to 18. So let us approach that answer with the last part of this trick. We are adding +4, +4, +4, exactly as if we had been adding 41 in the first paragraph here. We want the series 29, +4, +4, +4, ... to intersect the series 18+37, +37, +37, ... almost exactly like we are seeking the number where the series 18, +37, +37, +37, ... intersects the series 25+41, +41, +41, .... The first big difference is that we started at 29 and not with a modulus of 4. What IS 29 mod 4? The answer is 1, so instead of writing 29, +4, +4, +4, ..., we could write 1, +4, +4, +4, ..., keeping in mind that it takes 6 steps to get through the ignorable numbers smaller than 29, which is the "official" starting point for this series. |
|
| |
The second big difference is that because we are working with 4 instead of 37, we can very quickly find an appropriate number. That is, in the series 18+37, +37, +37, ..., or 55, 92, 129, ... --we only need to at-most look at 4 numbers in that series to find an X such that X mod 4 = 1. It happens to be 129. So divide by 4 to get 32 (and ignore the fraction), and then subtract 6 because we need to count from 29 instead of 1 (as described at end of last paragraph), and so 32 - 6 = 26. Take that 26 over to the cycle-of-41 in the first paragraph here, and compute 25 + (26 * 41) = 1091, the desired X such that X mod 37 = 18 and X mod 41 = 25. |
|
| |
So now we have a series that starts at 1091 and increments by (41 * 37) or 1517:
1091, +1517, +1517, +1517, ..., or 1091, 2608, 4125, 5642, ... --in THIS series we want to find an X such that X mod 27 = 23. When we find it, we will also have found N, the answer to this Madulus puzzle. |
|
| |
Therefore we proceed as already described:
1091 mod 27 = 11
2608 mod 27 = 16
We observe that 16 - 11 = 5
We have a series 11, +5, +5, +5, ..., or 11, 16, 21, 26, ....
We observe that the desired modulus of 23 is not one of the "early" members of that series, so....
We note 11 mod 5 = 1, and the series 1+5, +5, has only 1 member smaller than 11.
We want to find the number in the series 23+27, +27, +27, +27 ... or 50, 77, 104, 131..., where X mod 5 = 1
We discover it to be 131.
The integer part of the quotient of 131/5 is 26.
We subtract 1 from 26 to make sure our cycle-of-5 series starts counting from 11, so 26 - 1 = 25.
We take that 25 to our cycle-of-1517 and compute 1091 + (25 * 1517) = 39016. |
|
| |
Whoa! That is NOT the desired N! As indicated in a previous annotation, the N for this Madulus puzzle is 37499; we are "off" by an excess of 1517. So why was 25 the wrong multiplier (the correct one is 24)? {NOTE: this discrepancy is deliberate, so that the reader can be informed about something to watch out for.} |
|
| |
The answer involves a subtle difference between the first using of this trick (for 37), and the second (for 27). For 37, the series to intersect was 25+41, +41, +41, ..., and for 27, the series to intersect was 1091, +1517, +1517, +1517, .... The difference is that 25 was NOT the first number analyzed in terms of X mod 37 (it was 66), while 1091 WAS the first number analyzed in terms of X mod 27. But 1091 is not a reasonable result of the computation that multiplied 1517, while 66 is indeed a quite reasonable result of the computation that multiplied 41. (By "reasonable" I mean that we would have had to multiply 1517 by zero, in the computation, to get 1091, but in that case 1091 mod 27 would have yielded the desired modulus, and we would not have bothered to do 2608 mod 27, much less do the rest of the above steps.) |
|
| |
Therefore, because we started with 1091 mod 27, we need to subtract 1 from the multiplier of 25, thus obtaining the correct multiplier of 24, which leads us to the correct N of 37499. |
|
| |