Jump to content
BrainDen.com - Brain Teasers
  • 1

Help! A remainder is chasing me


bonanova
 Share

Question

I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 2.

When I divide it by 4, the remainder is 3.

When I divide it by 5, the remainder is 4.

When I divide it by 6, the remainder is 5.

When I divide it by 7, the remainder is 6.

When I divide it by 8, the remainder is 7.

When I divide it by 9, the remainder is 8.

When I divide it by 10, the remainder is 9.

It's not a small number, but it's not really big, either.

When I looked for a smaller number with this property I couldn't find one.

Can you find it?

Link to comment
Share on other sites

Recommended Posts

  • 0
Nope ... 2521 is not divisible by 11.

New solution

The number is 25201.

My solution is that the number should be X=2520Y+1 and for some integer Y X should be divisible by 11. Is there some simpler method?

Edited by imran
Link to comment
Share on other sites

  • 0
New solution

The number is 25201.

My solution is that the number should be X=2520Y+1 and for some integer Y X should be divisible by 11. Is there some simpler method?

that is correct. good job ... I just managed to do it the brute forth method.

Link to comment
Share on other sites

  • 0

Here is my answer to the original puzzle.

My answer is -1. No matter what integer you divide it by (except of course zero) the remainder is one less than the divisor.

Link to comment
Share on other sites

  • 0

#include <cstdlib>

#include <iostream>

using namespace std;

bool mod(unsigned int);

int main() {

	unsigned int i;

	for( i = 0; !mod(i); ++i);cout << i << endl;

	system("PAUSE");

	return EXIT_SUCCESS;

}


bool mod(unsigned int i) {

	for( unsigned int j = 2; j <= 10; ++j)

		if( i % j != (j - 1) )

			return false;

	return true;

}

Or, as my dad put it, (5*7*8*9)-1=2519

Damn engineers.

Edited by OstermanA
Link to comment
Share on other sites

  • 0
If we're looking for n where n divided by x (x being each number 2-10) leaves a remainder of x-1, n+1 divided by each number 2-10 leaves no remainder. To find n+1, we must simply multiply all prime factors of 2-10, excluding any duplicates. This is equal to 2*2*2*3*3*5*7 = 2520, then just subtract one to get the answer of 2519.

thats right.

we are looking for (lcm of 1 to 10 )-1=2520-1=2519

Link to comment
Share on other sites

  • 0
Here is my answer to the original puzzle.
My answer is -1. No matter what integer you divide it by (except of course zero) the remainder is one less than the divisor.

Since 2519 + 2520n where n is any integer, has the correct remainders, your answer fits at least part of the OP.

But you overlook the part of not being able to find a smaller answer.

If negative numbers are included, a smaller answer can always be found: for example, -2521 is less than your answer.

Therefore, negative numbers do not answer the OP.

Link to comment
Share on other sites

  • 0
Another variation of the above problem is as follows:

I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 1.

When I divide it by 4, the remainder is 1.

When I divide it by 5, the remainder is 1.

When I divide it by 6, the remainder is 1.

When I divide it by 7, the remainder is 1.

When I divide it by 8, the remainder is 1.

When I divide it by 9, the remainder is 1.

When I divide it by 10, the remainder is 1.

But when I divide it by 11, the remainder is 0 (just to make the procedure a little bit different).

Can you find it?

Let X be the answer to the puzzle where X = Y + 1, Y is a multiple of 2 to 10

=> The LCM of 2-10 is 2520.

=> X = 2520Y + 1.

However, X mod 11=0

=> 2520 mod 11=1

=> Thus (2520 * 10) mod 11 = 10

=> Thus [(2520 * 10) + 1] mod 11 = 10 + 1 = 11 = 0

Therefore X = 25201

Link to comment
Share on other sites

  • 0
In the spirit of ATL, I present to you my method, in C#, for calculating the answer by brute force, without taking into account LCM's. I'm curious how much smaller this could be done.

int GetNumber() {

int i=1, n=1; bool r=false;

for (;!r;){if(i%n==(n-1)){n=n%11+1;r=n==11;}else{i++;n=1;}}return i;}

Using a while statement instead might save a few spaces, but the biggest space saver I would be changing n=n%11+1 to n++. Both increment n by 1 but n++ is much more logical. I don't really understand why you wouldn't use it. I'm sure there are more ways to reduce the code as well.

Link to comment
Share on other sites

  • 0

Since negative numbers are not excluded by the problem as posed, the answer is negative infinity - since any other solution has another number smaller than it. This doesn't fit well with the statement 'it is not a small number', but that is a subjective description.

2519

-1

-2521

-5041

-7561

-10081

-12601

-15121

-17641

etc.

