ЕГЭшная задача с совсем не школьным продолжением

[pppppppo_98]

atlakatl в сообщении #1217829 писал(а):

Дан интервал. В Вашей статье проводится оценка максимальной длины прогрессии, возможных знаменателей.

Только вот нюанс в том ,что это интервал по мере роста оценки $m^*$ сокращается, верхняя граница тоже сокращается не хуже корня (неизвестной степени) - вот вопрос в том как оценить сокращение.. Да и нижняя растет , что сокращает перебор.

Цитата:

А дальше начинаем считать.
В псевдокоде у Вас одни процедуры. Где программа-то?

Цитата:

Дык первая процедура и есть программа - на входе$M_{min},M_{max}$ - на выходе $L_{max} - максимальная длина$. Логарифмы -корни имеют сложность пропорциональную длине(условно говоря найти делением максимальную степень, либо перебором по разрядам корень)

Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot 10^9]$.
Как происходит проверка конкретного знаменателя? - Я к чему? Вы утверждаете, что алгоритм у Вас "экспоненциальный".

Потому что верхняя граница , как мне кажется ( о чем и стоит вопрос) и останется функцией намного большего роста, чем логарифм верхней границы ака длины верхней границы...

Цитата:

Т.е. кроме сканирования по всему (или его конечной части) интервалу для определения первого члена не видно.
А значит, время счёта тупо пропорциональна длине интервала. И никакой экспоненты.

Ну думать или спрашивать об оптимизации никому не запрещено...Тем более есть такая вещь в музыке - называется октава...Там ведь для практических целей создания музыкальных инструментов аппроксимируют $2^{\frac{i}{12}}$ ближайшими цепными дробями....вот и думаю нельзя ли как -то и здесь применить цепные дроби для сокращения поиска - их числители знаменатели ведь тоже растут экспоненциально с каждым шагом аппроксимации

[Dmitriy40]

Dmitriy40 в сообщении #1217831 писал(а):

Если надо найти не минимальное $N$, а в заданном интервале, то можно найти минимальное, а потом домножить на минимальный коэффициент для попадания в заданный интервал.
...
И тогда перебор вообще не нужен, можно обойтись прямыми вычислениями, с временем $O(1)$.

Вот с этим я промахнулся, не для всяких интервалов это находит ответ. Например для интервала $[8000, \, 16000]$ ни одной из двух последовательностей длиной $n=5$ таким способом не находится. Значит без перебора всё же никуда.
Но можно ограничиться перебором лишь по $p$, начиная от указанного выше минимального вверх, находя коэфициент $c$ для попадания выражения $cp^{n-1}$ в заданный интервал и проверяя последнее число на попадание в интервал. Т.е. перебор будет весьма и весьма ограниченным, буквально несколько разных значений, в остальном же прямые вычисления.

[pppppppo_98]

atlakatl в сообщении #1217829 писал(а):

Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot 10^9]$.

кстати тоже детский интервал - его можно тоже не на егэ конечно (но не какой нибудь средненькой олимпиаде для 9 класса давать). Потому как уже на втором шаге итераций по s (s=3) можно найти последовательность длины равную 5. А значит перебор падает до верхней границы s=100 (потому что убывающие последовательности длины 6 должны начинаться с некоторого кратного пятой степени какого-то натурального числа) ...Тут похоже какая-то нетривиальная сложность перебора с зависимостью как от $M_{min}$, так и от $\frac{M_{max}}{M_{min}}$ (ну либо числа детские - нужны монструозные числа... либо недостаточная сложность границ, либо их отношений)

[Dmitriy40]

atlakatl в сообщении #1217829 писал(а):

Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot 10^9]$.

Если я прав в своей гипотезе, то в данном интервале должны быть последовательности из 12-ти членов (например 1088391168, 1269789696, 1481421312, 1728324864, 2016379008, 2352442176, 2744515872, 3201935184, 3735591048, 4358189556, 5084554482, 5931980229 - возможно и единственная) и не должно быть ни одной из 13-ти членов. Причём это легко посчитано руками на калькуляторе, даже без программ.

(PS. Числа.)

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

[Someone]

(Dmitriy40)

Dmitriy40 в сообщении #1217905 писал(а):

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

Что Вы имеете в виду? Шрифт не нравится?
$1\,088\,391\,168$, $1\,269\,789\,696$, $1\,481\,421\,312$, $1\,728\,324\,864$, $2\,016\,379\,008$, $2\,352\,442\,176$, $2\,744\,515\,872$, $3\,201\,935\,184$, $3\,735\,591\,048$, $4\,358\,189\,556$, $5\,084\,554\,482$, $5\,931\,980\,229$.

[pppppppo_98]

Dmitriy40 в сообщении #1217905 писал(а):

atlakatl в сообщении #1217829 писал(а):

Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot 10^9]$.

