Alan Smith wrote:Hi,
Also, please don't give me the answer to this!
Ivan Jozsef Balazs wrote:
Alan Smith wrote:Hi,
Also, please don't give me the answer to this!
I hope not risking to give the answer with the hint on the loop constructions.
Alan Smith wrote:I'm trying to find the smallest number that is evenly divisible by all numbers in the range 110. I know I can use ten 'ands' to check if a number is divisible by each number in the range but it just seems messy and longwinded. Anyone have any ideas?
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Yes: think about factors. If a number is divisible by 10, you already know that it MUST be divisible by 2 and 5  and what do those two numbers have in common?.
Chew on that for a bit...
BTW, this doesn't really have anything to do with a "range operator".
Winston
Alan Smith wrote:Hi Winston, I have the solution but its a mess! Basically, I want to refactor the code and am looking for the approach programmatically as opposed to the problem itself.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Alan Smith wrote:Hi Winston, I have the solution but its a mess! Basically, I want to refactor the code and am looking for the approach programmatically as opposed to the problem itself.
I don't understand that last sentence at all. Did you actually read my post?
Winston
Matthew Brown wrote:
Oh, and you really don't need to check i % 1 .
Alan Smith wrote:Yes Winston, I read your post but my maths is a little loose...now that you mention it. I know that what 2 and 5 have in common is that they are both evenly divisible into 10. But I'm genuinely stumped as to what I can do with that, sorry!
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Matthew Brown wrote:
Alan Smith wrote:
Matthew Brown wrote:
Oh, and you really don't need to check i % 1 .
Then I'm lost!
What is (1 % 1)? (2 % 1)? (3 % 1)? (34865 % 1)? Notice a pattern?
Winston Gutkowski wrote:
Alan Smith wrote:Yes Winston, I read your post but my maths is a little loose...now that you mention it. I know that what 2 and 5 have in common is that they are both evenly divisible into 10. But I'm genuinely stumped as to what I can do with that, sorry!
And what are 2 and 5 divisible by?
Winston
Alan Smith wrote:They all equate to zero?
Matthew Brown wrote:
Alan Smith wrote:They all equate to zero?
That's right. All integers are divisible by 1. (i % 1 == 0) will always be true, so there's no need to check it.
Alan Smith wrote:Both are divisible by 1.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Alan Smith wrote:Both are divisible by 1.
As Matthew said, all numbers are divisible by 1. What else are 2 and 5 divisible by, and what is the difference between them and 10?
Winston
Alan Smith wrote:2 is divisible by itself, 5 is divisible by itself. Difference between 10 and 2 = 8, difference between 10 and 5 = 5.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Alan Smith wrote:2 is divisible by itself, 5 is divisible by itself. Difference between 10 and 2 = 8, difference between 10 and 5 = 5.
You're being too literal: What is similar about 2 and 5, that is different about 10? Hint: if you reread all the posts so far you should be able to find the answer.
Winston
Alan Smith wrote:I think I get what your saying. If anything is a factor of a number you dont have to check it. ie. if I check a number is divisible by 10, 9, 8, and 7 I should get my answer because the rest of the numbers (below 7) are factors of these numbers. Does that make sense?
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Alan Smith wrote:I think I get what your saying. If anything is a factor of a number you dont have to check it. ie. if I check a number is divisible by 10, 9, 8, and 7 I should get my answer because the rest of the numbers (below 7) are factors of these numbers. Does that make sense?
Yup, but you can also do it another, much easier, way. Hint: what are 2 and 5 (and 3 and 7 in your range) called?
Winston
Alan Smith wrote:This is a guess but 2 and 5 are the common divisors, and 3 and 7 are the undivisors (for want of a better word!).
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Alan Smith wrote:This is a guess but 2 and 5 are the common divisors, and 3 and 7 are the undivisors (for want of a better word!).
OK, maybe it's best that you look at this page, because I'm clearly not explaining it properly. The fact is that you don't have to check every number in your range, but the ones that you do check are very important.
Winston
Alan Smith wrote:Sorry for wreaking your head, i'll have a look and take it from there. Thanks for your patience.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Alan Smith wrote:Sorry for wreaking your head, i'll have a look and take it from there. Thanks for your patience.
No probs. The fact is that you DON'T have to check every number to work out the smallest number that is divisible by every number from 110  in fact, you only have to deal with the factors 9, 8, 7 and 5  but I'll leave you to work out why.
Winston
Aleksey Vladimirovich wrote:Could you explain please, why checking of 9, 8, 7 and 5 would be enough?
Ivan Jozsef Balazs wrote:
Aleksey Vladimirovich wrote:Could you explain please, why checking of 9, 8, 7 and 5 would be enough?
If 8 is a divisor of a number, then so are its divisors, 2 and 4, as well.
If 9 is a divisor of a number, then so is 3.
If 2 and 3 divide a number, so does 6. Why?
n=2.x (1)
n=3.y (2)
From 3 times (1) 3.n = 6.x (3)
From 2 times (2) 2.n = 6.y (4)
Now subtract (4) from (3):
n = 6x6y=6.(xy)
Pretty elementary stuff.
Aleksey Vladimirovich wrote:I got this, that is why I wrote about [6...10] range. My question was why only those 4 particular numbers?
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
fred rosenberger wrote:What you are trying to find is the "least common multiple" of the numbers 1 through 10. Google that term, and you will find tons of info. What folks have been hinting at here is that there are two kinds of numbers...someone already mentioned "composite" numbers. If you know (or find out) what the opposite of a composite is, it will help you.
Aleksey Vladimirovich wrote:I got this, that is why I wrote about [6...10] range. My question was why only those 4 particular numbers?
quick note  that is actually FIVE numbers....
Winston Gutkowski wrote:No probs. The fact is that you DON'T have to check every number to work out the smallest number that is divisible by every number from 110  in fact, you only have to deal with the factors 9, 8, 7 and 5  but I'll leave you to work out why.
Winston
Aleksey Vladimirovich wrote:You misunderstood me...
Aleksey Vladimirovich wrote:
I didn't get how come checking of only these 4 numbers (9, 8, 7 and 5) is a sufficient condition...
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
fred rosenberger wrote:Well...look at one of 'missing' numbers...let's say 2.
Aleksey Vladimirovich wrote:
fred rosenberger wrote:Well...look at one of 'missing' numbers...let's say 2.
No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is  I don't see any rule in this sequence and asking someone to explain.
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
Aleksey Vladimirovich wrote:No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is  I don't see any rule in this sequence and asking someone to explain.
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
fred rosenberger wrote:
Aleksey Vladimirovich wrote:
fred rosenberger wrote:Well...look at one of 'missing' numbers...let's say 2.
No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is  I don't see any rule in this sequence and asking someone to explain.
so take 6. you know that if a number is divisible by 6, it must be divisible by 2. It must also be divisible by 3. In fact, if it is divisible by 2 and 3, you know it MUST be divisible by 6.
Now take that a step further. we know that if your candidate is divisible by 8, it must be divisible by 2.
Please READ the article suggested above  about composite numbers, their opposites, and finding least common multiples. That is all relevant. we didn't post those suggestions just to hear ourselves talk.
Winston Gutkowski wrote:
Aleksey Vladimirovich wrote:No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is  I don't see any rule in this sequence and asking someone to explain.
Simply put:
9 = 3 x 3
and
8 = 2 x 2 x 2
so any number that divides by 9 MUST divide by 3, and any number that divides by 8 MUST divide by 2  ergo any number that divides by both 9 AND 8, must divide by both 3 AND 2; and what numbers divide by both 3 AND 2?
Do you also notice that those numbers 2, 3, 5 and 7 have cropped up again? I refer you to my post about 50 back.
Winston
Aleksey Vladimirovich wrote:Yeah, I see. But I don't think this algorithm would be faster than the one what I was talking about. Or would it?
"Leadership is nature's way of removing morons from the productive flow"  Dogbert
Articles by Winston can be found here
Aleksey Vladimirovich wrote:
Winston Gutkowski wrote:
Aleksey Vladimirovich wrote:No, let's say 6 instead of 2, what in this case? I think it's possible that number would be divisible by 9, 8, 7 and 5, but not by 6 (not in this particular case), what I'm saying is  I don't see any rule in this sequence and asking someone to explain.
Simply put:
9 = 3 x 3
and
8 = 2 x 2 x 2
so any number that divides by 9 MUST divide by 3, and any number that divides by 8 MUST divide by 2  ergo any number that divides by both 9 AND 8, must divide by both 3 AND 2; and what numbers divide by both 3 AND 2?
Do you also notice that those numbers 2, 3, 5 and 7 have cropped up again? I refer you to my post about 50 back.
Winston
Yeah, I see. But I don't think this algorithm would be faster than the one what I was talking about. Or would it?
Alan Smith wrote:I wonder if there is an algorithm that can be passed a range of numbers and find what numbers in the range need to be used, and then process them numbers to return the smallest number. Its a little out of my league unfortunately but just a though
Aleksey Vladimirovich wrote:I don't think this algorithm would be faster than the one what I was talking about. Or would it?
Aleksey Vladimirovich wrote:The sufficient condition will be to check only range: [(lowerBorderOfRange < upperBorderOfRange / 2 ? (int) upperBorderOfRange / 2 : lowerBorderOfRange), upperBorderOfRange]
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
I knew I would regret that burrito. But this tiny ad has never caused regrets:
Garden Master Course kickstarter
https://coderanch.com/t/754577/GardenMasterkickstarter
