Информативный заголовок: задачка повышенного уровня сложности
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Информативный заголовок: задачка повышенного уровня сложности - 2010-04-19 23:36:06.333333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
для гурманов. найти не менее пяти чисел, удовлетворяющих равенству 2^n % n == 3
здесь '^' - операция возведения в степень, '%' - операция получения остатка от деления, '==' - проверка на равенство. язык реализации произвольный, железо для расчётов произвольное, первому решившему - волшебный бублик
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-20 12:41:51.466666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Есть основания полагать, что среди первого миллиона натуральных чисел корней уравнения нету. Запрячь что ли видеокарту и проверить ещё 99 миллионов, или может мозги включить? Вот ведь в чём вопрос… Но да ладно, на этот вопрос я сам ответ могу найти, но меня смущает фраза про произвольное железо. Значит ли это, что существует алгоритм, который сосчитает на любом железе, даже самом галимом? Или надо понимать ровно наоборот, как предложение запрячь всё доступное железо, чтобы оно высчитывало бы корни пару недель?
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-20 16:10:31.470000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: rgo
меня смущает фраза про произвольное железо
здесь были любители использования CUDA, насколько я помню
quote:
ORIGINAL: rgo
Значит ли это, что существует алгоритм, который сосчитает на любом железе, даже самом галимом? Или надо понимать ровно наоборот, как предложение запрячь всё доступное железо, чтобы оно высчитывало бы корни пару недель?
вообще говоря, вариант про включение мозга был наиболее существенным :)
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-20 16:45:39.026666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ну и задачки ты подкинул :). Может через недельку займусь, поищу закономерности между степенью числа и остатком от деления.
Пока мой мозг зохаван очередным велосипедом на WinAPI, для локализации тулбаров =\. Работу с ресурсами в винде явно индусы писали.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-20 17:11:40.680000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
ORIGINAL: Denaturat
вообще говоря, вариант про включение мозга был наиболее существенным :)
Ну этот вывод сразу напрашивался, судя по тому, что задача повышенной сложности вариант с перебором мне кажется отпадает.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-22 23:53:10.230000
|
|
|
tеstеr
Сообщений: 377
Оценки: -46
Присоединился: 2008-02-08 17:56:40.563333
|
del
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-23 16:05:38.843333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
2^n mod n = 3
3 = 2^n mod n
3 = 2^n - q * n, где q - некое целое число
Дальше надо каким-то боком выразить n через q и посмотреть, в каких случаях и n, и q одновременно могут принимать целые значения. Это так, мысли вслух и пища для размышления. Если вечером будет время, попробую из этой пищи приготовить нормальный ужин.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-23 18:26:05.340000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
2^n mod n = 3
3 = 2^n mod n
3 = 2^n * k + n, где k - некое целое число
ЭЭЭ. Не надо нас путать.
Деление с остатком m на n, это решение уравнения m = nq + r в целых числах (0 < r < n). Подставляя сюда условие, получаем: 2^n = q*n + 3;
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-23 18:28:20.690000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
ЭЭЭ. Не надо нас путать.
Деление с остатком m на n, это решение уравнения m = nq + r в целых числах (0 < r < n). Подставляя сюда условие, получаем: 2^n = q*n + 3;
Дада, как раз исправил, не успел перезагрузить страницу :)
Ну суть, в общем-то, та же.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-23 23:22:21.606666
|
|
|
tеstеr
Сообщений: 377
Оценки: -46
Присоединился: 2008-02-08 17:56:40.563333
|
quote:
ORIGINAL: rgo
2^n = q*n + 3 2^n - чётное
=> q*n+3 - чётное
=> q*n - нечётное
=> q - нечётное и n - нечетное
=> q=2x+1; n=2y+1
…
если x-чётное, то y-нечётное
если x-нечётное, то y-чётное
Выразить x через y можно, но в формуле будет 2^(2y), что нереально вычислять, при больших y.
Выразить y через x не вышло.
Думаю, что решения нет.
Вчера решил что пришел к противоречию и тем самым доказал, что решения нет, но оказалось ошибся.
Нет противеречий.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-24 01:10:20.260000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Деление с остатком m на n, это решение уравнения m = nq + r в целых числах (0 < r < n). Подставляя сюда условие, получаем: 2^n = q*n + 3;
А теперь, внимание, фокус.
2^n mod n = 3 (1)
2^n = q*n + 3 | 0 < r < n (2)
При условии, что n и r - целые числа, эти уровнения должны быть эквивалентны и иметь одинаковые корни.
Решаем (2) графическим методом, получаем корни:
q = 13/4
n = 4
Подставляем n = 4 в (1):
2^4 mod 4 = 16 mod 4 = 0 =/= 3. (??)
Следовательно, переход от оператора mod к обычному уравнению и введение параметра q было нелегально. Вопрос только в том, почему.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-24 01:28:28.793333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Хотя нет, q можно ввести, но только наложив ограничение, что оно принадлежит целым числам. Соответственно, q = 13/4 и n = 4 не являются корнями уравнения.
Возвращаемся к уравнению
2^n = qn + 3
и выражаем его двумя функциями:
y = 2^n – степенная функция
y = qn + 3 – линейная функция, где q - тангенс угла между прямой осью абсцисс
При q = 1 получаем график:
Из него видно, что каков бы ни был параметр q, два графика пересекутся максимум 2 раза, при этом один раз в точке с координатой y меньше 3. То есть если у этого уравнения и есть корни, то всего 1, никак не 5.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-24 01:33:12.830000
|
|
|
Genco
Сообщений: 1662
Оценки: 90
Присоединился: 2007-12-16 23:11:22.003333
|
<del>
//Не успел. Можно теперь через численные мат.методы пробить чтоли? о_О как то даже не верится
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-24 07:36:00.963333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
Из него видно, что каков бы ни был параметр q, два графика пересекутся максимум 2 раза, при этом один раз в точке с координатой y меньше 3. То есть если у этого уравнения и есть корни, то всего 1, никак не 5.
Да. Если фиксировать q, то так и будет. Но уравнение мы решаем имея две неизвестные q и n. График соответственно должен содержать две поверхности:
f(n,q) = 2^n
f(n,q) = q*n + 3
Они пересекутся по какой-то офигительной кривой, которая концами своими упрётся в бесконечность. Нам надо найти 5 точек этой кривой, с целыми координатами q и n. Сколько таких точек будет, я не знаю.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-04-24 13:47:08.410000
|
|
|
LeVLeV
Сообщений: 1
Оценки: 0
Присоединился: 2010-04-24 13:43:05.520000
|
предел при n->беск q(n)/q(n-1) = 2
Долго думал как это применить но не придумал)
мож кому пригодится
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-02 13:41:18.626666
|
|
|
tеstеr
Сообщений: 377
Оценки: -46
Присоединился: 2008-02-08 17:56:40.563333
|
Среди первых 10 млн натуральных чисел решения не нашёл (причём считается быстро, с помощью powmod).
Ещё, доказал выше, что n- нечётное.
Ещё заметил, что если n-простое число, то отстаток(2^n, n) == 2. Данное равенство точно справедливо для первых 10 млн натуральных чисел. И наоборот, если отстаток(2^n, n) == 2, то n - простое число.
Таким образом, остаток(2^n, n) == 2 является хорошей проверкой числа n на простоту.
Собственно, я искал числа, удовлетворяющие условию "остаток от деления 2^n на n навен 3" следующим кодом.
for(i=1; i<=10000001; i+=2)
{
if(powmod(2,i,i)==3) printf("%d\n", i);
} и при этом, среди первых 10 000 000 + 1 нечётных чисел, решения не было.
Тест на простоту можно выполнять так:
if(powmod(2,i,i)==2)
Функция POWMOD есть в математических библиотеках, или её можно написать самому:
http://algolist.manual.ru/maths/count_fast/fast_exp.php
Диапазон изменения для целых чисел большой (для переменных х64):
[-9.22337203685e+18; 9.22337203685e+18]
Поэтому можно замахнуться подальше чем на 10 000 000, я уж не буду, так как решил что нет решения.
Плюс очень доволен тем, что заметил тест на простоту.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-02 18:18:45.766666
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
quote:
И наоборот, если отстаток(2^n, n) == 2, то n - простое число
проверь 341 или, например, 561
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 09:54:19.670000
|
|
|
=OutlaW=
Сообщений: 382
Оценки: 0
Присоединился: 2009-01-08 17:19:13.703333
|
Решение состоит в том, чтобы доказать что решений нет?
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 13:38:57.693333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: =OutlaW=
Решение состоит в том, чтобы доказать что решений нет?
вместо того, чтобы спрашивать,- взял бы и доказал
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 16:33:47.480000
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
Известные решения:
4700063497 - Guy (1994)
3468371109448915 - Alekseyev (2006)
8365386194032363 - Crump (2000)
10991007971508067 - Crump (2007)
63130707451134435989380140059866138830623361447484274774099906755 - Montgomery (1999)
Проверить можно в мэпле
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 16:42:23.853333
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
quote:
Известные решения:
Ну так неинтересно.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 17:04:14.323333
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
quote:
Ну так неинтересно.
да
но это я по поводу
quote:
Решение состоит в том, чтобы доказать что решений нет?
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 17:31:50.676666
|
|
|
=OutlaW=
Сообщений: 382
Оценки: 0
Присоединился: 2009-01-08 17:19:13.703333
|
quote:
ORIGINAL: _ruzmaz_
Известные решения:
4700063497 - Guy (1994)
3468371109448915 - Alekseyev (2006)
8365386194032363 - Crump (2000)
10991007971508067 - Crump (2007)
63130707451134435989380140059866138830623361447484274774099906755 - Montgomery (1999)
Проверить можно в мэпле
Хм, а я брутил до 100000000, и ничего не найдя, подумал что решений нет
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 18:37:39.250000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ну вот и кинул бы сюда свой брут.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-03 23:39:58.070000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _ruzmaz_
Известные решения
лично я бы за такое дисквалифицировал в особо тяжкой форме. с последующим расстрелом
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-04 12:39:32.706666
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
quote:
лично я бы за такое дисквалифицировал в особо тяжкой форме. с последующим расстрелом
Ну если вдруг реально обломал кого-то, то прошу прощения.
Однако, замечу, что ввиду того, что инфа, которую я запостил, гуглиться без проблем, поставленная задача может звучать действительно серьезно только если вместо "… найти не менее пяти чисел, удовлетворяющих равенству …" писать "… найти хотя бы одно число, отличное от ранее найденных, удовлетворяющее равенству …".
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-04 13:09:47.310000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
обломал. я задачу закрываю, мне дальше неинтересно; куда отправлять решения твоей задачи, ты и сам найдёшь
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-11 21:03:48.810000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Еще задачки будут?
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-12 18:06:14.736666
|
|
|
Zmaster
Сообщений: 930
Оценки: 0
Присоединился: 2007-02-09 19:02:43.500000
|
Denaturat, еще задачу, пожалуйста :)
P.S. _ruzmaz_, на будущее: это нечестно, тут интерес откопать решение самому, а не найти в гугле.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-12 19:17:10.100000
|
|
|
Родригес
Сообщений: 444
Оценки: 0
Присоединился: 2010-04-16 20:28:58.240000
|
Zmaster, совершенно верно. А если уж стало интересно и нашел в гугле решение -не надо портить людям удовольствие.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-13 19:15:34.123333
|
|
|
SmanxX1
Сообщений: 208
Оценки: 0
Присоединился: 2007-07-31 14:33:56.650000
|
quote:
я задачу закрываю, мне дальше неинтересно
А мне интересно. Может все же покажешь реализацию решения на яп?
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-13 19:43:56.863333
|
|
|
_ruzmaz_
Сообщений: 105
Оценки: 0
Присоединился: 2009-08-22 18:26:07.173333
|
Если задача позиционируется как "повышенного уровня сложности", то её решение не должно гуглится ни с первого, ни с тридцать первого запроса, тем более если за неё бублик полагается)
Задача в уточнённой мной формулировке вполне сложна и вполне для гурманов), и её решение принесёт и удовольствие и бублик, заинтересован ли в этом Denaturat или нет.
|
|
|
|
|
RE: Информативный заголовок: задачка повышенного уровня сложности - 2010-05-13 19:59:54.776666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Denaturat не говорил, что он нашёл шестое. Да и тут скорее интереснее то, справится ли кто-то с задачей и сможет привести методику, нежели просто наличие готового ответа.
|
|
|
|
|
|
