Задачка

здесь можно обсудить кошечек и ёжиков
Ответить
Аватара пользователя
uchebnik fiziki
Сообщения: 4265
Зарегистрирован: Пн авг 20, 2012 9:04 pm

Re: Задачка

Сообщение uchebnik fiziki » Пн апр 20, 2015 7:23 pm

Maryna писал(а):Из двух загаданных одно является простым числом, а второе - произведением двух простых
Есть гипотеза Лемойна (Lemoine's conjecture): любое нечётное -- сумма нечётного простого и чётного произведения двух простых

то есть загадано либо произведение хотя бы четырёх простых, либо сумма 174
Свобода, равенство, братство.

Или смерть.

Аватара пользователя
uchebnik fiziki
Сообщения: 4265
Зарегистрирован: Пн авг 20, 2012 9:04 pm

Re: Задачка

Сообщение uchebnik fiziki » Пн апр 20, 2015 9:02 pm

Дальше всё плохо:

1. Если произведение нечётное -- сумма 174 и оба числа нечётные. 174 = 77 (7*11) +97 = 91 (7*13) + 83 = 85 (5*17) +89 = 95 (5*19) + 79 и т.д., то есть однозначного разложения нет и знающий произведение может узнать числа, но знающий сумму их не может узнать.
2. Если произведение чётное:
2.1. Сумма 174 и оба числа чётные -- кажется, та же фигня, что и выше, но надо проверять
2.2. Сумма нечётная, одно число чётное, другое нечётное -- мы не сможем узнать их решение (все нечётные числа в нужном диапазоне представляются по Лемойну как минимум двумя способами)

вроде так
Свобода, равенство, братство.

Или смерть.

Аватара пользователя
гаер*
Сообщения: 2423
Зарегистрирован: Пн июл 12, 2010 5:01 pm

Re: Задачка

Сообщение гаер* » Пн апр 20, 2015 9:21 pm

Гесс писал(а):Интересно что ряд четных чисел не может быть представлен как сумма 2 разных простых: 82, 86...
ладно, проехали

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Пн апр 20, 2015 9:24 pm

1) Нужно доказать (как немануально пока незнаю) что 82, 86, 174, 178, 182, 184, 188, 190, 192, 194 не являются суммами
2) Тогда сумма гарантированно нечетная.
3) Тогда одно из чисел четное а второе нечетное.
4) Тогда их произведение четное.

Очень невнятные решения со ссылкой на Квант 95ого или 78ого года утверждают что это 13 и 4, но мне катастрофически непонравились рассуждения. (9ого номера Кванта в 95ом году не существует, а 8ой номер 78 года не содержит такой задачи). Да, я уже провел маленький литературный поиск и он меня не удовлетворил.

Аватара пользователя
гаер*
Сообщения: 2423
Зарегистрирован: Пн июл 12, 2010 5:01 pm

Re: Задачка

Сообщение гаер* » Пн апр 20, 2015 9:28 pm

Гесс писал(а):
uchebnik fiziki писал(а):Надо ещё в случае остальных нечётных проверить, что они не являются суммой двух простых -- это все числа вида "простое+2"
Этот список был составлен из матрицы "все простые до 100" на "все простые до 100" с отбраковкой всех дублей и ранжировкой по возрастанию, так что здесь реально выкинуты все возможные комбинации простых чисел, четные и нечетные, при условии что оба эти числа меньше 100 и неравны между собой.
Ох уж эти машинные методы! Может на входе был неправильный список "все простые до 100"?

Аватара пользователя
гаер*
Сообщения: 2423
Зарегистрирован: Пн июл 12, 2010 5:01 pm

Re: Задачка

Сообщение гаер* » Пн апр 20, 2015 9:32 pm

Гесс писал(а):Нужно доказать (как немануально пока незнаю) что 82, 86, 174, 178, 182, 184, 188, 190, 192, 194 не являются суммами
лучше мануально что являются 82=71+11; 86=79+7

Аватара пользователя
uchebnik fiziki
Сообщения: 4265
Зарегистрирован: Пн авг 20, 2012 9:04 pm

Re: Задачка

