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

[gris]

Ну тогда и
$2\cdot 9^3\to\{1458,1620,1800,2000\}$
А вот пять членов никак не уместить. Вообще можно оценку делать наибольшего количества членов натуральной геометрической прогрессии на интервале определённой длины. Как отметил Лукомор, можно длину прогрессии считать не в количестве членов, а в разности между первым и последним. Два числа всегда образуют прогрессию, а вот три натуральных — нет. Если прогрессию длиной три в первом смысле начинать с $n^2$, то её наименьшая длина во втором смысле будет $2n+1$. То есть, если задан интервал $[1000000,1002000]$, то не стоит там искать трёхчленную прогрессию. Ну и вообще. А уже было написано про оценку через отношение. Только, мне кажется, там зависит и от начального числа. Например, на интервале $[N,2N]$ при большом $N$ можно длинную прогрессию построить.

[atlakatl]

Уже при знаменателе $12/11$ на интервале $[N, 2,4N]$ получаем 11 членов:
25937424601
28295372292
30867678864
33673831488
36735088896
40074642432
43717791744
47692136448
52027785216
56757583872
61917364224
Знаменатель всё ближе к $1$. Значит, и на интервале члены будут располагаться гуще.

[gris]

atlakatl, а Вы не заглядывали в файл с решением? Я просто боюсь по нынешним временам.

(Оффтоп)

ИСН приучил к студенту, а сам его забросил. А Один студент вот так скачал файл с решением, а там сотовый телефон. Теперь уж седьмой год ничего не скачивает

А то начну свои дурацкие идеи выкладывать, а они уж изложены и лучше в сто раз.
Я бы как делал, например, для интервала $[568743,1056423]$:
$(\sqrt[4]{568743}+1)^4=753420<;\quad(\sqrt[5]{568743}+1)^5=800059<;\quad(\sqrt[6]{568743}+1)^6=1062991>$
То есть ищем прогрессии в $5+1=6$ членов. Ну и первую пятую степень берём.
$(\lceil\sqrt[5]{568743}\rceil)^5=759375;$
$(\lceil\sqrt[5]{568743}\rceil+1)^5=1048576;$
Знаменатель $16/15$.
Всё нормально. Но это повезло, конечно, с правым концом. Если взять, например,$900000$, то придётся искать кратные или вообще пять-прогрессию.

[Simple Fairy]

Я тут совсем мимокрокодил, но мне кажется, что эта задача не имеет какого-то НЕ переборного решения,
т.к. подразумевает нахождения наибольшего количества целых членов на заданном промежутке, а он полностью зависит от факторизации данных чисел в этом промежутке, т.е. путь состоит в умножении какого-то начального значения из промежутка на q, которое будет 'съедать' степени простых чисел и заменять их какими-то новыми, которые больше прежних, причем я предполагаю, что если мы берем q как отношение двух таких чисел, то числитель всегда должен быть на 1 больше знаменателя, таким образом задача сводится к факторизации всех чисел на отрезке, возможно, что этот перебор можно как-то сократить, но на асимптотику перебора это повлиять не должно. (Максимум можно сделать какие-то асимптотические оценки сверху/снизу).

P.S. Судя по моим рассуждаем, задача явным образом сводится к функции делителей, а для нее уже известны оценки сверху(насчет снизу не знаю)

$$ \tau(n) < ne^{\gamma}\ln\ln(n)+\frac{0.6483}{\ln\ln(n)} $$

[atlakatl]

gris
Файл по ссылке ТС кривой, не распознаётся.

[Лукомор]

gris в сообщении #1217718 писал(а):

Ну тогда и ...

$11^3\to\{1331,1452,1584,1728\}$

[Simple Fairy]

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

gris
Файл по ссылке ТС кривой, не распознаётся.

У меня все работает, попытайтесь открыть 'адобом'.

[atlakatl]

Simple Fairy
Спасибо, открыл.

[pppppppo_98]

gris в сообщении #1217718 писал(а):

Ну тогда и
Только, мне кажется, там зависит и от начального числа. Например, на интервале $[N,2N]$ при большом $N$ можно длинную прогрессию построить.

зависимость от от начального члена $M_{min}$, а не только от $\frac{M_{max}}{M_{min}}$ естественно будет. в этом можно убедиться даже в школьном варианте сократив обе границы на 7, то есть взяв интервал [30,50]... Для других значений можно просто умножить границы отрезка на большую степень достаточно большего числа скажем ${(2^m)}^n$. Длина будет не менее чем $n$, для дроби $1+2^{-m}}$, если ${\left(1+2^{-m\right)}^n<\frac{M_{max}}{M_min}}$

[gris]

А в чём, собственно, состоит теоретический вопрос? Существует функция $\mathrm{PPPPPPP}(N, L)$, дающая максимальное число членов натуральной геометрической прогрессии на интервале $[N,N+L]$ и её можно исследовать. Она себя ведёт, по моему, без сильных скачков. Можно посмотреть её изменение при постоянном $N, L$ или их отношении. Можно находить все прогрессии в заданном интервале.
Или это чисто алгоритмическая задача?

[pppppppo_98]

gris в сообщении #1217788 писал(а):

А в чём, собственно, состоит теоретический вопрос?

Какая временная сложность этого алгоритима (или эквивалентно сложность вычисления вашей функции) ? Или хотя бы к какому классу принадлежит $\mathbf{P}$ или $\mathbf{NP}$. Естиь ведб очень простые в формулировке функции, которые на практике оказываются весьма сложно вычислимы (в книге Булоса Вычислимость и логика, приведен пример такой функции)...Тут ситуация попроще виден экспотенциальный предел (по длине арнгументов, ибо как правильно вы заметили, все ГП можно перечислить). Но тогда вопрос, а что нибудь эффективнее в стиле алгоритма евклида - никто ничего не видет?

