Question Number 118043 by prakash jain last updated on 14/Oct/20
![How many numbers in the range [1,10^n −1] are divisible by 9? digit repetitions are not allowed.](Q118043.png)
$$\mathrm{How}\:\mathrm{many}\:\mathrm{numbers}\:\mathrm{in}\:\mathrm{the}\:\mathrm{range} \\ $$$$\left[\mathrm{1},\mathrm{10}^{{n}} −\mathrm{1}\right]\:\mathrm{are}\:\mathrm{divisible}\:\mathrm{by}\:\mathrm{9}? \\ $$$$\mathrm{digit}\:\mathrm{repetitions}\:\mathrm{are}\:\mathrm{not}\:\mathrm{allowed}. \\ $$
Commented by mr W last updated on 15/Oct/20
$${without}\:{repetition}\:{means}\:{max}. \\ $$$$\mathrm{10}\:{digits}\:{are}\:{allowed},\:{i}.{e}.\:{n}\leqslant\mathrm{10}. \\ $$$$ \\ $$$$\mathrm{10}\:{digit}\:{numbers}: \\ $$$$\mathrm{0}+\mathrm{1}+\mathrm{2}+..+\mathrm{9}=\mathrm{45}\:\checkmark \\ $$$$\Rightarrow\frac{\mathrm{9}}{\mathrm{10}}×\mathrm{10}!=\mathrm{9}×\mathrm{9}! \\ $$$$ \\ $$$$\mathrm{9}\:{digit}\:{numbers}: \\ $$$$\mathrm{1}+\mathrm{2}+..+\mathrm{9}=\mathrm{45}\:\checkmark \\ $$$$\Rightarrow\mathrm{9}! \\ $$$$\mathrm{0}+\mathrm{1}+\mathrm{2}+..+\mathrm{8}=\mathrm{36}\:\checkmark \\ $$$$\Rightarrow\frac{\mathrm{8}}{\mathrm{9}}×\mathrm{9}!=\mathrm{8}×\mathrm{8}! \\ $$$$\Rightarrow\mathrm{9}!+\mathrm{8}×\mathrm{8}!=\mathrm{17}×\mathrm{8}! \\ $$$$ \\ $$$$\mathrm{8}\:{digit}\:{numbers}: \\ $$$${without}\:\mathrm{0}+\mathrm{9}\:\Rightarrow\mathrm{8}! \\ $$$${without}\:\mathrm{1}+\mathrm{8},\mathrm{2}+\mathrm{7},\mathrm{3}+\mathrm{6},\mathrm{4}+\mathrm{5}\:\Rightarrow\mathrm{4}×\frac{\mathrm{7}}{\mathrm{8}}×\mathrm{8}!=\mathrm{4}×\mathrm{7}×\mathrm{7}! \\ $$$$\Rightarrow\mathrm{8}!+\mathrm{4}×\mathrm{7}×\mathrm{7}!=\mathrm{36}×\mathrm{7}! \\ $$$$ \\ $$$$\mathrm{7}\:{digit}\:{numbers}: \\ $$$${without}\:\mathrm{0}+\mathrm{1}+\mathrm{8},\mathrm{0}+\mathrm{2}+\mathrm{7},\mathrm{0}+\mathrm{3}+\mathrm{6},\mathrm{0}+\mathrm{4}+\mathrm{5}\:\Rightarrow\mathrm{4}×\mathrm{7}! \\ $$$${without}\:\mathrm{1}+\mathrm{8}+\mathrm{9},\mathrm{2}+\mathrm{7}+\mathrm{9},\mathrm{3}+\mathrm{6}+\mathrm{9},\mathrm{4}+\mathrm{5}+\mathrm{9}\:\Rightarrow\mathrm{4}×\frac{\mathrm{6}}{\mathrm{7}}×\mathrm{7}!=\mathrm{4}×\mathrm{6}×\mathrm{6}! \\ $$$${without}\:\mathrm{1}+\mathrm{2}+\mathrm{6},\mathrm{1}+\mathrm{3}+\mathrm{5}\:\Rightarrow\mathrm{2}×\frac{\mathrm{6}}{\mathrm{7}}×\mathrm{7}!=\mathrm{2}×\mathrm{6}×\mathrm{6}! \\ $$$${without}\:\mathrm{2}+\mathrm{3}+\mathrm{4}\:\Rightarrow\frac{\mathrm{6}}{\mathrm{7}}×\mathrm{7}!=\mathrm{6}×\mathrm{6}! \\ $$$$\Rightarrow\left(\mathrm{4}×\mathrm{7}+\mathrm{4}×\mathrm{6}+\mathrm{2}×\mathrm{6}+\mathrm{6}\right)\mathrm{6}!=\mathrm{10}×\mathrm{7}! \\ $$$$ \\ $$$$\mathrm{6}\:{digit}\:{numbers}: \\ $$$${without}\:\mathrm{0}+\mathrm{1}+\mathrm{2}+\mathrm{6},\mathrm{0}+\mathrm{1}+\mathrm{3}+\mathrm{5},\mathrm{0}+\mathrm{2}+\mathrm{3}+\mathrm{4}\:\Rightarrow\mathrm{3}×\mathrm{6}! \\ $$$${without}\:\mathrm{1}+\mathrm{2}+\mathrm{6}+\mathrm{8},\mathrm{1}+\mathrm{3}+\mathrm{5}+\mathrm{9},\mathrm{2}+\mathrm{3}+\mathrm{4}+\mathrm{9}\:\Rightarrow\mathrm{3}×\frac{\mathrm{5}}{\mathrm{6}}×\mathrm{6}!=\mathrm{3}×\mathrm{5}×\mathrm{5}! \\ $$$$\Rightarrow\mathrm{3}\left(\mathrm{6}+\mathrm{5}\right)\mathrm{5}!=\mathrm{33}×\mathrm{5}! \\ $$$$ \\ $$$$\mathrm{5}\:{digit}\:{numbers}: \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{7}+\mathrm{2}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{6}+\mathrm{3}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{5}+\mathrm{4}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{5}+\mathrm{3}+\mathrm{2} \\ $$$$\mathrm{9}+\mathrm{7}+\mathrm{6}+\mathrm{4}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{7}+\mathrm{6}+\mathrm{3}+\mathrm{2} \\ $$$$\mathrm{9}+\mathrm{7}+\mathrm{5}+\mathrm{4}+\mathrm{2} \\ $$$$\mathrm{9}+\mathrm{6}+\mathrm{5}+\mathrm{4}+\mathrm{3} \\ $$$$ \\ $$$$...... \\ $$
Commented by prakash jain last updated on 15/Oct/20
$$\mathrm{Thanks}\:\mathrm{sir}. \\ $$$$\mathrm{It}\:\mathrm{looks}\:\mathrm{listing}\:\mathrm{is}\:\mathrm{the}\:\mathrm{only}\:\mathrm{possible}\:\mathrm{way}. \\ $$$$\mathrm{I}\:\mathrm{thought}\:\mathrm{I}\:\mathrm{had}\:\mathrm{seen}\:\mathrm{a}\:\mathrm{closed}\:\mathrm{forum} \\ $$$$\mathrm{expression}\:\mathrm{somewhere}\:\mathrm{but}\:\mathrm{was}\:\mathrm{not} \\ $$$$\mathrm{able}\:\mathrm{to}\:\mathrm{derive}. \\ $$
Answered by floor(10²Eta[1]) last updated on 24/Dec/20
![from 1 to 10^n −1 we have ((10^n −1)/9) multiples of 9 (considering the numbers with the same digits) so let′s calculate how many numbers have the same digits and are divisible by 9 [aa...a] (n digits) a.n≡0(mod9), a∈[1,9] ∧ n≥2 a∈{1, 2, 4, 5, 7, 8}⇒n=9k, k≥1 a∈{3, 6}⇒n=3k, k≥1 a=9⇒n=k≥2 2 digits: (99) 3 digits: (333, 666, 999) 4 digits: (9999) 5 digits: (99999) 6 digits: (333333, 666666, 999999) [...] 9 digits: (11...1, 22...2, 33...3, ..., 99..9) 2 digits to 9 digits: 5+3.2+9=20 cases 10 digits to 19: 7+3.2+9=22 cases from 1 to x we have x−⌊(x/3)⌋numbers that are coprime with 3 (because ⌊(x/3)⌋ is the number of multiples of 3, from 1 to x) from 2 to x we have (x−⌊(x/3)⌋−1)+3(⌊(x/3)⌋−⌊(x/9)⌋)+9⌊(x/9)⌋ x−1+2⌊(x/3)⌋+6⌊(x/9)⌋numbers that are divisible by 9 and have the same digits from 2 digits to n digits we have n−1+2⌊(n/3)⌋+6⌊(n/9)⌋ numbers that have the same digits and are divisible by 9 Ans: ((10^n −1)/9)−(n−1+2⌊(n/3)⌋+6⌊(n/9)⌋)](Q118072.png)
$$\mathrm{from}\:\mathrm{1}\:\mathrm{to}\:\mathrm{10}^{\mathrm{n}} −\mathrm{1}\:\mathrm{we}\:\mathrm{have}\:\frac{\mathrm{10}^{\mathrm{n}} −\mathrm{1}}{\mathrm{9}}\:\mathrm{multiples}\:\mathrm{of}\:\mathrm{9} \\ $$$$\left(\mathrm{considering}\:\mathrm{the}\:\mathrm{numbers}\:\mathrm{with}\:\mathrm{the}\:\mathrm{same}\:\mathrm{digits}\right) \\ $$$$\mathrm{so}\:\mathrm{let}'\mathrm{s}\:\mathrm{calculate}\:\mathrm{how}\:\mathrm{many}\:\mathrm{numbers}\:\mathrm{have}\: \\ $$$$\mathrm{the}\:\mathrm{same}\:\mathrm{digits}\:\mathrm{and}\:\mathrm{are}\:\mathrm{divisible}\:\mathrm{by}\:\mathrm{9} \\ $$$$\left[\mathrm{aa}...\mathrm{a}\right]\:\left(\mathrm{n}\:\mathrm{digits}\right) \\ $$$$\mathrm{a}.\mathrm{n}\equiv\mathrm{0}\left(\mathrm{mod9}\right),\:\mathrm{a}\in\left[\mathrm{1},\mathrm{9}\right]\:\wedge\:\mathrm{n}\geqslant\mathrm{2} \\ $$$$\mathrm{a}\in\left\{\mathrm{1},\:\mathrm{2},\:\mathrm{4},\:\mathrm{5},\:\mathrm{7},\:\mathrm{8}\right\}\Rightarrow\mathrm{n}=\mathrm{9k},\:\mathrm{k}\geqslant\mathrm{1} \\ $$$$\mathrm{a}\in\left\{\mathrm{3},\:\mathrm{6}\right\}\Rightarrow\mathrm{n}=\mathrm{3k},\:\mathrm{k}\geqslant\mathrm{1} \\ $$$$\mathrm{a}=\mathrm{9}\Rightarrow\mathrm{n}=\mathrm{k}\geqslant\mathrm{2} \\ $$$$\mathrm{2}\:\mathrm{digits}:\:\left(\mathrm{99}\right) \\ $$$$\mathrm{3}\:\mathrm{digits}:\:\left(\mathrm{333},\:\mathrm{666},\:\mathrm{999}\right) \\ $$$$\mathrm{4}\:\mathrm{digits}:\:\left(\mathrm{9999}\right) \\ $$$$\mathrm{5}\:\mathrm{digits}:\:\left(\mathrm{99999}\right) \\ $$$$\mathrm{6}\:\mathrm{digits}:\:\left(\mathrm{333333},\:\mathrm{666666},\:\mathrm{999999}\right) \\ $$$$\left[...\right] \\ $$$$\mathrm{9}\:\mathrm{digits}:\:\left(\mathrm{11}...\mathrm{1},\:\mathrm{22}...\mathrm{2},\:\mathrm{33}...\mathrm{3},\:...,\:\mathrm{99}..\mathrm{9}\right) \\ $$$$\mathrm{2}\:\mathrm{digits}\:\mathrm{to}\:\mathrm{9}\:\mathrm{digits}:\:\mathrm{5}+\mathrm{3}.\mathrm{2}+\mathrm{9}=\mathrm{20}\:\mathrm{cases} \\ $$$$\mathrm{10}\:\mathrm{digits}\:\mathrm{to}\:\mathrm{19}:\:\mathrm{7}+\mathrm{3}.\mathrm{2}+\mathrm{9}=\mathrm{22}\:\mathrm{cases} \\ $$$$\mathrm{from}\:\mathrm{1}\:\mathrm{to}\:\mathrm{x}\:\mathrm{we}\:\mathrm{have} \\ $$$$\mathrm{x}−\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor\mathrm{numbers}\:\mathrm{that}\:\mathrm{are}\:\mathrm{coprime}\:\mathrm{with}\:\mathrm{3} \\ $$$$\left(\mathrm{because}\:\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor\:\mathrm{is}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{multiples}\:\mathrm{of}\:\mathrm{3},\:\mathrm{from}\:\mathrm{1}\:\mathrm{to}\:\mathrm{x}\right) \\ $$$$\mathrm{from}\:\mathrm{2}\:\mathrm{to}\:\mathrm{x}\:\mathrm{we}\:\mathrm{have} \\ $$$$\left(\mathrm{x}−\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor−\mathrm{1}\right)+\mathrm{3}\left(\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor−\lfloor\frac{\mathrm{x}}{\mathrm{9}}\rfloor\right)+\mathrm{9}\lfloor\frac{\mathrm{x}}{\mathrm{9}}\rfloor \\ $$$$\mathrm{x}−\mathrm{1}+\mathrm{2}\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor+\mathrm{6}\lfloor\frac{\mathrm{x}}{\mathrm{9}}\rfloor\mathrm{numbers}\:\mathrm{that}\:\mathrm{are}\:\mathrm{divisible} \\ $$$$\mathrm{by}\:\mathrm{9}\:\mathrm{and}\:\mathrm{have}\:\mathrm{the}\:\mathrm{same}\:\mathrm{digits} \\ $$$$\mathrm{from}\:\mathrm{2}\:\mathrm{digits}\:\mathrm{to}\:\mathrm{n}\:\mathrm{digits}\:\mathrm{we}\:\mathrm{have} \\ $$$$\mathrm{n}−\mathrm{1}+\mathrm{2}\lfloor\frac{\mathrm{n}}{\mathrm{3}}\rfloor+\mathrm{6}\lfloor\frac{\mathrm{n}}{\mathrm{9}}\rfloor\:\mathrm{numbers}\:\mathrm{that}\:\mathrm{have} \\ $$$$\mathrm{the}\:\mathrm{same}\:\mathrm{digits}\:\mathrm{and}\:\mathrm{are}\:\mathrm{divisible}\:\mathrm{by}\:\mathrm{9} \\ $$$$ \\ $$$$\mathrm{Ans}: \\ $$$$\frac{\mathrm{10}^{\mathrm{n}} −\mathrm{1}}{\mathrm{9}}−\left(\mathrm{n}−\mathrm{1}+\mathrm{2}\lfloor\frac{\mathrm{n}}{\mathrm{3}}\rfloor+\mathrm{6}\lfloor\frac{\mathrm{n}}{\mathrm{9}}\rfloor\right) \\ $$$$ \\ $$