Сообщение uchebnik fiziki » Пн апр 20, 2015 10:11 pm

хотя для 174, кажется, однозначный вариант 93 (3*31) + 81 (3^4)
Свобода, равенство, братство.

Или смерть.

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Пн апр 20, 2015 10:16 pm

гаер* писал(а):
Гесс писал(а):
uchebnik fiziki писал(а):Надо ещё в случае остальных нечётных проверить, что они не являются суммой двух простых -- это все числа вида "простое+2"
Этот список был составлен из матрицы "все простые до 100" на "все простые до 100" с отбраковкой всех дублей и ранжировкой по возрастанию, так что здесь реально выкинуты все возможные комбинации простых чисел, четные и нечетные, при условии что оба эти числа меньше 100 и неравны между собой.
Ох уж эти машинные методы! Может на входе был неправильный список "все простые до 100"?
А может мегамозги были накуренные, а может задача некорректно составлена, а может быть корова, а может проплыла. "Машинный метод" это был Эксель. Ну и ручная чистка дублей приведшая к ошибке описанной в следующем посте.

Ряд решателей утверждает что следует исключить простые числа больше 50. Мне это неясно. Кто-то возьмется обьяснить?

Код: Выделить всё

http://www.socionica.com/viewtopic.php?pid=264559#p264559

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Пн апр 20, 2015 10:20 pm

гаер* писал(а):
Гесс писал(а):Нужно доказать (как немануально пока незнаю) что 82, 86, 174, 178, 182, 184, 188, 190, 192, 194 не являются суммами
лучше мануально что являются 82=71+11; 86=79+7
Да, результат ручной чистки дублей. В матрице они есть, в конечном ряде уже потеряны. Тем не менее 174, 178, 182, 184, 188, 190, 192, 194 в матрице нет, проверил повторно. Чтото голова сегодня помноженная на ноль.

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Пн апр 20, 2015 10:35 pm

Кажется я понял на интуитивном (но пока не строгоматематическом) уровне почему простые числа больше 50 должны быть исключены из рассмотрения.

Аватара пользователя
uchebnik fiziki
Сообщения: 4265
Зарегистрирован: Пн авг 20, 2012 9:04 pm

Re: Задачка

Сообщение uchebnik fiziki » Пн апр 20, 2015 10:41 pm

а, блин, действительно, большие же однозначное разложение дают
Свобода, равенство, братство.

Или смерть.

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Пн апр 20, 2015 11:57 pm

Очень тупорылый и очень машинный метод, заточенный под реализацию в Экселе.
1) Первый лист - произведение 2-99 на 2-99, это "всего" 10 000 чисел, в виде симметричной матрицы. Главную диагональ можно убивать сразу.
2) Второй лист - сумма чисел той же матрицы. Для простоты рассматриваем треугольник под диагональю. Перепндикулярно главной диагонали будут проходить "изолинии". Из этих изолиний надо будет убить все изолинии чисел которые я прописал на прошлой странице. Плюс все горизонтали и вертикали из простых чисел старше 50. Чисел будет еще очень много.
3) Третий лист - проверяет "жива ли" клетка на втором листе и если да - берет значение клетки с первого листа. Если клетка мертва - не берет ничего.
4) Дальше нам нужно найти в этой матрице произведений все произведения которые встречаются только один раз. И выяснить кто из них встречался на первом листе больше одного раза. Это должно быть уже очень ограниченное число произведений и нам будут известны пары чисел их образующие.
5) Остается проверить суммы от разложений произведений из п.4. и найти уникальную сумму.
PROFIT.

Аватара пользователя
uchebnik fiziki
Сообщения: 4265
Зарегистрирован: Пн авг 20, 2012 9:04 pm

Re: Задачка

Сообщение uchebnik fiziki » Вт апр 21, 2015 12:02 am

думаю, там надо убивать избыточные варианты с помощью гипотез о суммах простых и произведений простых: наверняка их больше, чем две уже приведённых
Свобода, равенство, братство.

Или смерть.

Аватара пользователя
ИСН
Робин Гуд
Сообщения: 8531
Зарегистрирован: Пт окт 10, 2003 5:32 pm
Контактная информация:

