How-many-numbers-in-the-range-1-10-n-1-are-divisible-by-9-digit-repetitions-are-not-allowed-

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 .

Commented by mr W last updated on 15/Oct/20

w i t h o u t r e p e t i t i o n m e a n s m a x .

10 d i g i t s a r e a l l o w e d, i . e . n ⩽ 10 .

10 d i g i t n u m b e r s :

0 + 1 + 2 + . . + 9 = 45 ✓

\Rightarrow \frac{9}{10} \times 10! = 9 \times 9!

9 d i g i t n u m b e r s :

1 + 2 + . . + 9 = 45 ✓

\Rightarrow 9!

0 + 1 + 2 + . . + 8 = 36 ✓

\Rightarrow \frac{8}{9} \times 9! = 8 \times 8!

\Rightarrow 9! + 8 \times 8! = 17 \times 8!

8 d i g i t n u m b e r s :

w i t h o u t 0 + 9 \Rightarrow 8!

w i t h o u t 1 + 8, 2 + 7, 3 + 6, 4 + 5 \Rightarrow 4 \times \frac{7}{8} \times 8! = 4 \times 7 \times 7!

\Rightarrow 8! + 4 \times 7 \times 7! = 36 \times 7!

7 d i g i t n u m b e r s :

w i t h o u t 0 + 1 + 8, 0 + 2 + 7, 0 + 3 + 6, 0 + 4 + 5 \Rightarrow 4 \times 7!

w i t h o u t 1 + 8 + 9, 2 + 7 + 9, 3 + 6 + 9, 4 + 5 + 9 \Rightarrow 4 \times \frac{6}{7} \times 7! = 4 \times 6 \times 6!

w i t h o u t 1 + 2 + 6, 1 + 3 + 5 \Rightarrow 2 \times \frac{6}{7} \times 7! = 2 \times 6 \times 6!

w i t h o u t 2 + 3 + 4 \Rightarrow \frac{6}{7} \times 7! = 6 \times 6!

\Rightarrow (4 \times 7 + 4 \times 6 + 2 \times 6 + 6) 6! = 10 \times 7!

6 d i g i t n u m b e r s :

w i t h o u t 0 + 1 + 2 + 6, 0 + 1 + 3 + 5, 0 + 2 + 3 + 4 \Rightarrow 3 \times 6!

w i t h o u t 1 + 2 + 6 + 8, 1 + 3 + 5 + 9, 2 + 3 + 4 + 9 \Rightarrow 3 \times \frac{5}{6} \times 6! = 3 \times 5 \times 5!

\Rightarrow 3 (6 + 5) 5! = 33 \times 5!

5 d i g i t n u m b e r s :

9 + 8 + 7 + 2 + 1

9 + 8 + 6 + 3 + 1

9 + 8 + 5 + 4 + 1

9 + 8 + 5 + 3 + 2

9 + 7 + 6 + 4 + 1

9 + 7 + 6 + 3 + 2

9 + 7 + 5 + 4 + 2

9 + 6 + 5 + 4 + 3

\dots \dots

Commented by prakash jain last updated on 15/Oct/20

Thanks sir .

It looks listing is the only possible way .

I thought I had seen a closed forum

expression somewhere but was not

able to derive .

Answered by floor(10²Eta[1]) last updated on 24/Dec/20

from 1 to 10^{n} - 1 we have \frac{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 \dots a] (n digits)

a . n \equiv 0 (\mod 9), a \in [1, 9] \land n ⩾ 2

a \in {1, 2, 4, 5, 7, 8} \Rightarrow n = 9 k, k ⩾ 1

a \in {3, 6} \Rightarrow n = 3 k, k ⩾ 1

a = 9 \Rightarrow n = k ⩾ 2

2 digits : (99)

3 digits : (333, 666, 999)

4 digits : (9999)

5 digits : (99999)

6 digits : (333333, 666666, 999999)

[\dots]

9 digits : (11 \dots 1, 22 \dots 2, 33 \dots 3, \dots, 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 - ⌊ \frac{x}{3} ⌋ numbers that are coprime with 3

(because ⌊ \frac{x}{3} ⌋ is the number of multiples of 3, from 1 to x)

from 2 to x we have

(x - ⌊ \frac{x}{3} ⌋ - 1) + 3 (⌊ \frac{x}{3} ⌋ - ⌊ \frac{x}{9} ⌋) + 9 ⌊ \frac{x}{9} ⌋

x - 1 + 2 ⌊ \frac{x}{3} ⌋ + 6 ⌊ \frac{x}{9} ⌋ numbers that are divisible

by 9 and have the same digits

from 2 digits to n digits we have

n - 1 + 2 ⌊ \frac{n}{3} ⌋ + 6 ⌊ \frac{n}{9} ⌋ numbers that have

the same digits and are divisible by 9

Ans :

\frac{10^{n} - 1}{9} - (n - 1 + 2 ⌊ \frac{n}{3} ⌋ + 6 ⌊ \frac{n}{9} ⌋)