Цитата:

Существует функция $\mathrm{PPPPPPP}(N, L)$, дающая максимальное число членов натуральной геометрической прогрессии на интервале $[N,N+L]$ и её можно исследовать. Она себя ведёт, по моему, без сильных скачков. Можно посмотреть её изменение при постоянном $N, L$ или их отношении. Можно находить все прогрессии в заданном интервале.
Или это чисто алгоритмическая задача?

[Simple Fairy]

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

gris в сообщении #1217788 писал(а):

А в чём, собственно, состоит теоретический вопрос?

Какая временная сложность этого алгоритима (или эквивалентно сложность вычисления вашей функции) ? Или хотя бы к какому классу принадлежит $\mathbf{P}$ или $\mathbf{NP}$. Естиь ведб очень простые в формулировке функции, которые на практике оказываются весьма сложно вычислимы (в книге Булоса Вычислимость и логика, приведен пример такой функции)...Тут ситуация попроще виден экспотенциальный предел (по длине арнгументов, ибо как правильно вы заметили, все ГП можно перечислить). Но тогда вопрос, а что нибудь эффективнее в стиле алгоритма евклида - никто ничего не видет?

Цитата:

Существует функция $\mathrm{PPPPPPP}(N, L)$, дающая максимальное число членов натуральной геометрической прогрессии на интервале $[N,N+L]$ и её можно исследовать. Она себя ведёт, по моему, без сильных скачков. Можно посмотреть её изменение при постоянном $N, L$ или их отношении. Можно находить все прогрессии в заданном интервале.
Или это чисто алгоритмическая задача?

Ну, я могу точно придумать алгоритм с полиномиальной сложностью, а что у вас за алгоритм - не знаю.
P.S. В стиле алгоритма евклида, это $\log n$? - тогда вряд ли.

[pppppppo_98]

Simple Fairy в сообщении #1217813 писал(а):

Ну, я могу точно придумать алгоритм с полиномиальной сложностью, а что у вас за алгоритм - не знаю.
P.S. В стиле алгоритма евклида, это $\log n$? - тогда вряд ли.

я таки не был точен и не пояснил, что я подразумеваю под полиномиальностью...а под полиномиальностью я подаразумеваю полиномиальность по длине чисел. Пусть $m_1=\log M_{min}, m_2=\log M_{max}, m=\max\left\{m_1,m_2\right\}$ или $m=m_1+m_2$, что в контексте классов сложности эквивалентно . Под полиномимиальной сложностью понимаю число шагов $O(m^{\alpha})$...для некоторого фиксированного положительного действительного $\alpha$. Если речь, идет о полиномиальности по $M_{min},M_{max}$ - то это субэкспотенциальный алгоритм. я построил в первом своем посте алгоритм, который точно не хуже экспотенциального. Если есть интерес - скачайте файл по ссылке и откройте в adobe reader. Может еще какое дельное замечание об ускорении сходимости

меня вот все мысль свербит - нельзя ли тут цепные дроби при оценках начального члена прогрессии как-то применить

[atlakatl]

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

я построил в первом своем посте алгоритм, который точно не хуже экспотенциального

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

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

нельзя ли тут цепные дроби при оценках начального члена прогрессии как-то применить

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

[Dmitriy40]

Сварганил перебор, запустил, подождал. Результат интересный. Искал минимальные последовательности (наименьшее $N$) заданной длины с заданным отношением начального и конечного числа (точнее не самих чисел, а допустимых границ). Конкретно, искал в интервале $[N, \, 2N]$. Вот что нашёл:

9,12,16,n=3
64,80,100,125,n=4
1296,1512,1764,2058,2401,n=5
16807,19208,21952,25088,28672,32768,n=6
531441,590490,656100,729000,810000,900000,1000000,n=7

Посмотрев на начальное число и подумав пришёл к гипотезе:

Цитата:

пусть ищем последовательность из $n$ членов, в границах $[N, \, kN], k=\operatorname{const}$, тогда первой (наименьшей, минимальной по величине чисел, с наименьшим $N$) будет последовательность с первым числом $N=p^{n-1}$, где $p$ выбирается минимальным так чтобы выполнялось $\left(\frac{p+1}{p}\right)^{n-1} \le k$.

Т.е. перебор нужен лишь для подбора $p$, да и то, похоже от него тоже можно отказаться и вычислить $p$ напрямую из $n$ и $k$: $p=\left\lceil\dfrac{1}{\sqrt[n-1]{k}-1}\right\rceil$. Но возможно это работает лишь для минимальных последовательностей (не фиксированном $N$).

-- 21.05.2017, 17:09 --

Как ни странно, но для интервала $[210, \, 350]$ гипотеза выдаёт правильную последовательность $216, 252, 294, 343$. Случайность конечно, ну или сознательный выбор автора задачи.

-- 21.05.2017, 17:17 --

Если надо найти не минимальное $N$, а в заданном интервале, то можно найти минимальное, а потом домножить на минимальный коэффициент для попадания в заданный интервал. Похоже об этом уже было сказано выше:

gris в сообщении #1217708 писал(а):

Число вида $cn^k$ стартует натуральную прогрессию длиной $k+1$ со знаменателем $m/n$. Для густоты $m=n+1$.

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