Krys 2 20 января, 2016 Опубликовано 20 января, 2016 · Жалоба Здравствуйте. Вопросик в качестве разминки для мозгов: Как математически доказать, что число 2^x может быть поделено нацело только числом вида 2^y, где y<=x, и никаким другим числом не может (или наоборот может и ещё есть какие-то числа)? Т.е. например число 2 в 12 степени это 4096 нацело делится двойкой в любой степени до 12 и ничем другим. Т.е. для меня важно доказать, что нет ничего другого, кроме 2^y Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 18 20 января, 2016 Опубликовано 20 января, 2016 · Жалоба Как математически доказать, что число 2^x может быть поделено нацело только числом вида 2^y, где y<=x, и никаким другим числом не может (или наоборот может и ещё есть какие-то числа)? Это следует из Основной теоремы арифметики: Каждое натуральное число n > 1 можно представить в виде n = p1 *...* pk, где p1 ,.., pk — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 20 января, 2016 Опубликовано 20 января, 2016 · Жалоба Поскольку 2^y = 2 * 2 * 2 ... очевидно, что никаких других сомножителей, кроме степени двойки, у числа нет. И 2 уже ни на что не раскладывается. Аналогичные свойства будет иметь x ^ y, если x - простое число. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Eddy_Em 1 20 января, 2016 Опубликовано 20 января, 2016 (изменено) · Жалоба Во-во, присоединяюсь к предыдущему оратору. Просто разложим: 2^a = 2^{m+n}, где a = m+n по определению. Таким образом, множителями 2^a яляются два числа: 2^m и 2^n, где m≤a и n≤a. ЧТД. А вот для непростых чисел это уже не так. Непростое число x есть произведение N чисел: Пa_i Т.е. x^y = (Пa_i)^y = Пa_i^y = Пa_i^{m+n} Т.о. здесь уже даже при разложении на 2 множителя получаем кучу вариантов. Изменено 20 января, 2016 пользователем Эдди Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexeyW 0 20 января, 2016 Опубликовано 20 января, 2016 · Жалоба Задача для разнообразия: перемножаем числа от 1 до 99, сколько нулей будет в конце результата? А можно еще попробовать в общем виде - от 1 до N. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iiv 18 20 января, 2016 Опубликовано 20 января, 2016 · Жалоба ну раз ту все задачки выкладывают, можно я на злобу дня (года) выложу: как доказать, что число 1010...10101, в котором 2016 нулей не является простым? Как подсказку, озвучу один из делителей 80681 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Krys 2 21 января, 2016 Опубликовано 21 января, 2016 · Жалоба Спасибо откликнувшимся. Мне это не просто для развлекухи надо было, а для математического обоснования при составлении одного документика Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alexvu 5 25 января, 2016 Опубликовано 25 января, 2016 · Жалоба ну раз ту все задачки выкладывают, можно я на злобу дня (года) выложу: как доказать, что число 1010...10101, в котором 2016 нулей не является простым? Как подсказку, озвучу один из делителей 80681 А должно быть красивое решение или Вы знаете только метод подбора на компе? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iiv 18 25 января, 2016 Опубликовано 25 января, 2016 · Жалоба А должно быть красивое решение или Вы знаете только метод подбора на компе? я знаю три решения: 1. красивое, 2. требующее знания очень специфических методов (считаю его не красивым, более того, на раз даже его не напишу, надо в книжки заглядывать), 3. ну и перебор, конечно. возможно есть еще какие-то другие решения :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RCray 0 26 января, 2016 Опубликовано 26 января, 2016 · Жалоба ну раз ту все задачки выкладывают, можно я на злобу дня (года) выложу: как доказать, что число 1010...10101, в котором 2016 нулей не является простым? <...> 1. B соответствии с формулой геометрической прогрессии само число "1010...10101, в котором 2016 нулей" = (2^4032-1)/3. Но это нам ничего не дает. 2. "1010...10101, в котором 2016 нулей" = 0x5555..555 (в котором 1008 пятерок), то есть делится на 5 = 0x1111..111 (в котором 1008 единиц) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ViKo 1 26 января, 2016 Опубликовано 26 января, 2016 · Жалоба Постойте, разве число 1010... - записано в двоичной системе? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
RCray 0 26 января, 2016 Опубликовано 26 января, 2016 · Жалоба тогда "ой" Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
jks 0 26 января, 2016 Опубликовано 26 января, 2016 · Жалоба ну раз ту все задачки выкладывают, можно я на злобу дня (года) выложу: как доказать, что число 1010...10101, в котором 2016 нулей не является простым? Как подсказку, озвучу один из делителей 80681 Не силен я в математике но как-то так думаю. Число 101010....10101<4033> содержит 2016*2 + 1 дес. цифр. Если умножить 101010....10101<4033> на 11 , то получим число с одними единицами (репьюнит Rn(N=4034)). 101010....10101<4033> * 11 = 11111...11<4034> = RN(4034) Так как N - четно его можно представить в виде произведения: RN(4034) = 111...111<2017> * 100...001<2018> число 100...001<2018> делится на 11 т.к. содержит 2 единицы и четное число групп из двух цифр. 100...001<2018> mod(11) == 0, 10000...0001<2018> : 11 = 909090...9091<2016> т.о. 101010....10101<4033> = 111...11<2017>*909090....91<2016>. т.е. 101010....10101<4033> содержит по крайней мере два делителя 111...111<2017> и 9090...9091<2016>. один из делителей 9090...9091<2016> равен 80681. другие делители можно найти после факторизации (или в интернете). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iiv 18 26 января, 2016 Опубликовано 26 января, 2016 · Жалоба 2. "1010...10101, в котором 2016 нулей" = 0x5555..555 (в котором 1008 пятерок), то есть делится на 5 = 0x1111..111 (в котором 1008 единиц) не 0x5555..555 а 0x15555..555 хотя задача изначально в десятичной системе сформулирована, в двоичной системе не все так просто, хотя число тоже не простое, для тех, кому хочется и в двоичной системе помучиться, дам подсказку на делитель: 2936753 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
regtiha 0 8 апреля, 2016 Опубликовано 8 апреля, 2016 · Жалоба Число "1010...10101, в котором 2016 нулей" = 10^0 + 10^2 + 10^4 + ... + 10^2016, что как сказал RCray действительно является геометрической прогрессией и ее сумма равна 10^0*(100^2017 - 1)/(100 -1). Как видно число делится на на 99, а также на 3, 33, 11, 9. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться