2
$\begingroup$

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.

2 Answers 2

2

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

  • 0
    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.2012-10-08
  • 0
    @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.2012-10-08
  • 0
    Why don't you just use $k$ instead of $m$ or visa versa, rather than introducing two variables? You say $k\in\{1,...,n\}$ then have reference $m\leq 1000$, which is really the condition on $k$, unless $m$ and $k$ are essentially the same thing2012-10-08
  • 0
    @Thomas: They’re both free variables, and I definitely want the one in the second sentence to have a different name from the one in the first sentence; the one in the last sentence could go either way.2012-10-08
  • 1
    This question was asked in an exam. How do I find such value of k that maximizes divisor function without using tables ?2012-10-08
  • 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.2012-10-08
  • 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$2012-10-08
  • 0
    It would be more helpful if the downvoter explained.2012-10-08
2

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.

  • 0
    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.$2012-10-08
  • 0
    Thanks for answering. Interesting article.2012-10-08