Мозжевилов Максим Александрович Разработка модулей генерации заданий и решений по теме «Основы теории чисел» диплом

Вид материала

Диплом

Подобный материал:

• Майзаков Максим Александрович Разработка модулей автоматической генерации заданий, 799.4kb.
• Дидин Максим Александрович Переславль-Залесский Гимназия 7 7 7 7 7 7 7 7 56 диплом, 189.17kb.
• Дидин Максим Александрович Переславль-Залесский Гимназия 10 8 3 10 10 15 8 64 диплом, 103.28kb.
• hulan ucoz, 73.13kb.
• Ок. 365 300 до н э. древнегреческий математик. Работал в Александрии, 72.88kb.
• Разработка урока по теме: «Развитие мышления через постановку проблемно творческих, 84.71kb.
• Курс III семестр- VI всего аудиторных часов 69 ч.,, 47.01kb.
• Отчет о выполеннии ниокр по теме Разработка унифицированных функциональных модулей, 219.08kb.
• Рабочей программы учебной дисциплины «основы теории вероятностей и математической статистики», 46.75kb.
• Рейтинг-план освоения дисциплины «Теория принятия решений» Недели, 83.54kb.

2.7. Сколько нечетных чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

Сколько нечетных чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 3400, b = 14000, p = 0,75;

б) a = 1500, b = 32000, p = 0,85;

в) a = 2900, b = 36000, p = 0,93;

г) a = 850, b = 47000, p = 0,91;

д) a = 1300, b = 44000, p = 0,997.

Сколько нечетных чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 3400, b = 14000, p = 0,75.

Решение:

Примерное количество простых чисел в диапазоне от 3400 до 14000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1048,33.

Количество чисел, больших 3400 и меньших 14000, есть 10600. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 5300. Вероятность случайного выбора простого числа есть

P = 1048,33 / 5300 ≈ 0,2.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 6,29 => n=7.

Ответ: требуется 7 испытаний.

б) a = 1500, b = 32000, p = 0,85.

Решение:

Примерное количество простых чисел в диапазоне от 1500 до 32000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2879,68.

Количество чисел, больших 1500 и меньших 32000, есть 30500. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 15250. Вероятность случайного выбора простого числа есть

P = 2879,68 / 15250 ≈ 0,19.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 9,07 => n=10.

Ответ: требуется 10 испытаний.

в) a = 2900, b = 36000, p = 0,93.

Решение:

Примерное количество простых чисел в диапазоне от 2900 до 36000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3067,67.

Количество чисел, больших 2900 и меньших 36000, есть 33100. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 16550. Вероятность случайного выбора простого числа есть

P = 3067,67 / 16550 ≈ 0,19.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 12,97 => n=13.

Ответ: требуется 13 испытаний.

г) a = 850, b = 47000, p = 0,91.

Решение:

Примерное количество простых чисел в диапазоне от 850 до 47000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 4242,87.

Количество чисел, больших 850 и меньших 47000, есть 46150. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 23075. Вероятность случайного выбора простого числа есть

P = 4242,87 / 23075 ≈ 0,18.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 11,85 => n=12.

Ответ: требуется 12 испытаний.

д) a = 1300, b = 44000, p = 0,997.

Решение:

Примерное количество простых чисел в диапазоне от 1300 до 44000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3933,94.

Количество чисел, больших 1300 и меньших 44000, есть 42700. Доля нечетных чисел есть 1/2. Тогда всего перебирается чисел 21350. Вероятность случайного выбора простого числа есть

P = 3933,94 / 21350 ≈ 0,18.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 28,52 => n=29.

Ответ: требуется 29 испытаний.

2.8. Сколько не кратных 3-м чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

Сколько не кратных 3-м чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 2800, b = 31000, p = 0,97;

б) a = 2800, b = 24000, p = 0,85;

в) a = 4800, b = 39000, p = 0,7;

г) a = 2900, b = 20000, p = 0,85;

д) a = 3100, b = 27000, p = 0,999.

Сколько не кратных 3-м чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 2800, b = 31000, p = 0,97.

Решение:

Примерное количество простых чисел в диапазоне от 2800 до 31000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2644,8.

