You are invited to Log in or Register a free Frihost Account!

# Big number

saberlivre
A number is written by placing the numbers 19 through 73 im sequence. How many times can this number be divided by 3 withot rest?
SonLight
I'm not sure I quite understand the question. I'm hoping it's a real problem with a definite answer, and some interesting techniques that can be used to simplify finding the answer.

I think you mean to write out the number 192021 ... 717273, then determine how many times it can be divided by 3 without remainder. For example, if the number is a multiple of 3 then it can be divided at least once; if it is also a multiple of 9 then it can be divided at least twice, etc. for 27, 81, 243, ... . If I have misstated the problem, then please clarify it for us.

My initial thought is to attack the problem with the old "casting out nines" method -- if a number is a multiple of 3 or 9 then the sum of its digits are also a multiple of 3 or 9. It is not clear whether the idea can be generalized in any way. Summing the digits should allow me to determine that the answer is 0 (not a multiple of 3 at all), 1 (multiple of 3 but not of 9), or at least two (multiple of nine, unknown whether it is a multiple of 27). I am assuming it will be a multiple of 9 and that therefore the problem might be interesting.
IceCreamTruck
Kinda needing the answer to those questions as well, but I'm posting so I get the updates in email. This seems to be a fun question, but I'm not sure the purpose yet.

 Code: 19202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273

Too much?
kelseymh
 saberlivre wrote: A number is written by placing the numbers 19 through 73 im sequence. How many times can this number be divided by 3 withot rest?

None. Division by three will have a remainder of 1. SonLight had the correct approach: sum of digits is (1+9) + (45*5 + 20*10) + (28+6) = 469 => 19 => 10 => 1. I leave it as an exercise for the other readers as to why I wrote the computation as I did.
Afaceinthematrix
People are correct with none. I number is divisible by 3 if you can add up the digits that make it and that number is divisible by 3. If 6 divides it, then it will also be even. If nine divides it, then the digits will add up to a number that nine divides. Etc. The numbers 19 to 73 add up to 2530 which has none of those properties... Of course I cheated on this because I am sure there's some trick that you can use without having to actually add those numbers up... But instead of figuring out the trick (like maybe looking at how many numbers in each interval range like 20-29, 30-39, 40-49, etc. are divisible by three... that is actually a pretty easy way to solve this problem), I just used a computer to see what it added up to because it took me two and a half seconds to write the program (and I already had my compiler open anyways):

 Code: #include using namespace std; int main() {     int k = 19;     int total = 0;     while (k < 74){     total += k;     k++;     }     cout << total; }