I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 2.

When I divide it by 4, the remainder is 3.

When I divide it by 5, the remainder is 4.

When I divide it by 6, the remainder is 5.

When I divide it by 7, the remainder is 6.

When I divide it by 8, the remainder is 7.

When I divide it by 9, the remainder is 8.

When I divide it by 10, the remainder is 9.

It's not a small number, but it's not really big, either.

When I looked for a smaller number with this property I couldn't find one.

Can you find it?

Edited by xucam
Link to comment
Share on other sites

  • 0
I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 2.

When I divide it by 4, the remainder is 3.

When I divide it by 5, the remainder is 4.

When I divide it by 6, the remainder is 5.

When I divide it by 7, the remainder is 6.

When I divide it by 8, the remainder is 7.

When I divide it by 9, the remainder is 8.

When I divide it by 10, the remainder is 9.

It's not a small number, but it's not really big, either.

When I looked for a smaller number with this property I couldn't find one.

Can you find it?

The method which I think most of the students can understand is to use the

LCM? Lowest Common Multiplier?

Since the number is always remain (n-1) when devided by n ( n = 2 to 10), then it will be just the common multiplier of 2, 3, 4....to 9 and then -1.

LCM of (2, 3, 4,......,8,9)= 2520

2520 - 1 = 2519 !

then the next one will be 2(2520)-1 = 5039; 3(2520)-1 = 7559, etc....

Link to comment
Share on other sites

  • 0

Hi. numbers that fit that condition are:

2519, 5039, 7559, 10079, 12599, 15119, 17639, 20159, 22679, 25199, 27719, 30239, 32759, 35279, 37799, 40319, 42839, 45359, 47879, 50399, 52919, 55439, 57959, 60479, 62999, 65519, 68039, 70559, 73079, 75599, 78119, 80639, 83159, 85679, 88199, 90719, 93239, 95759, 98279, 100799, 103319, 105839, 108359, 110879, 113399, 115919, 118439, 120959, 123479, 125999, 128519, 131039, 133559, 136079, 138599, 141119, 143639, 146159, 148679, 151199, 153719, 156239, 158759, 161279, 163799, 166319, 168839, 171359, 173879, 176399, 178919, 181439, 183959, 186479, 188999, 191519, 194039, 196559, 199079, 201599, 204119, 206639, 209159, 211679, 214199, 216719, 219239, 221759, 224279, 226799, 229319, 231839, 234359, 236879, 239399, 241919, 244439, 246959, 249479, 251999, 254519, 257039, 259559, 262079, 264599, 267119, 269639, 272159, 274679, 277199, 279719, 282239, 284759, 287279, 289799, 292319, 294839, 297359, 299879, 302399, 304919, 307439, 309959, 312479, 314999, 317519, 320039, 322559, 325079, 327599, 330119, 332639, 335159, 337679, 340199, 342719, 345239, 347759, 350279, 352799, 355319, 357839, 360359, 362879, 365399, 367919, 370439, 372959, 375479, 377999, 380519, 383039, 385559, 388079, 390599, 393119, 395639, 398159, 400679, 403199, 405719, 408239, 410759, 413279, 415799, 418319, 420839, 423359, 425879, 428399, 430919, 433439, 435959, 438479, 440999, 443519, 446039, 448559, 451079, 453599, 456119, 458639, 461159, 463679, 466199, 468719, 471239, 473759, 476279, 478799, 481319, 483839, 486359, 488879, 491399, 493919, 496439, 498959, 501479, 503999, 506519, 509039, 511559, 514079, 516599, 519119, 521639, 524159, 526679, 529199, 531719, 534239, 536759, 539279, 541799, 544319, 546839, 549359, 551879, 554399, 556919, 559439, 561959, 564479, 566999, 569519, 572039, 574559, 577079, 579599, 582119, 584639, 587159, 589679...

you can check it, you can't find a number minor than 2519, you add 2520 each time and each number will fit the same condition!

Edited by clao784
Link to comment
Share on other sites

  • 0

I wrote an excel spreadsheet that calculated it for me. The number you are referring to is 2519 but here are a few larger numbers that work as well....

5039, 7559, 10079, 12599, 15119, 17639, 20159

I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 2.

When I divide it by 4, the remainder is 3.

When I divide it by 5, the remainder is 4.

When I divide it by 6, the remainder is 5.

When I divide it by 7, the remainder is 6.

When I divide it by 8, the remainder is 7.

When I divide it by 9, the remainder is 8.

When I divide it by 10, the remainder is 9.

It's not a small number, but it's not really big, either.

When I looked for a smaller number with this property I couldn't find one.

Can you find it?

Link to comment
Share on other sites

  • 0