Количество чисел, больших 2800 и меньших 31000, есть 28200. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 18800. Вероятность случайного выбора простого числа есть

P = 2644,8 / 18800 ≈ 0,14.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 23,13 => n=24.

Ответ: требуется 24 испытания.

б) a = 2800, b = 24000, p = 0,85.

Решение:

Примерное количество простых чисел в диапазоне от 2800 до 24000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2026,82.

Количество чисел, больших 2800 и меньших 24000, есть 21200. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 14133,33. Вероятность случайного выбора простого числа есть

P = 2026,82 / 14133,33 ≈ 0,14.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 12,26 => n=13.

Ответ: требуется 13 испытаний.

в) a = 4800, b = 39000, p = 0,7.

Решение:

Примерное количество простых чисел в диапазоне от 4800 до 39000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3122,95.

Количество чисел, больших 4800 и меньших 39000, есть 34200. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 22800. Вероятность случайного выбора простого числа есть

P = 3122,95 / 22800 ≈ 0,14.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 8,17 => n=9.

Ответ: требуется 9 испытаний.

г) a = 2900, b = 20000, p = 0,85.

Решение:

Примерное количество простых чисел в диапазоне от 2900 до 20000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1655,74.

Количество чисел, больших 2900 и меньших 20000, есть 17100. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 11400. Вероятность случайного выбора простого числа есть

P = 1655,74 / 11400 ≈ 0,15.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 12,09 => n=13.

Ответ: требуется 13 испытаний.

д) a = 3100, b = 27000, p = 0,999.

Решение:

Примерное количество простых чисел в диапазоне от 3100 до 27000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2260,51.

Количество чисел, больших 3100 и меньших 27000, есть 23900. Доля не кратных 3-м чисел есть 2/3. Тогда всего перебирается чисел 15933,33. Вероятность случайного выбора простого числа есть

P = 2260,51 / 15933,33 ≈ 0,14.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 45,15 => n=46.

Ответ: требуется 46 испытаний.

2.9. Сколько нечетных и не кратных 3-м чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

Сколько нечетных и не кратных 3-м чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 3200, b = 26000, p = 0,5;

б) a = 2800, b = 22000, p = 0,7;

в) a = 4900, b = 33000, p = 0,99;

г) a = 2300, b = 43000, p = 0,97;

д) a = 560, b = 36000, p = 0,7.

Сколько нечетных и не кратных 3-м чисел из диапазона от a до b следует перебрать, чтобы с вероятностью не менее p получить хотя бы одно простое? (перебранные числа не исключаются из множества перебора).

а) a = 3200, b = 26000, p = 0,5.

Решение:

Примерное количество простых чисел в диапазоне от 3200 до 26000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2161,1.

Количество чисел, больших 3200 и меньших 26000, есть 22800. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 7600. Вероятность случайного выбора простого числа есть

P = 2161,1 / 7600 ≈ 0,28.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 2,07 => n=3.

Ответ: требуется 3 испытания.

б) a = 2800, b = 22000, p = 0,7.

Решение:

Примерное количество простых чисел в диапазоне от 2800 до 22000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 1847,5.

Количество чисел, больших 2800 и меньших 22000, есть 19200. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 6400. Вероятность случайного выбора простого числа есть

P = 1847,5 / 6400 ≈ 0,29.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 3,53 => n=4.

Ответ: требуется 4 испытания.

в) a = 4900, b = 33000, p = 0,99.

Решение:

Примерное количество простых чисел в диапазоне от 4900 до 33000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 2595,1.

Количество чисел, больших 4900 и меньших 33000, есть 28100. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 9366,67. Вероятность случайного выбора простого числа есть

P = 2595,1 / 9366,67 ≈ 0,28.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 14,19 => n=15.

Ответ: требуется 15 испытаний.

г) a = 2300, b = 43000, p = 0,97.

Решение:

Примерное количество простых чисел в диапазоне от 2300 до 43000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3733,25.

Количество чисел, больших 2300 и меньших 43000, есть 40700. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 13566,67. Вероятность случайного выбора простого числа есть

P = 3733,25 / 13566,67 ≈ 0,28.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 10,9 => n=11.

Ответ: требуется 11 испытаний.

д) a = 560, b = 36000, p = 0,7.

Решение:

Примерное количество простых чисел в диапазоне от 560 до 36000 есть

K = π(b) - π(a) = b/ln(b) - a/ln(a) ≈ 3342,93.

Количество чисел, больших 560 и меньших 36000, есть 35440. Доля нечетных и не кратных 3-м чисел есть 1/3. Тогда всего перебирается чисел 11813,33. Вероятность случайного выбора простого числа есть

P = 3342,93 / 11813,33 ≈ 0,28.

Вероятность достичь успеха хотя бы в одном из n испытаний есть 1-(1-P)ⁿ ≥ p. Тогда n ≥ log_(1-P)(1-p), т.е n ≥ ln(1-p) / ln(1-P) ≥ 3,62 => n=4.

Ответ: требуется 4 испытания.

3. Модуль EILER.

3.1. Вычислить функцию φ(n).

Вычислить функцию φ(n).

а) n=224939;

б) n=5929;

в) n=27;

г) n=143286143;

д) n=343.

Вычислить функцию φ(n).

а) n=224939.

Решение:

n=11³∙13².

φ(n)=11²∙10∙13∙12 = 188760.

Ответ: φ(224939) = 188760.

б) n=5929.

Решение:

n=7²∙11².

φ(n)=7∙6∙11∙10 = 4620.

Ответ: φ(5929) = 4620.

в) n=27.

Решение:

n=3³.

φ(n)=3²∙2 = 18.

Ответ: φ(27) = 18.

г) n=143286143.

Решение:

n=7²∙11³∙13³.

φ(n)=7∙6∙11²∙10∙13²∙12 = 103062960.

Ответ: φ(143286143) = 103062960.

д) n=343.

Решение:

n=7³.

φ(n)=7²∙6 = 294.

Ответ: φ(343) = 294.

Вычислить функцию φ(n).

а) n=290605;

б) n=226941;

в) n=5681;

г) n=169;

д) n=1366365.


Вычислить функцию φ(n).

а) n=290605.

Решение:

n=5∙7∙19²∙23.

φ(n)=4∙6∙19∙18∙22 = 180576.

Ответ: φ(290605) = 180576.

б) n=226941.

Решение:

n=3∙11∙13∙23².

φ(n)=2∙10∙12∙23∙22 = 121440.

Ответ: φ(226941) = 121440.

в) n=5681.

Решение:

n=13∙19∙23.

φ(n)=12∙18∙22 = 4752.

Ответ: φ(5681) = 4752.

г) n=169.

Решение:

n=13².

φ(n)=13∙12 = 156.

Ответ: φ(169) = 156.

д) n=1366365.

Решение:

n=3∙5∙7²∙11∙13².

φ(n)=2∙4∙7∙6∙10∙13∙12 = 524160.

Ответ: φ(1366365) = 524160.

Вычислить функцию φ(n).

а) n=133;

б) n=1031849;

в) n=16546530;

г) n=5277907635;

д) n=2211105.

Вычислить функцию φ(n).

а) n=133.

Решение:

n=7∙19.

φ(n)=6∙18 = 108.

Ответ: φ(133) = 108.

б) n=1031849.

Решение:

n=7∙13∙17∙23∙29.

φ(n)=6∙12∙16∙22∙28 = 709632.

Ответ: φ(1031849) = 709632.

в) n=16546530.

Решение:

n=2∙3∙5∙7∙11∙13∙19∙29.

φ(n)=1∙2∙4∙6∙10∙12∙18∙28 = 2903040.

Ответ: φ(16546530) = 2903040.

г) n=5277907635.

Решение:

n=3∙5∙7∙11∙13∙17∙23∙29∙31.

φ(n)=2∙4∙6∙10∙12∙16∙22∙28∙30 = 1703116800.

Ответ: φ(5277907635) = 1703116800.

д) n=2211105.

Решение:

n=3∙5∙13∙17∙23∙29.

φ(n)=2∙4∙12∙16∙22∙28 = 946176.

Ответ: φ(2211105) = 946176.