Prime Sums

[Nataly-Mak]

Не поняла.
Вот такая и будет задача?

Цитата:

Прямолинейные программы является последовательность, которая начинается с 1 и имеет каждая запись получается из двух предыдущих записей на сложение, умножение или вычитание. Эта последовательность показывает наименьшее количество шагов, необходимых для достижения п!.10-шагом, решение за 12 {1, 2, 4, 6, 24, 30, 720, 900, 924, 518400, 12!}, Найденных Stan Wagon, Джон Гилфорд найдены все такие, и доказано, что 10 является минимальным за 12!

Цитата из A217032.

[Herbert Kociemba]

Nataly-Mak в сообщении #672911 писал(а):

Вот такая и будет задача?

Of course I do not know, but I see no other interesting problem which has to do with straight lines and factorials

[Nataly-Mak]

Ну, скоро узнаем

[mertz]

Will need a large integer library. 64-bit integers will work for N < 22. 128-bit for N < 34.

[Nataly-Mak]

Программы на QBASIC с очень большими числами не работают.
У меня были большие проблемы в конкурсе "Orchard Planting Problem".
Поэтому вряд ли я буду решать эту задачу.
Кроме того, она мне не показалась интересной. Хотя первый взгляд бывает ошибочным.
Статья в OEIS, между прочим, недавно написана. Задача свеженькая

(Оффтоп)

Ну почему никто из организаторов конкурса не предложит ни одну из моих проблем?
Мне кажется, что мои задачи по квадратам намного интереснее. Например, искать квадраты Стенли из простых чисел с минимальным индексом. А? Или квадраты Стенли из чисел Смита с минимальным индексом. До порядков 6-7 ещё не так сложно найти, а вот для порядков больше 7 уже надо попыхтеть

На сайте primepuzzles.net уже появились две мои головоломки: 663 и 671.
Последняя по совершенным магическим квадратам из простых чисел:
http://www.primepuzzles.net/puzzles/puzz_671.htm
Carlos обещал в феврале опубликовать головоломку о квадратах Стенли из простых чисел.

Отправка статьи в OEIS о квадратах Стенли (из простых чисел и из чисел Смита с минимальным индексом) у меня зашла в тупик.
Уже двоих товарищей просила помочь скомпоновать материал в формате статьи и отправить его в Энциклопедию. Оба сначала согласились помочь, но потом замолчали.
Напоминать мне неудобно. Кого ещё попросить помочь??
Кто хорошо знает процедуру отправки статьи в OEIS? Я давно делала это сама по аналогии с предыдущими статьями о магических квадратах. Но сейчас уже забыла, да и статья о квадратах Стенли не аналогична - там были статьи о магических квадратах, а теперь об антимагических
Если кто может помочь мне с этим, прошу написать в личку.

[Pavlovsky]

Для задачи N=7 min решения 1798 не существует.

[Nataly-Mak]

Pavlovsky
вы молдоцом, решаете задачу, грызёте
Осталось, значит, для минимума "семёрки" проверить 1800. И минимумы будут закрыты. Останутся максимумы.

(Оффтоп)

А у меня ничего не получилось с новыми рекордами, и я ушла в другую тему - грызу квадраты Стенли.
Параллельно занялась восстановлением Антологии "Россия"
[огромная поэтическая антология, которая сдохла вместе со старым сайтом; так жалко! пропал такой большой труд; сохнанилось у меня на диске далеко не всё, что-то придётся набирать заново или искать в Интернете; сейчас почти восстановила 2-ой том (XX век); начала с него, так как он намного меньше по объёму 1-го тома].

[dimkadimon]

Pavlovsky в сообщении #673241 писал(а):

Для задачи N=7 min решения 1798 не существует.

Почему?

[Pavlovsky]

Поиск решения 1798, это первая попытка использования механизма подсхем.

1) Берем все неизоморфные схемы с нижней оценкой 1798.
2) Добавляем к ним все допустимые наборы простых чисел. Собственно это у меня уже все было.
3) В связке схема+набор простых чисел, ищем подсхемы с нижней оценкой не больше суммы первых N(=7) простых чисел.

Полный перебор всех вариантов по пункту 3) не дал результатов. А значит решения 1798 не существует.

Небольшой наглядный пример. Возьмем набор простых чисел (последний в списке).
89,101,103,107,109,113,127,131,137,139,149,157,163,173
Сумма первых 7-и простых чисел равна 749. Не существует схемы с оценкой 1798, у которой есть подсхема (7 линий) с оценкой <=749.

[Nataly-Mak]

Забавная страничка с часовыми поясами есть на сайте AZ



До начала конкурса осталось чуть меньше 6 часов.

-- Сб янв 19, 2013 14:34:49 --

Pavlovsky в сообщении #673543 писал(а):

Небольшой наглядный пример. Возьмем набор простых чисел (последний в списке).
89,101,103,107,109,113,127,131,137,139,149,157,163,173
Сумма первых 7-и простых чисел равна 749. Не существует схемы с оценкой 1798, у которой есть подсхема (7 линий) с оценкой <=749.

Другими словами можно сказать --- без подсхем? Не удаётся выставить первые 7 зачётных линий:

89,101,103,107,109,113,127

Или это не равносильные утверждения? Что-то никак не пойму

[Pavlovsky]

Nataly-Mak в сообщении #673603 писал(а):

Другими словами можно сказать --- без подсхем? Не удаётся выставить первые 7 зачётных линий:

Нет не так.

Пусть у нас есть схема (14 линий) с оценкой 1798 и у нее есть подсхема (7 линий) с оценкой 749. Это означает, что есть теоретическая возможность, построить квадрат где 14 линий схемы дает сумму 1798 и одновременно 7 линий подсхемы дают сумму 749. Это достаточно сильное необходимое условие.

Скажем мы можем найти 14 линий которые дают сумму 1798. Так же можем найти 7 линий дающих сумму 749. Но чтобы выполнились эти условия одновременно, необходмо чтобы 7 линий являлись поднмножеством 14 линий. Причем не просто подмножеством. Числа на 7-ми линиях мы должны распределять с учетом того, что числа у нас уже разбиты на группы основной схемой (14 линий).

[Nataly-Mak]

Pavlovsky в сообщении #673636 писал(а):

Скажем мы можем найти 14 линий которые дают сумму 1798. Так же можем найти 7 линий дающих сумму 749. Но чтобы выполнились эти условия одновременно, необходмо чтобы 7 линий являлись поднмножеством 14 линий. Причем не просто подмножеством. Числа на 7-ми линиях мы должны распределять с учетом того, что числа у нас уже разбиты на группы основной схемой (14 линий).

Нет, не врубилась.
1. Пусть мы можем найти 14 линий, которые дают сумму 1798.
Эта сумма имеет конкретный, соответствующий ей, набор из 14 простых.
Но тогда есть 7 линий, дающих сумму первых 7 простых этого набора!

2. Эти 7 линий являются подмножеством 14 линий. Причём не просто подмножеством. Числа в этих 7 линиях распределены с учётом того, что числа уже разбиты на группы основной схемой.

И что здесь не так

-- Сб янв 19, 2013 15:39:10 --

Ещё раз: я хочу доказать эквивалентность двух утверждений: вашего с использованием понятия "подсхема" из 7 линий и моего --- без использования этого понятия (просто 7 первых зачётных линий).
Пока не вижу, почему эти утверждения не эквивалентны.

[Pavlovsky]

Nataly-Mak в сообщении #673645 писал(а):

1. Пусть мы можем найти 14 линий, которые дают сумму 1798.
Эта сумма имеет конкретный, соответствующий ей, набор из 14 простых.

Это совсем не так. Нижняя оценка 1798 для схемы, означает, что мы можем так расставить числа в квадрате, что сумма линий будет 1798. Ниоткуда не следует, что мы гарантируем что все суммы линий будут простые числа. То есть нижняя теоретическая оценка 1798, это необходимое, но не достаточное условие построения решения по заданной схеме.

Механизм подсхем тоже формулирует только необходимое условие, просто гораздо более жесткое.

Pavlovsky в сообщении #673636 писал(а):

Пусть у нас есть схема (14 линий) с оценкой 1798 и у нее есть подсхема (7 линий) с оценкой 749.

Эта фраза означает, что можем так расставить числа в квадрате, что сумма 14 линий будет 1798, а 7 линий из этих 14-ти будут иметь сумму 749. Опять же, что все суммы линий будут простыми числами мы не гарантируем.

[Nataly-Mak]

Ну, это вы от простых чисел - значений зачётных линий - ушли.
Так не годится.
Если уж говорить о необходимом и достаточном условии, то надо оперировать только простыми числами.

Тогда так спрошу: 7 зачётных линий, дающих первые 7 простых чисел в конкретном наборе из 14 простых, - это подсхема

Ещё раз подчеркну: будем говорить только о наборе 14 простых, имеющем оценку 1798. Нафиг надо тут рассуждать о любых числах, дающих в сумме 1798???

Любое необходимое условие является сильным Если какое-то необходимое условие не выполняется, то уже однозначно мы не будем иметь желаемый результат (не имеет значения: сильное или слабое необходимое условие, оно обязано выполняться - и точка).

Итак, моё утверждение заключается в следующем:
пусть мы имеем схему с оценкой 1798 и конкретный набор из 14 простых, дающих в сумме 1798. Берём первые 7 простых чисел в этом наборе.
Выполняем полный перебор по схеме (естественно, к схеме у нас приложено и соответствующее разбиение; в данном случае разбиение естественное), пытаясь выставить 7 зачётных линий, имеющих 7 выбранных нами значений.

Утверждение: если не удаётся выставить указанные 7 линий при полном переборе, то и все 14 линий выставить не удастся.
Не выполнено необходимое условие!

Где ошибка в моих рассуждениях?

[Pavlovsky]

Nataly-Mak в сообщении #673658 писал(а):

Тогда так спрошу: 7 зачётных линий, дающих первые 7 простых чисел в конкретном наборе из 14 простых, - это подсхема

Нет.

Подсхема это подмножество линий основной схемы. Так же как для схемы, для подсхемы можно вычислить нижнюю (верхнюю) теоретическую оценку суммы линий входящих в подсхему.