Which Unlucky Neighbor Got The Most Election Spam?
It's an election year, and volunteers are putting posters up for their favorite candidates. There is a long street in your town with 1,000 houses in a row.
The first volunteer who passes through this street has time to put a poster on the door of every house. The second volunteer comes a bit later, and only has time to put a poster on the door of every second house, starting with the second house. The third volunteer puts a poster on the door of every third house, starting with the third house. This continues until the thousandth (and last) volunteer runs down the street and puts a single poster on the thousandth house.
Which house has the most campaign posters on its door?
Image credit: Sean O'Flaherty via Wikimedia Commons
The answer is 840.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
22 solutions
This is not a rigorous enough argument. What if multiplying the first four primes gave us 5 0 1 ? Then we would be stuck, but would 1 6 really be maximal?
That said, I don't know if there really is any rigorous argument that doesn't involve guess and check. This is how I would have found it if I didn't know 840 already from prior knowledge:
What if the number only has one distinct prime factor? Then we would get 2 9 = 5 1 2 with 1 0 divisors.
Two distinct prime factors? 2 5 3 3 with 24 divisors
Three? 2 4 3 2 5 1 30 divisors
Four? 2 3 3 1 5 1 7 1 , as we found before, with 32 divisors
Five? Impossible, since 2 ∗ 3 ∗ 5 ∗ 7 ∗ 1 1 > 1 0 0 0 .
(I found these maxima using guess and check)
Log in to reply
That's an interesting point, although I don't know what makes me think that the one with most quantity of distinct prime factors will have more divisors. Ill check that later!
Log in to reply
Well done; I used a similar thought process. It is interesting to solve for a 1,000,000 house street, and with higher numbers, it is better to include less distinct prime factors.
The solution should be LCM of first n integers, where LCM is just less than 1000. In this case LCM of 1,2,3,4,5,6,7,8 is 840 < 1000
Log in to reply
First of all, you should also explain what makes you think that ! Because I doubt it. Suppose the no. of houses was 400(instead of 1000) with 400 volunteers running around...in that case, your solution would yield LCM of 1,2,3,4,5,6=60 (as lcm of 1,2,3,4,5,6,7=420 >400) But this is not the correct answer as 360 has more divisors than 60. So it won't give the answer :-)
I actually did it that way..:)
Good logical solution! Accepted by me! :)
Logic is not something abstract...its also a way of solving problems till it has a sound base...so solving with logic is perfectly alright in my view !
Log in to reply
Wrote a python code.
count=[0] 1001 for i in xrange(1,1001): for j in xrange(1,1000/i+1): count[i j]+=1
print max(zip(count,xrange(1001)))
I accepted this just like what i think it first i just don't realize to multiply it by 4
Log in to reply
But forget how did i think like that. Can you remind me why should multiples the primes?
I multiplied by 4 because 2 1 0 is yet a number that if you multiply by 4 is still less than 1 0 0 0 . Renember that we want to maximize the quantity of divisors.
This is the way I did it! :-)
I don't see how logic would not be allowed :) I used the same method, though I admit it seems a bit guesswork-ish.
The house with the most factors is the house with the most election spam. We quickly realize that we must find a number that is the multiple of as many small primes as possible. We see that the house number is less than or equal to 1 , 0 0 0 , and the fact that the greatest common multiple of the primes from 2 to 7 is 8 4 0 , which also happens to be the least common multiple of the first 8 whole numbers. Thus, our answer is 8 4 0 .
Eh? There is no 'greatest common multiple', so I assume you meant 'least common multiple', but even then, the least common multiple of the primes from 2 to 7 (which are 2 , 3 , 5 , 7 ) is 2 ⋅ 3 ⋅ 5 ⋅ 7 = 2 1 0 = 8 4 0 .
Log in to reply
Wait that was poorly phrased
I meant to say that the "greatest multiple common to all of 2, 3, 5, and 7 that was less than or equal to 1000."
Exactly my friend, exactly.
The answer will be a number with maximum number of factors 1x2=2, 1x2x3=6, 1x2x3x4=24, 1x2x3x4x5=120, 1x2x3x4x5x7=840, (6 is excluded because 2x3 is already there) 1x2x3x4x5x7x9=7560, ........................................so on. so the largest number in this series below 1000 is 840.
We answer this problem by the same way bro! First method that crossed in my mind was n ! ≤ 1 0 0 0 . At this point I got 7 2 0 and then I rethought my answer until I realized the method like you made.
But, I doubt 1 thing, if the no. of houses would have been 15 instead of 100, your process would have answered 6, as it the highest in the series who satisfies being less than 15. But, in case of 15 houses, the correct answer is 12th house, with 6 posters on it. I guess the series requires rectification as, 1x3x4 = 12, instead of 1x2x3x4 = 24, as '2', is already contained by '4' ; according to your own logic.
An analysis of the problem reveals that it amounts to finding the number between 1 and 1000 that has the largest number of divisors. The technique for calculating this may be found here .
To get the highest possible number of divisors, we need to combine as many different prime factors as possible, and multiply by 2 s when the highest possible prime factor has been found, as this in total gives the most combinations. By some testing we find the following:
2 3 ⋅ 3 ⋅ 5 ⋅ 7 = 8 4 0
which has ( 3 + 1 ) ⋅ ( 1 + 1 ) ⋅ ( 1 + 1 ) ⋅ ( 1 + 1 ) = 4 ⋅ 2 ⋅ 2 ⋅ 2 = 3 2 factors.
No other combination gives more factors.
Thus, house number 8 4 0 has the most posters.
The solution is that number which has maximum number of factors. Also observe that any factor of a number can be constructed my multiplying one or more of its prime factors. So that number should also have maximum number of prime factors. observe that 2 3 5 7=210 is the number less than 1000 having maximum number of unique prime factors. So the solution of the problem is definitely a multiple of 210. Now observe that 2 2 210=840 is less than 1000, but 2 3*210=1260 is larger than 1000. Hence the solution is 840
Concept used after generating a base of 210 is to max factors -- concept 2 2 is greater than 3 1. Even the base uses the same concept!
well, lucky guess + wolfram alpha
wow genius
It's really annoying to see your arduous solutions. I didn't post a solution because I saw someone already has, & found only your link. Try to benefit yourself from this community. I assure you, you won't make a word from this site, unless you use it to learn.
Log in to reply
Hi Paramjit! Could you please post your solution as a comment instead?
Don't be so harsh. I don't blame him for googling that either -- I think finding the number less than 1000 with the most divisors is a rather trivial task.
A more constructive link: http://en.m.wikipedia.org/wiki/Highly composite number
@Santanu, I prefer to be an ignorant one day, and read the solutions to learn, than being an ignorant all my life, thinking that Im smarter than others just because I look for the answer in google. Nice! You're putting google above your level.
Since I really thought that this was easy , I did not post the entire solution as I expected all to know it...If in the process I have harmed anyone's ideas or ideals I am sorry ...Since all know that the answer will be the number with the highest number of factors (below 1000) and as I can see that no one has given any way how to find that other than trial and error or Wikiped-ing or Googl-ing I think I did the right thing
Log in to reply
Two solutions above have an understandable procedure, with the beauty it deserves. Also, when I personally write a solution, I don't think if this was hard or easy for me, I think on those that are actually getting the solution to grow up. This, because when I don't know a problem I read the solutions expecting clear ones, and that's what I've got. That makes me think that the ones that will read the solutions I post will expect the same, since we're here to learn. Your solution is nothing more than two links.
Can anyone please tell me how to proceed correctly and not in a random way?
Log in to reply
this question is based on the concept of highly composite number
\boxed{volunteer1} 1 2 3 4 ......................1000 \boxed{volunteer2} 2 4 6 .....................(all the multiples of 2 ) \boxed{volunteer3} 3 6__9..........999 (all the multiple of 3 ) \boxed{volunteer4} .. . . . \boxed{volunteer1000} 1000 (only 1 house )
so you see a pattern here , so the number (which actually represent a house in this problem ) which has the highest number of divisors and we have search it between 1 and 1000 as there are 1000 houses
to find how many divisor a number have , you can use the folllowing algorithm for eg take 84
1 . find all the prime factor so 84 has 2,3 7 as its prime factors
- note down the exponent appearing if you write the number as a product of its prime factors 84=2^{2} 3^{1} 7^{1}
so here the exponent are 2,1 ,1
- add 1 to each exponent and then multiply them together
so here 2+1=3 (exponent of 2) and 1+1=2 (exponent of 3) and 1+1=2(exponent of 7)
now multiply 3\times2\times2
so for 84 we have 12 divisors {the reason why we multiplied the exponents use the multiplication rule of probability ...., if some one wants more on this step three drop your email here ... }
now if we use this thing here by some amount of trial and error we can find that 840 is the number
as 840 =2^{3}\times3^{1}\times5^{1}\times7^{1}
after adding one , to each exponent and multiply
4\times2\times2\times2 =32
Log in to reply
I think this is what you meant to post, Vikas:
this question is based on the concept of highly composite number
v o l u n t e e r 1 1 , 2 , 3 , 4 , . . . . . . . . . . . . . . . . . . . . . . 1 0 0 0 v o l u n t e e r 2 2 , 4 , 6 . . . . . . . . . . . . . . . . . . . . . (all the multiples of 2 ) v o l u n t e e r 3 3 , 6 , 9 . . . . . . . . . . 9 9 9 (all the multiple of 3 ) v o l u n t e e r 4 . . . . . v o l u n t e e r 1 0 0 0 1 0 0 0 (only 1 house )
so you see a pattern here , so the number (which actually represent a house in this problem ) which has the highest number of divisors and we have search it between 1 and 1000 as there are 1000 houses
to find how many divisor a number have , you can use the folllowing algorithm for eg take 84
1 . find all the prime factor so 84 has 2,3 7 as its prime factors
note down the exponent appearing if you write the number as a product of its prime factors 8 4 = 2 2 3 1 7 1 so here the exponent are 2,1,1
add 1 to each exponent and then multiply them together so here 2+1=3 (exponent of 2) and 1+1=2 (exponent of 3) and 1+1=2(exponent of 7)
now multiply 3 × 2 × 2
so for 84 we have 12 divisors {the reason why we multiplied the exponents use the multiplication rule of probability ...., if some one wants more on this step three drop your email here ... }
now if we use this thing here by some amount of trial and error we can find that 840 is the number
as 8 4 0 = 2 3 × 3 1 × 5 1 × 7 1
after adding one , to each exponent and multiply
4 × 2 × 2 × 2 = 3 2
Tip: add '\ (' and '\ )' (without the quotes and spaces) to the beginning and end of all your math.
Hi Vikas! I've also come across the divisor function before (i.e. take each exponent of the prime factorisation of some number, add one to each exponent and multiply to get the total number of divisors of some number). Can you explain why this works? What is the mathematical reasoning behind it?
Log in to reply
@Mark Mottian – So let's say that the prime factorization of integer N is 2 4 × 3 6 . We can choose ( 0 , 1 , 2 , 3 , o r 4 ) for our exponent of 2 , since we can have a factor of N that is a pure power of 3 , with no factors of 2 . Our choices for what power we raise 3 to is 0 , 1 , 2 , 3 , 4 , 5 , 6 ) . Thus, we have ( 4 + 1 ) × ( 6 + 1 ) factors. Can you see why this holds true for any number?
The first solution by Diego E. Nazario Ojeda is completely logical and there is no problem with it whatsoever.....You can refer it for the best...And yeah, its not random either :-)
I'm afraid I did something similar. I looked up the answer on the Online Encyclopedia of Integer Sequences. Looked up " number of divisors ", found
"See A002183, A002182 for records."
in the cross-references of the first search result (the actual function counting the number of divisors τ ( n ) ), and found 840 in the sequence A002182 .
Log in to reply
Also, has anyone else noticed how the comments aren't arranged chronologically? It's a bit disorienting.
for this we have to take a set of those no.'s whose LCM is less than 1000. Here it comes out to be 2,3,4,5,6,7&8. Its LCM comes out to be 840. And also the 840th person will also put a poster on it so it is the house which will have maximum posters on it.
Well, the answer is the LCM of starting integers just less than 1000 i.e LCM of 1,2,...8 is 840 :)
The actual question is- Find the +ve integer below 1000 with maximum no. of factors? and this question has been beautifully disguised in the problem.
for this we have to take a set of those no.'s whose LCM is less than 1000. Here it comes out to be 2,3,4,5,6,7&8. Its LCM comes out to be 840. And also the 840th person will also put a poster on it so it is the house which will have maximum posters on it.
the aim would be to find number less than thousand with maximum divisors. Begin with prime numbers first 2 * 3 * 5 * 7=210 On further multiplying by the next prime number 11 the product exceeds 1000. Now we can give powers to prime numbers. The least way increasing the number pf divisors keeping the product below 1000 would be to increase powers of 2. 210 * 2 =420 210 * 4=840 <1000 and we can not go beyond it .. so answer is 840 .!!
simple!!! just find which no has more no of factors; 840 has 32 trivial factors which is the highest;
It's the largest product that can be formed by the largest no. of co-prime numbers. Since the maximum numbers of co-prime should be used, they should be as small as possible.
On trial these co-prime numbers can be found to be 3,5,7 and 8 giving largest product possible by 4 co-prime numbers i.e. 840.
The house with the most campaign posters will be the one with the most factors. If we want it to have many factors, it should be the product of as many numbers as possible, starting from 1.
For it to be a multiple of 1 we take 1
To be a multiple of 2 as well we take 1 * 2 = 2
To be a multiple of 3 as well we take 1 * 2 * 3 = 6
To be a multiple of 4 as well we take 1 * 2 * 3 * 2 (since 4 = 2 * 2) = 12
To be a multiple of 5 as well we take 1 * 2 * 2 * 3 * 5 = 60
60 is already a multiple of 6,
To be a multiple of 7 as well we take 1 * 2 * 2 * 3 * 5 * 7 = 420
To be a multiple of 8 as well we take 1 * 2 * 2 * 3 * 5 * 7 * 2 (since 8 = 2 * 2 * 2) = 840
Now obviously if we multiply 840 by any integer bigger than 1 we will exceed 1000, so 840 must be the answer.
Answer must be multiple of 2 3 4 5 7 ,here we have not consider 9 as answer must be smaller than 1000
the number between 0 to 999 having more number of factors is 840
The answer is the no. with max. no. of divisors. We know that if N= a p b q ;[where a&b are prime];then no. of divisors is (p+1)(q+1). we begin with divisors 2x3x5x7x9 and so on; we see that 2x3x5x7x9 exceeds 1000;so we confine ourselves to using only 2,3,5,7and increase the indices to get a larger number; By using 2 three times we have the largest no.with these divisors and also has the largest no. of divisors. 840= 2 3 x3x5 x7 and no.of divisors=32.
Not difficult actually, all u have to do is find the L.C.M of all the numbers before 10. Since every other except prime numbers is a multiple of any of this numbers. when the L.C.M is gotten then u find the greatest multiple of this L.C.M that is less than or equal to 1000 then Gbam that's your answer.
Mathematical explanation;
prime numbers <10 = 2,3,5&7 L.C.M = 2x3x5x7 = 210 greatest multiple of 210 <0r= 1000 is 840.
we should try to cover maximum from 1 to 10,so we will take 2 3 4 5 7=840 .very few are missed so 840 should be the number.
Which integer has max factors within 1000 and it is 1x2x3x5x7x2x2=840.
The question boils down to which number has the greatest number of divisors. That would be 8 4 0 with 3 2 divisors.
Do people actually want to know how to get to this result? I don't think there is any formal argument that doesn't involve guess and check (I already knew 840 was the answer from prior knowledge).
Think as to how to maximize the number of divisors... 32 has less divisors than 30.Hence,after arriving at 210(prime factors--2,3,5,7), we cannot use another 2 and 3, therefore we have to be content with multiplying with 2times2. Resultant 840
Log in to reply
LCM and other methods will not work for all cases. Consider for example, there are 400 houses. Then the answer is 210 in all methods explained above, but the correct answer is 360
Log in to reply
Great observation! While one can reduce the number of cases to check by noticing that some numbers have more divisors than others, some guess-and-check is unavoidable.
I solved this with logic, i don't know if it's permitted.
Well, the question can be rewritten: "Find the positive integer in the interval [ 1 , 1 0 0 0 ] with the most quantity of divisors.
When one looks for the quantity of divisors, remember that if a number is factorized in the form p 1 a ⋅ p 2 b ⋅ … ⋅ p n k , then the quantity of divisors is ( a + 1 ) ( b + 1 ) … ( k + 1 ) . So, if we want to maximize the number of divisors of some number, one should, first of all, multiply a group of distinct primes with a product ≤ 1 0 0 0 .
One can easily find that 2 ⋅ 3 ⋅ 5 ⋅ 7 = 2 1 0 , and if you multiply by 1 1 then the product is > 1 0 0 0 . But 2 1 0 is yet a number that can be multiplied by 4 = 2 ⋅ 2 , and it will still being < 1 0 0 0 . We've maximized at this point, and got the number 2 3 ⋅ 3 ⋅ 5 ⋅ 7 = 8 4 0 , which has 3 2 divisors. Thus, the answer is 8 4 0 .