I think you should include dividing 11 to get a remainder of 10 and dividing 12 to get a remainder of 11

As has been said thousands of times on this post as if it was new:

Take the LCM of 1-12,by multiplying 2520 by 11 to get 27720

Minus 1 to add the remainder

end by getting:

27719

Link to comment
Share on other sites

  • 0

Another variation of the above problem is as follows:

I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 1.

When I divide it by 4, the remainder is 1.

When I divide it by 5, the remainder is 1.

When I divide it by 6, the remainder is 1.

When I divide it by 7, the remainder is 1.

When I divide it by 8, the remainder is 1.

When I divide it by 9, the remainder is 1.

When I divide it by 10, the remainder is 1.

But when I divide it by 11, the remainder is 0 (just to make the procedure a little bit different).

Can you find it?

Any number of the form

2X3X4X5X6X7X8X9XN -1

where N is any integer will satisfy the first 9 conditions, but since any number divided by 8 giving remainder 1 will also give the remainder 1 when divided by 2 or 4, and any number divided by 9, giving remainder 1 will also yield remainder 1 when divided by 3 therefore the number could be reduced to :

8X9X5X7n - 1 = 2520n -1

to be divisible by 11 we rerite it as:

2520n - 1 = 2530n - (10n+1)

2530n being a multiple of 11, we only have to fine n to make 10n +1 a multiple of 11

it's easy to see

n = 1 + 11m

Link to comment
Share on other sites

  • 0

That's it.

Here's my method: [care to share yours?]

<div style="margin:20px; margin-top:5px">

<div class="smallfont" style="margin-bottom:2px">Spoiler for solution: <input type="button" value="Show" style="width:45px;font-size:10px;margin:0px;padding:0px;" onClick="if (this.parentNode.parentNode.getElementsByTagName('div')[1].getElementsByTagName('div')[0].style.display != '') { this.parentNode.parentNode.getElementsByTagName('div')[1].getElementsByTagName('div')[0].style.display = ''; this.innerText = ''; this.value = 'Hide'; } else { this.parentNode.parentNode.getElementsByTagName('div')[1].getElementsByTagName('div')[0].style.display = 'none'; this.innerText = ''; this.value = 'Show'; }">

</div><div class="alt2" style="margin: 0px; padding: 6px; border: 1px inset;"><div style="display: none;">The number has to end in 9.

Looked brute force for small numbers.

59 and 119 were promising, but no cigar.

Then looked for agreement among

39 + multiples of 40,

69 + multiples of 70 and

89 + multiples of 90

Smallest one was 2519.

Still think of this as kind of brute force.

Maybe there is no elegant solution.</div></div></div>

This problem may be solved as a simple variant of the Chinese Remainder Theorem, BN. If you do not have a book on Elementary Number Theory to hand, just Google it. The problem was first posed by the great physicist Dirac (in the 1930's I seem to remember, at a Mathematical symposium.)

Link to comment
Share on other sites

  • 0

Let the number is X.

Now consider the number X+1.

As the remainder for X/2 is 1, it follows X+1 is completely divisible by 2.

As the remainder for X/3 is 2, it follows X+1 is completely divisible by 3. and so on...

So X+1 is completely divisible by 2,3...10.

and the lowest such number has to be LCM of 2,3,...10 = 2520.

So X = 2520 - 1 = 2519.

Other number would be 2520n - 1, where n = 1,2,3...

Edited by azjain
Link to comment
Share on other sites

  • 0

Wow, I haven't posted on these forums in a long time...

Heh, I was about to go all number theory and brute force the answer, but then I saw the smart solutions people were putting up, and went... 'wow.'

I'll answer the one that was answered less often? (But still answered?)

Another variation of the above problem is as follows:

I just found a number with an interesting property:

When I divide it by 2, the remainder is 1.

When I divide it by 3, the remainder is 1.

When I divide it by 4, the remainder is 1.

When I divide it by 5, the remainder is 1.

When I divide it by 6, the remainder is 1.

When I divide it by 7, the remainder is 1.

When I divide it by 8, the remainder is 1.

When I divide it by 9, the remainder is 1.

When I divide it by 10, the remainder is 1.

But when I divide it by 11, the remainder is 0 (just to make the procedure a little bit different).

Can you find it?

Like some people have said, the solution is probably only really able to found through brute force... kind of.

Use the LCM method, and you find that the number x-1 is divisible by 2, 3, 4, 5, 6, 7, 8, 9, and 10, where x will be the number that fits these conditions.

x-1 = some multiple of 2520. Divide 2520 by 11, and you get a remainder of 1. You figure out, you need to multiply the number by ten, because you will be adding one, making the remainder 11, or 0.

Hence, 25201.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...