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

[pppppppo_98]

Товарищи ученые! Доценты с кандидатами!

У дружка сын готовится к итоговому государственному тестированию (переводные экзамены из 9 в 10 класс). Звонит мне на праздниках дружок и говорит помоги решить задачу - а я на пляже лежал - говорю записать нечем. На что он отвечает условие простое - писать ничего и не надо. И формулирует мне такую задачу.

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

Отступление. Он сам не видел на тот момент задачи и как потом оказалось звучала она конкретнее. То есть был задан отрезок $[210,350]$. В этом случае задача действительно становится ЕГЭшной - нужен небольшой перебор, чтобы понять что это 4. И решается она действительно с записью минут в 15-20 (примерное время на каждую задачу ЕГЭ)

Но так как, мне она была сформулирована именно так как я сказал (жирным шрифтом), то и мое решение несколько иное. Итак я сразу же пришел к мысли , что задача не имеет аналитического решения, и сводится к построению алгоритма. Алгоритм с решением привожу по ссылке, ибо хотя и писал ее в латехе, решение на 5 листах , и не уверен, что потянет ли движок форума значительное число латеховских макросов. Все чего мне удалось добиться это перебор, который я некотроым образом сократил (чего видимо тоже хотят добиться при решении этой задачи экзаменаторы). И теперь два вопроса

1. Сложность по памяти данного алгоритма $O(1)$. Вопрос кто может оценить временную сложность в зависимости от границ $M_{min},M_{max}$? Вопрос исходит из того, что в школе ведь учат алгоритм Евклида, ибо он эффективно( со скоростью порядка длины ака логарифма числа) находить НОД двух чисел
2. Кто видит лучший по скорости алгоритм, ибо моя гипотеза что он субэкспотенциальный по длине чисел (или возможно их отношения)?

скачать решение можно здесь http://my-files.ru/wzhsv8

Так кая тут условно второй раз и не знаю местные порядки, то размещаю вопрос сразу в 3 разделах. Да простят модераторы и снесут лишние копии

[Лукомор]

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

найти длину наибольшей геометрической прогрессии

Хотелось бы уточнить, что такое "длина геометрической прогрессии", и "наибольшая геометрическая прогресия"...

[pppppppo_98]

количество членов лежащем в задаваемом отрезке

[Лукомор]

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

количество членов лежащем в задаваемом отрезке

Лукомор в сообщении #1217480 писал(а):

и "наибольшая геометрическая прогрессия"...

?!

[Mikhail_K]

Лукомор в сообщении #1217521 писал(а):

?!

Что неясно? Очевидно, рассматриваются конечные геометрические прогрессии (или, что то же самое, участки бесконечных геометрических прогрессий из идущих подряд членов), все члены которых натуральны и находятся в заданном отрезке. Длина такой прогрессии - очевидно, количество членов в ней.

[DeBill]

pppppppo_98
Перебор по всем знаменателям вида $\frac{n+1}{n}$ ?

[Skeptic]

pppppppo_98, приведите решение для ЕГЭ. Тогда снимутся все вопросы по постановке задачи.

[Лукомор]

DeBill в сообщении #1217545 писал(а):

Перебор по всем знаменателям вида $\frac{n+1}{n}$ ?

И $\frac{n-1}{n}$ ?!

-- Сб май 20, 2017 15:34:53 --

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

Что неясно?

Разница между:
"наибольшая длина геометрической прогрессии в интервале"
и
"длина наибольшей геометрической прогрессии в интервале"...

[atlakatl]

pppppppo_98 дал "ответ": 4 члена - и свалил.
Всё понятно только Mikhail_K
$350/210=5/3$ В пределах этого числа надо уместить куб знаменателя прогрессии - коль речь идёт о 4-х членах.

[Munin]

А знаменатель 1 рассматривать можно?

[Mikhail_K]

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

pppppppo_98 дал "ответ": 4 члена - и свалил.
Всё понятно только Mikhail_K
$350/210=5/3$ В пределах этого числа надо уместить куб знаменателя прогрессии - коль речь идёт о 4-х членах.

Не так уж это и невозможно.
$216, 252, 294, 343$.

-- 20.05.2017, 17:23 --

Прогрессию без ограничения общности считаем возрастающей. Если знаменатель - несократимая дробь $p/q$ и в прогрессии как минимум 5 членов, то $1<\frac{p}{q}\leq\sqrt[4]{\frac{5}{3}}$, что возможно только при $q\geq 8$. Первый член прогрессии должен делиться на $q^4\geq 4096$, что невозможно. Противоречие.

-- 20.05.2017, 17:23 --

Munin в сообщении #1217585 писал(а):

А знаменатель 1 рассматривать можно?

Видимо, нельзя

[pppppppo_98]

DeBill в сообщении #1217545 писал(а):

pppppppo_98
Перебор по всем знаменателям вида $\frac{n+1}{n}$ ?

Да...

Но вот скорость этого перебора мне непонятна...Именно в этом вопрос..К какому классу сложности относится этот алгоритм? Можно ли его улучшить?

-- Сб май 20, 2017 19:23:05 --

Skeptic в сообщении #1217573 писал(а):

pppppppo_98, приведите решение для ЕГЭ. Тогда снимутся все вопросы по постановке задачи.

216,252,294,343....а если не поленитесь и по ссылке моей пройдетесь ...то там и решение есть

-- Сб май 20, 2017 19:25:41 --

Munin в сообщении #1217585 писал(а):

А знаменатель 1 рассматривать можно?

Ну наверное можно...только длина будет 1...
Только не надр мне говорить что если 100500 раз число умножить на 1 то это поменяет длину прогрессии


Так вот проще будет вот ссылка на исходное условие http://images.vfl.ru/ii/1495294401/cde9 ... 291045.jpg
Но интересует не этот конкретный случай [210,350]- он тривиальный... а общий-так как он звучит в первом посте жирным шрифтом..есть ли чо нить побыстрее перебора

[Someone]

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

Ну наверное можно...только длина будет 1...

Нет. Длина конечной последовательности — это количество её членов, а не количество различных значений.

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

Так вот проще будет вот ссылка на исходное условие http://images.vfl.ru/ii/1495294401/cde9%20...%20291045.jpg

Это условие исключает знаменатель прогрессии, равный $1$.

Цитата:

Какое наибольшее количество натуральных чисел можно выбрать на промежутке от $210$ до $350$, чтобы получилась геометрическая прогрессия?

[gris]

Число вида $cn^k$ стартует натуральную прогрессию длиной $k+1$ со знаменателем $m/n$. Для густоты $m=n+1$. То есть по бытовому надо поискать степень числа побольше с показателем побольше и к началу поближе.
Вот $[1000,2000]$
$10^3\to\{1000,1100,1210,1331\}$
$2^{10}\to\{1024,1536\}$
$4^5\to\{1024,1280,1600,2000\}$

[atlakatl]

gris
$8^3\to\{1024,1152,1296,1458\}$