Re: Задачка

Сообщение ИСН » Вт апр 21, 2015 1:24 am

Фух, вроде осилил.

Код: Выделить всё

sum = Range[4, 198];
prod = Union[Flatten[Table[i*j, {i, 2, 99}, {j, 2, i}]]];
nonsum = Union[Flatten[Table[Prime[i] + Prime[j], {i, PrimePi[100]}, {j, i}]]];
prod = Select[prod,
  Function[n, 
     d = Select[Divisors[n], (1<#<100) && (1<n/#<100) && (#<=n/#) &];
     Length[d] > 1 && Length[Complement[d + n/d, nonsum]] == 1
    ][#]&
  ]
sum = Select[sum, Function[Length[Intersection[Table[i*(#-i), {i, 2, #/2}], prod]] == 1][#] &]
Complement[sum, nonsum]
Решение таки единственно: сумма - 17, произведение - 52.

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Вт апр 21, 2015 2:15 am

В 10 строк?
Я ушел плакать.

Мой вариант с Экселем тоже потребовал бы программирования - на третьем листе будет около полутора тысяч живых клеток из них несколько сотен значений встречаются однократно, совмещать это с первым листом можно либо скриптом либо очень упертым студентом. Ни того ни другого у меня нет.

Аватара пользователя
Maryna
Лиса-Алиса
Сообщения: 7002
Зарегистрирован: Пт июл 28, 2006 12:14 pm
Контактная информация:

Re: Задачка

Сообщение Maryna » Вт апр 21, 2015 10:09 am

Люди, вы мне вернули этот мир.
Таки мое предположение относительно трех простых (13 и 2*2) было правильным.
Интересно, можно ли ее все-таки решить без Экселя и программирования? Гесс, что там народ в интернетах писал по этому поводу?

Аватара пользователя
Гесс
Сообщения: 13055
Зарегистрирован: Ср фев 15, 2012 11:19 pm

Re: Задачка

Сообщение Гесс » Вт апр 21, 2015 10:56 am

Maryna писал(а):Люди, вы мне вернули этот мир.
Таки мое предположение относительно трех простых (13 и 2*2) было правильным.
Интересно, можно ли ее все-таки решить без Экселя и программирования? Гесс, что там народ в интернетах писал по этому поводу?
Я закрыл вчера все ссылки, поэтому их надо перегугливать, вот например, http://www.socionica.com/viewtopic.php?id=3206&p=2 преимущественно страница 2.
Практически во всех лучших решениях в конце народ остается с примерно 10 вариантов сумм для которых длжен проверить число возможных разложений, и только для 17 разложение оказывается единственным. Если задача реально была в Кванте, то я попробую ее выгуглить, там должно быть изящное решение.

Аватара пользователя
Maryna
Лиса-Алиса
Сообщения: 7002
Зарегистрирован: Пт июл 28, 2006 12:14 pm
Контактная информация:

Re: Задачка

Сообщение Maryna » Вт апр 21, 2015 11:56 am

Большое спасибо, Гесс, буду пристально втыкать.

Аватара пользователя
uchebnik fiziki
Сообщения: 4265
Зарегистрирован: Пн авг 20, 2012 9:04 pm

Re: Задачка

Сообщение uchebnik fiziki » Вт апр 21, 2015 12:06 pm

Гесс писал(а):только для 17 разложение оказывается единственным
3*5+2
Свобода, равенство, братство.

Или смерть.

Аватара пользователя
ИСН
Робин Гуд
Сообщения: 8531
Зарегистрирован: Пт окт 10, 2003 5:32 pm
Контактная информация:

Re: Задачка

Сообщение ИСН » Вт апр 21, 2015 12:57 pm

У 3*5 и 2 произведение не фигурирует в списке хороших произведений (т.е. таких, по которым на 3 шаге становятся ясны сами числа). Видимо, это потому, что у него (у 30) есть другие разложения, по которым сумма множителей тоже хорошая. Да собственно, что далеко ходить: 5*6.

Ответить

Вернуться в «лицом к лицу»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 20 гостей