Числа кратные 7

[TGX]

Сколько существует чисел от 10000 до 20000, которые не делятся ни на 5, ни на 7?

Комбинаторикой можно подсчитать, сколько будет не кратных 5-ти... а что делать с 7?

[venco]

Надо считать не комбинаторикой, а арифметикой.

[TGX]

спасибо, а можно какие-нибудь советы конкретней?

[Maslov]

Посчитайте количество чисел, делящихся на 5, затем количество чисел, делящихся на 7, затем по формуле включений-исключений количество чисел делящися на 5 или на 7.

[venco]

TGX в сообщении #352573 писал(а):

спасибо, а можно какие-нибудь советы конкретней?

На 5 делится каждое пятое число. Т.е. какая доля всех чисел подряд делится на 5?

[TGX]

в том, то и дело, что каждое 5-ое на пять, а каждое 7-ое на семь... но ведь эти множества могут пересекаться, не так ли... а в лоб посчитать числа делящиеся на 7 трудновато, т.к. признак делимости на 7 не просто считается.... в отличие от деления на 5...

-- Ср сен 15, 2010 01:11:58 --

вот нашёл соседний топик: http://dxdy.ru/topic21640.html

наверно можно поступить аналогичным образом...

определить для кратных семи n(min) и n(max) - потом посмотреть, какие из них кратны ещё пяти... и аналогично для кратных пяти... затем всё скомбинировать...

как вы считаете?

[Someone]

TGX в сообщении #352598 писал(а):

в лоб посчитать числа делящиеся на 7 трудновато, т.к. признак делимости на 7 не просто считается

Зачем нужен признак делимости на $7$?
Например, сколько чисел от $100$ до $200$ делятся на $11$? Наименьшее такое число - $110$, наибольшее - $198$, поэтому делящихся на $11$ будет $\frac{198-110}{11}+1=9$ штук.
Откуда взялось $110$? Делим $100$ на $11$, получаем $9$ и $1$ в остатке. Значит, наибольшее число $\leqslant 100$, делящееся на $11$, равно $9\cdot 11=99$, а так как нам нужно наименьшее, которое $\geqslant 100$, прибавляем $11$ и получаем число $99+11=110$.

[Sasha2]

Ну, TGX, давайте так:
Вот к примеру возьмем число 12.
Сколько чисел от 1 до 12 делятся на 5?
Разделим 12 на 5. Получим 2 с остатком. Остаток отбросим, получим 2.
Итак, всего целых чисел от 1 до 12, которые делятся на 5, два. Вы можете и простым перебором установить это.
Но формула общая таким образом найдена. Теперь уже нетрдно вычислить сколько чисел делятся на 5 от, скажем 10000 до 20000.
Точно таким же образом Вы действуете и с семеркой.
Итак найдено общее число чисел, делящихся на 5 и на 7. Но некоторые из этих чисел встречаются два раза, потому как они делятся и на 5 и на 7. Эти числа нужно исключить. В том смысле, что вычесть их число из суммы чисел, делящихся на 5 или на 7. Остается сообразить, что все эти числа делятся на 35.

И теперь, резюмируя все сказанное выше, очень просто записываем окончательный ответ
$([\frac{20000}{5}]-[\frac{10000}{5}])+([\frac{20000}{7}]-[\frac{10000}{7}])-([\frac{20000}{35}]-[\frac{10000}{35}])$.

Это и есть формула включений- исключений для Вашего случая, то что Вам говорил уважаемый Maslov.
Здесь квадратные скобки обозначают целую часть числа.

[Cash]

Sasha2, вы слишком поверхностно подошли к задаче, не учитывая концы отрезков.
Я думаю, что ваша формула неверна.
Например, количество чисел от 10 до 20, делящихся на 5, по вашей формуле равно
$([\frac{20}{5}]-[\frac{10}{5}]) = 2$, но их все-таки немного больше

[Алексей К.]

$5\times 7 = 35 \:?$
\begin{picture}(100,100) \put(0,0){\framebox(100,100){}} \put(0,0){\circle*{2}} \put(35,50){\circle{40}} \put(60,50){\circle{30}} \put(30,45){5} \put(60,50){7} \put(47,46){\tiny35} \end{picture}

[Cash]

добавим чуть-чуть строгости.
Сколько чисел от $1$ до $N$ делится на $p$?
Безусловно, $[\frac{N}{p}]$.
Теперь можно перейти к задаче о количестве чисел делящихся на $p$ на отрезке $[N_1;N_2]$
Количество чисел, от $1$ до $N_2$, делящихся на $p$, как мы выяснили равно $[\frac{N_2}{p}]$.
И нам необходимо вычесть количество чисел от $1$ до $N_1-1$, делящихся на $p$.
Итого получаем формулу
$([\frac{N_2}{p}]-[\frac{N_1-1}{p}]) $

Sasha2, еще раз просмотрел ваше сообщение и понял, что ход ваших рассуждений аналогичен. Возможно просто в спешке вы выкинули начало отрезка. Извините, если был слишком придирчив

[Sasha2]

Да все верно, с концом это я поторопился.

[TGX]

огромное спасибо за подробное разъяснение... когда давал ссылку на тему, в принципе там этот подход и оговаривался...