1

I have a weird problem I'm hoping has a clever math solution! Is there a way to figure out what percentage of large numbers are divisible by a number? For example, what percentage of $8$ digit numbers would be divisible by $7$? How would I figure this out for $X$ digit numbers and other numbers to divide by? Thanks for any help! Rick

Mohsen Shahriari
  • 6,718
Rick Love
  • 11
  • 1
    Approximately $\frac{1}{7}$'th of the $8$ digit numbers will be divisible by $7$. This, because exactly one out of every seven consecutive numbers will be divisible by $7$. If you want the exact amount rather than just saying "approximately $\frac{1}{7}$'th", you just need to consider the boundaries of the set you are considering and how soon after the beginning or before the end you find another multiple of $7$. – JMoravitz Aug 07 '20 at 14:06
  • 1
    More generally, among the numbers $1,2,3,\dots,n$ there will be $\left\lfloor \dfrac{n}{k}\right\rfloor$ of these who are divisible by $k$ and so among the numbers $m,m+1,m+2,\dots,n$ there will be $\left\lfloor\dfrac{n}{k}\right\rfloor - \left\lfloor\dfrac{m-1}{k}\right\rfloor$ seen by just counting the amount from $1$ to $n$ and removing from the count those which occurred from $1$ to $m-1$. To get a ratio or percentage... all that remains is then to divide by the total number of numbers in your range. – JMoravitz Aug 07 '20 at 14:11
  • I added my answer for a range of numbers (which includes the case of $8$-digit numbers). If you have a more varied set of "large numbers", then it all depends on the set. For example, the number of $8$-digit prime numbers divisible by $7$ is exactly zero. –  Aug 07 '20 at 14:15

1 Answers1

0

Presume your numbers are all between $m$ and $M$. For example, for $8$-digit numbers, $m=10000000, M=99999999$.

Lat $d$ be the number you want to check the divisibility with.

$\lfloor M/d\rfloor$ is the quotient obtained by dividing the largest number $\le M$ divisible by $d$ with $d$. Similarly, $\lceil m/d\rceil$ is the quotient obtained by dividing the smallest number $\ge m$ divisible by $d$ by $d$. Therefore, the number of numbers in the range $[m,M]$ divisible by $d$ is $\lfloor M/d\rfloor-\lceil m/d\rceil+1$.

If you are interested in percentage, it is going to be:

$$\frac{\lfloor M/d\rfloor-\lceil m/d\rceil+1}{M-m+1}\times 100\%$$

Note: the notation $\lfloor x\rfloor$ denotes the largest integer $\le x$. Similarly, the notation $\lceil x\rceil$ denotes the smallest integer $\ge x$.

In your example ($d=7$), $\lfloor M/d\rfloor=14285714$ and $\lceil m/d\rceil=1428572$, so the percentage is $\frac{14285714-1428572+1}{99999999-10000000+1}=\frac{12857143}{90000000}\approx 14.2857144444\ldots \%$, which is very close to $1/7$.

  • Thanks for your help! I wasn't sure if any weirdness appeared in large numbers in terms of divisors. I think this gives us an elegant solution to an otherwise thorny coding challenge. Very helpful to have this formula so we can calculate exact percentages. – Rick Love Aug 10 '20 at 08:07