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

Great riddle, very close to the Chinese remainder theorem,

Here's my brute force code for original riddle:


int remainder = 1;

            int answer = 0;

            string result = string.Empty;


            for (int number = 1; number <= 10000; number++)

            {

                for (int divisor = 2; divisor <= 10; divisor++)

                {

                    if (number % divisor == remainder)

                    {

                        if (remainder == 9)

                        {

                            answer = number;

                            result += string.Format("{0} ", answer);

                            break;

                        }

                        remainder++;

                    }

                }

                remainder = 1;

            }

Code for the second riddle:

string result2 = string.Empty;

            for (int number = 11; number <= 100000; number++)

            {

                for (int divisor = 2; divisor <= 10; divisor++)

                {

                    if (number % divisor == 1)

                    {

                        if (divisor == 10)

                        {

                            ++divisor;

                            if (number % divisor == 0)

                            {

                                result2 += string.Format("{0} ", number);

                                break;

                            }

                        }

                    }

                    else break;

                }

            }

Link to comment
Share on other sites

  • 0

There is a perfect solution.

Study the question inteligently. Assume that answer is X. If you add 1 to the answer X = Say X+1 this figur will be the exact divisible by each number from 1 to 10.

Therefore you need to find a LCM Lowest common Multiple of numbers 1 to 10. That is 2520.

Therefore Answer = 2519

Pramod Kasarekar

Edited by kasarekar
Link to comment
Share on other sites

  • 0

Ohw, I thought it was much easier.

Is this possible?

x² - x

Because:

2² - 2 = 4 - 2 = 2 --> 2/2 = 1

3² - 3 = 9 - 3 = 6 --> 6/3 = 2

4² - 4 = 16 - 4 = 12 --> 12/4 = 3

5² - 5 = 25 - 5 = 20 --> 20/5 = 4

6² - 6 = 36 - 6 = 30 --> 30/6 = 5

7² - 7 = 49 - 7 = 42 --> 42/7 = 6

8² - 8 = 64 - 8 = 56 --> 56/8 = 7

9² - 9 = 81 - 9 = 72 --> 72/9 = 8

10² - 10 = 100 - 10 = 90 --> 90/10 = 9

You see?

Or wasn't that the question?

Link to comment
Share on other sites

  • 0

no i think u have misunderstood the question... u answered it thinking that remainder means the quotient (the actual answer) we are asking for the remainder

for instance lets say u have 5/2 the answer would = to 2 and the remainder would be 1 (speaking in long division way and without continuing to turn it into a decimal)

so the question was what is the smallest number you can get that when u divide it by 2 your remainder is 1 and when u divide by 3 your remainder is 2 and so on and so on...

the answer is 2519

no one could find anyth smaller.(but clever job on your answer were that the objective :thumbsup:)hope that clears everything up :)

Edited by guppy
Link to comment
Share on other sites

  • 0

i have the best method

since all the remainders differ by 1 from the divisors so.

.. let us assume the number to by x

so adding one to x ie x+1 results another number of special property.

ie it is divisible by all other numbers 2,3,4,5,6,7,8,9,10.

to find the least number taking their LCM(lowest common multiple) results you 2520 yes

x+1=2520

so x is equal to 2519

i can assure you no other method is better

Edited by harikrishnan
Link to comment
Share on other sites

  • 0

i have the best method

since all the remainders differ by 1 from the divisors so.

.. let us assume the number to by x

so adding one to x ie x+1 results another number of special property.

ie it is divisible by all other numbers 2,3,4,5,6,7,8,9,10.

to find the least number taking their LCM(lowest common multiple) results you 2520 yes

x+1=2520

so x is equal to 2519

i can assure you no other method is better

Link to comment
Share on other sites

  • 0

2519

Lets say the number is X.

SInce, it is divisible by the numbers 2,3,...,10, if we add 1 to it.

SO, the number (X+1) is divisible by 2,3,4,...,10.

Now, we need to find the smallest number divisible by 2,3,4,...,10.

It should be the LCM(2,3,4,...,10) = 2520

So, X+1 = 2520

hence, X = 2519

Link to comment
Share on other sites

  • 0

if you check out each number out each number's posiblities and put it into a formula, you will obtain:

