Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider ice cream shops numbered 1 to 1000 and same number of boys. The first boy goes to 1,2,3,4...1000. The second boy goes to 2,4,6...1000. 3rd goes to 3,6...,and so on for each boy. Which shop will get the most customers?

Note: A generalized solution i.e. for n shops will be preferred.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

You’re looking for the integer $k\in\{1,\dots,n\}$ that maximizes the divisor function. If $m=\prod_{i=1}^rp_i^{a_i}$, where the $p_i$ are distinct primes, then $d(m)=\prod_{i=1}^r(a_1+1)$. For literature on the divisor function see its entry in OEIS; these graphs give you some idea of its overall behavior. This table lists the divisors and $d(m)$ for $m\le 1000$; on a quick eyeball scan it appears that $d(840)=32$ is the maximum for $n=1000$.

share|improve this answer
    
You are confusing $k$ and $m$ here (and then using $n$ from the original problem.) You want $k\in\{1,...,n\}$ and maximize $d(k)$. Not even sure where $m$ comes in. –  Thomas Andrews Oct 8 '12 at 12:38
    
@Thomas: There was only one typo; it should have been $\{1,\dots,n\}$. $m$ is simply a convenient variable distinct from both $k$ and $n$; I didn’t want to risk confusion between a general statement about the divisor function and the $k$ that I was talking about originally. –  Brian M. Scott Oct 8 '12 at 12:42
1  
This question was asked in an exam. How do I find such value of k that maximizes divisor function without using tables ? –  Serious Oct 8 '12 at 12:56
1  
@Serious: I don’t know of a really nice way. $840=2^3\cdot3\dot5\cdot7$; with $4$ distinct prime factors you automatically get at least $16$, and cubing the $2$ gives you an extra factor of $2$ at the small cost of multiplying your number by $4$ instead of $11$. If faced with this problem, I’d start by looking at products of small primes and then seeing what I could gain by raising the exponent on one or two of them; that would at least limit the testing. –  Brian M. Scott Oct 8 '12 at 13:07
1  
@Serious the "eyeball" way to solve this sort of problem is to realize the answer must be of the form $2^a3^b5^c7^d$ for $a\geq b\geq c\geq d$. It can't have any higher prime factor because $2\cdot 3\cdot 5\cdot 7\cdot 11>1000$. Then some trial and error finds $2^3\cdot 3\cdot 5\cdot 7=840$ –  Thomas Andrews Oct 8 '12 at 13:09
show 3 more comments

Such numbers which have the most number of factors than all numbers lesser than themselves are called Highly composite numbers. The Wikipedia link also gives a table of such numbers, like 1,2,4,6,12,24,etc.

The answer for n=1000 turns out to be 840.

share|improve this answer
    
Note that this doesn't prove that $840$ is the unique answer - there might be a number between $840$ and $1000$ which has the same number of divisors as $840.$ –  Thomas Andrews Oct 8 '12 at 12:46
    
Thanks for answering. Interesting article. –  Serious Oct 8 '12 at 14:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.