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