Если я прав в своей гипотезе, то в данном интервале должны быть последовательности из 12-ти членов (например 1088391168, 1269789696, 1481421312, 1728324864, 2016379008, 2352442176, 2744515872, 3201935184, 3735591048, 4358189556, 5084554482, 5931980229 - возможно и единственная) и не должно быть ни одной из 13-ти членов. Причём это легко посчитано руками на калькуляторе, даже без программ.

(PS. Числа.)

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

Я тоже посчитал в Mathematica за 70 шагов (с таким интервалом действительно можно в олимпиаду выкладывать)... Ща выложу листинг.. Да пока проверял в псевдокоде три бага нашел...то же исправлю и выложу....


Итак листинг Mathematica cо итерациями для этого случая http://my-files.ru/q2s8hi (в pdf)

Сам исходный файл Mathematica http://my-files.ru/t8z8pg (с расширением .nb)

Текст решения с исправленным псеводокодом в решении http://my-files.ru/nvkatv (в pdf)

ЗЫ

Извиняюсь сразу за оффтопик, и не камень в чужой огород...А почему так латек коряво выглядит. Это из-за моих настроек, или движок ренедерит в картинку - а потом ее вставляет в текст? На других сайтах как-то покрасивше выглядит - особенно если работает MathJaX

[Dmitriy40]

(Числа)

Someone в сообщении #1217920 писал(а):

Что Вы имеете в виду?

Не, это похоже я ошибся при редактировании формулы, знаки $ расставил, а вот теги math оставил лишь вокруг всей последовательности, ну все числа и слились в одну формулу криво. Сейчас ещё раз перепроверил, теперь отображается правильно, если каждое число и $ и math обрамлено. Раздражает эта вот особенность движка, с тегами math, как будто просто $ мало.

[Батороев]

pppppppo_98 в сообщении #1217419 писал(а):

Пусть имеется отрезок ряда натуральных чисел - найти длину наибольшей геометрической прогрессии, лежащую в этом отрезке(скажем $[M_{min},M_{max}]$)

Как мне видится, на заданном интервале необходимо определить максимальные одинаковые степени двух наибольших последовательных натуральных чисел. Например, в ЕГЭ-шной задаче: $6^3=216, 7^3=343$.

[Mikhail_K]

Батороев в сообщении #1217926 писал(а):

Как мне видится, на заданном интервале необходимо определить максимальные одинаковые степени двух наибольших последовательных натуральных чисел. Например, в ЕГЭ-шной задаче: $6^3=216, 7^3=343$.

Это не так. Возьмите ЕГЭшную задачу и замените в ней обе границы промежутка на в два раза большие.

[Батороев]

Mikhail_K в сообщении #1217928 писал(а):

Возьмите ЕГЭшную задачу и замените в ней обе границы промежутка на в два раза большие.

Получил четыре числа: $343;392;448;512$. У Вас больше?

[Mikhail_K]

Батороев в сообщении #1217930 писал(а):

Получил четыре числа: $343;392;448;512$. У Вас больше?

Вы увеличили вдвое обе границы промежутка? и какая нижняя граница?

[Батороев]

(Оффтоп)

Тьфу на меня! Отвлекся на основную работу и напортачил...

-- 22 май 2017 11:43 --

Получил варианты только по три числа.

-- 22 май 2017 12:11 --

(Оффтоп)

Батороев в сообщении #1217926 писал(а):

Как мне видится

Значит, не все виделось. т.к. существует цепочка из четырех удвоенных ЕГЭ-шных.

[pppppppo_98]

Кто подскажет. А какие существуют библиотеки с/с++ для работы с действительно целыми длинными числами (ну скажем в десяток-сотню тысяч цифр). Ну и соответственно не сильно смещенный генератор случайных последовательностей такой длины.

[Xaositect]

pppppppo_98 в сообщении #1217944 писал(а):

Кто подскажет. А какие существуют библиотеки с/с++ для работы с действительно целыми длинными числами (ну скажем в десяток-сотню тысяч цифр). Ну и соответственно не сильно смещенный генератор случайных последовательностей такой длины.

https://gmplib.org/

[Someone]

Попроще в обращении NTL. Я её когда-то в C++Builder компилировал. Насколько я помню, её можно откомпилировать так, чтобы она использовала GMP в качестве вычислительного ядра. Но для компиляции GMP мне пришлось возиться с MinGW и MSYS.

(Dmitriy40)

Dmitriy40 в сообщении #1217923 писал(а):

Не, это похоже я ошибся при редактировании формулы, знаки $ расставил, а вот теги math оставил лишь вокруг всей последовательности

Ну да, там появляется абзацный отступ и перенос на следующую строку, и, поскольку результат выдаётся в виде картинки, выглядит действительно безобразно. И ещё надо удалить лишние знаки доллара, которые появляются после нажатия на кнопку math (раньше их не было; я не заметил, когда они появились — похоже, из-за начинающих пользователей, которые вечно math ставят, а знаки доллара забывают).

Dmitriy40 в сообщении #1217923 писал(а):

Раздражает эта вот особенность движка, с тегами math, как будто просто $ мало.

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