for the number 2: (x is any natural number, and it's diferent for every equation)

1+ 2x

Number 3

29+30x

Number 4

19+ 20x

Number 5

9+ 10x

Number 6

29 + 30x

Number 7

69 + 70x

Number 8

39 + 40x

Number 9

89+90x

Number 10

9 + 10X

So we need a number that is equivalent to all those equations. we have:

1+2X

29+30X

19+20X

9+10X

69+70X

39+40x

89+90X

So, we go and analyse the equations who give bigger products for the smallest number of X. those are: 89+90x and 69 + 70x. Replacing one of the x for another letter (y) we get:

89+90y = 69 + 70x <=> 20 = 70x - 90y

With that, we can now replace the "x" and the "y". for that formula to work, after some calculations, I notice that the x must go for 8 + 9z and the y must go 6+7z

So, starting for the 1st, if z = 0, x=8 and y=6. we replace them in the equation

89 + 90 x 6 = 629.

However, this number doesnt exist on the equation 39+40x, so its invalid.

You keep going,

z=1; x= 17 and y = 13, the final =1259, also doesnt exist on the equation 39+40x, so its invalid.

z=2, the final is 1889, also invalid.

Then, finally, z=43 y = 6+(7x3) =27........ 89 + 90x27 = 2519; which is valid for all the equations.

Link to comment
Share on other sites

  • 0

I actually believe I've found a smaller number, if negative numbers are allowed.

-1 !

-1 = -1 * 10 + 9

-1 = -1 * 9 + 8

-1 = -1 * 8 + 7

-1 = -1 * 7 + 6

-1 = -1 * 6 + 5

-1 = -1 * 5 + 4

-1 = -1 * 4 + 3

-1 = -1 * 3 + 2

-1 = -1 * 2 + 1

Link to comment
Share on other sites

  • 0

For those of those familiar with SQL, these types of problems are easily solved by perfoming a query on a Numbers (or Tally) table.

For example I have run the following selection on a numbers table (Numbers) containing 100,000,000 Rows (1,2,3....100,000,000) for the first 17 rows of the sequence (2 remainer 1 up to 18 remaining 17)

The answer is 12,252,239

SELECT

Min(Number)

FroM Numbers

WHERE

Number%2 = 1

AND Number%3 = 2

AND Number%4 = 3

AND Number%5 = 4

AND Number%6 = 5

AND Number%7 = 6

AND Number%8 = 7

AND Number%9 = 8

AND Number%10 =9

AND Number%11 = 10

AND Number%12 = 11

AND Number%13 = 12

AND Number%14 = 13

AND Number%15 = 14

AND Number%16 = 15

AND Number%17 = 16

AND Number%18 = 17

(To get the solutions to next rows in the sequence: 19 remainder 18, 20 remainder 19...) requires a bigger Number table

Edited by brifri238
Link to comment
Share on other sites

  • 0

FYI: If you extend the sequence from 2 remainder 1 .... to bigger numbers

possible solutions are (I am not absoutely sure they are the smallest number that works for each but these work!)

20 remainder 19 ......................232,792,559

22 remainder 21.......................232,792,559

23 remainder 22....................5,354,228,879

24 remainder 23....................5,354,228,879

30 remainder 29.............2,329,089,562,799

31 remainder 30...........72,201,776,446,799

36 remainder 35.........144,403,552,893,599

40 remainder 39......5,342,931,457,063,199

Edited by brifri238
Link to comment
Share on other sites

  • 0

This is a classic problem related to the Chinese Remainder Theorem.

The number you're describing leaves a remainder of 1 when divided by 2, 2 when divided by 3, 3 when divided by 4, and so on. In other words, the number is 1 unit more than a multiple of 2, 2 units more than a multiple of 3, and so on.

We can represent this system of equations:

n ≡ 1 (mod 2) n ≡ 2 (mod 3) n ≡ 3 (mod 4) ... n ≡ 9 (mod 10)

When considering the first two equations, we can search for a number that leaves a remainder of 1 when divided by 2 and 2 when divided by 3. This is 5. As we progress, we can build on this foundation.

However, to find the smallest number that satisfies these conditions, you can take the least common multiple (LCM) of numbers from 1 to 10 and subtract 1.

LCM(1,2,3,4,5,6,7,8,9,10) = 2520

So, the number = 2520 - 1 = 2519

Indeed, 2519 satisfies all the given conditions. When you divide 2519 by any number from 2 to 10, the remainder is always 1 less than the divisor.

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...