kitsrock
well, another method would be to use the sigma notation on n+1 from 18 to 72 and see if that is divisible by 3. (if i remember correctly, adding the digits to see if it's divisible by 3 does not have to be of individual digits)

using the sigma notation I get 8574539875 which the digits keep adding up to 7 which would mean a remainder of 1.

if this is for a class, you have several methods to choose from to fit the teacher/professor's wanted/expected answer.
Afaceinthematrix
 kitsrock wrote: well, another method would be to use the sigma notation on n+1 from 18 to 72 and see if that is divisible by 3. (if i remember correctly, adding the digits to see if it's divisible by 3 does not have to be of individual digits) using the sigma notation I get 8574539875 which the digits keep adding up to 7 which would mean a remainder of 1. if this is for a class, you have several methods to choose from to fit the teacher/professor's wanted/expected answer.

I was thinking about suggesting that but you still have to do a little calculations... You would have to do (73*74)/2 - (18*19)/2 = 2530... But that is still a calculation that most people wouldn't do without a pen a paper... And I am sure that if you thought about it, you could find a nice elegant way to prove this without having to do a bunch of numerical effort...
SonLight
OK, according to my first post, I consider the problem "uninteresting" because it can be solved with one series of adding up digits. Since that was an unexpected result, that makes it very interesting indeed.

kelseymh's post seems to be similar to the way I would have proceeded to solve it, except that I thought I would need another good trick because I was expecting two or more factors of 3. All that remains is to find the most elegant way to organize the attack, either explaining kelseymh's factoring or improving upon it.

For a related problem with one foot in this forum and one foot in the philosophy forum, what it the smallest integer that is not interesting? Please justify your result.
kaankaan
 Quote: 19202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273

not to much
SonLight
kaankaan wrote:
 Quote: 19202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273

not to much

ok, that number (call it N) looks like it might be uninteresting. I'm not sure how you arrive at it, so I can't be sure that the method makes it really interesting. However, I am willing to accept as a working hypothesis that it may indeed be uninteresting.

Now for the hard part:

Why is N-1 an interesting number? If it isn't, then N is not the smallest uninteresting number. Of course if N-1 is interesting, there could still be some smaller number which is not ...
IceCreamTruck
SonLight wrote:
kaankaan wrote:
 Quote: 19202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273

not to much

ok, that number (call it N) looks like it might be uninteresting. I'm not sure how you arrive at it, so I can't be sure that the method makes it really interesting. However, I am willing to accept as a working hypothesis that it may indeed be uninteresting.

Now for the hard part:

Why is N-1 an interesting number? If it isn't, then N is not the smallest uninteresting number. Of course if N-1 is interesting, there could still be some smaller number which is not ...

Lmao.... I think you're really on to something here! Do the math!
inuyasha
Afaceinthematrix wrote:
People are correct with none. I number is divisible by 3 if you can add up the digits that make it and that number is divisible by 3. If 6 divides it, then it will also be even. If nine divides it, then the digits will add up to a number that nine divides. Etc. The numbers 19 to 73 add up to 2530 which has none of those properties... Of course I cheated on this because I am sure there's some trick that you can use without having to actually add those numbers up... But instead of figuring out the trick (like maybe looking at how many numbers in each interval range like 20-29, 30-39, 40-49, etc. are divisible by three... that is actually a pretty easy way to solve this problem), I just used a computer to see what it added up to because it took me two and a half seconds to write the program (and I already had my compiler open anyways):

 Code: #include using namespace std; int main() {     int k = 19;     int total = 0;     while (k < 74){     total += k;     k++;     }     cout << total; }

I fear that you misunderstood. The topic starter seemed to mean... Numbers are concated as strings. Not added up.
infinisa
kelseymh wrote:
 saberlivre wrote: A number is written by placing the numbers 19 through 73 im sequence. How many times can this number be divided by 3 withot rest?

None. Division by three will have a remainder of 1. SonLight had the correct approach: sum of digits is (1+9) + (45*5 + 20*10) + (28+6) = 469 => 19 => 10 => 1. I leave it as an exercise for the other readers as to why I wrote the computation as I did.

Hi kelseymh

The numbers from 19 to 73 can be broken up into 3 groups like this:

A) 19
B) 20-29, 30-39, 40-49, 50-59, 60-69
C) 70-73

We now add up the digits in each group:

In group (A) we have (1+9)

In group (C) we have 4 numbers (70, 71, 72, 73) containing 4 7's (tens) and 1+2+3 (units), giving (28+6)

In group (B) we have 5 groups of 10 numbers. In each group, the unit digit runs from 0 to 9, which adds up to 45 (using the formula 1+2+...+n = n(n+1)/2). Since there are 5 groups, we have 45*5.
The tens digits in each group are 2, 3, 4, 5 and 6, which add up to 20. Since each ocurrs 10 times in its group this gives 20*10. So for group (B) we get a total of 45*5 + 20*10.

Adding the 3 groups together, we get (1+9) + (45*5 + 20*10) + (28+6) = 469.

Adding the digits (which keeps the same remainder on dividing by 3 or 9) gives 19; repeating this operation twice more gives 10 then 1.

So the original number has a remainder of 1 ehen divided by 3 (or 9) and is not divisible by 3.
kelseymh
infinisa wrote:
kelseymh wrote:
 saberlivre wrote: A number is written by placing the numbers 19 through 73 im sequence. How many times can this number be divided by 3 withot rest?

None. Division by three will have a remainder of 1. SonLight had the correct approach: sum of digits is (1+9) + (45*5 + 20*10) + (28+6) = 469 => 19 => 10 => 1. I leave it as an exercise for the other readers as to why I wrote the computation as I did.

Hi kelseymh

...

Excellent job; full marks.
infinisa
Hi kesleymh

Wow, that was quick!

I teach maths and try not only to solve maths problems but also to explain the solutions clearly.
kelseymh
 infinisa wrote: Hi kesleymh Wow, that was quick! I teach maths and try not only to solve maths problems but also to explain the solutions clearly.

Indeed! I'm a particle physicist, and have the same goal. In this case, by showing some, but not all, of the intermediate steps, I hoped that others would learn by filling in the gaps.
loremar
 Code: #include using namespace std; int main() {    int i = 19; //numbers in the sequence 19-73    int x = 0; //remainder    int y = 0; //remainder and number in sequence concatenated         for(;i<74;)        {            y=x*100+i;            x=y%3;            i++;         }    cout << x;    getchar(); }

The program displays the last remainder. So if it displays zero then it is divisible by 3.
As to how many times it is divisible by 3, that's another story.

I run the program and the last remainder is 1 which is the same answer by kelseymh.
If I approach it by Math, I honestly would have get the answer by next year. To be honest.