» Образование

[The Chief]

a^3-(a-1)^3 <= b, где a, b - целые положительные. Нужно решение в общем виде, a<=f(b).

[Ашатан]

Фу, блин... Дошла до a^2-a и зависла.

[The Chief]

Упрощаем, 3a^2−3a+1 <= b , а дальше?

Всё, нашёл, ещё проще, a^2-a <= (b-1)/3, т.е. a <= int (sqrt ((b-1)/3)

[b70]

Сообщение от The Chief Упрощаем, 3a^2−3a+1 <= b , а дальше?

решаете квадратное уравнение, очевидно

[The Chief]

Ашатан, спасибо, навели на путь истинный.

---------- Сообщение добавлено 14.11.2013 13:22 ----------

b70, я-я, натюрлих. Сам сообразил.

[b70]

The Chief, ответ сверим?)))

[The Chief]

b70, мне нужен был оценочный результат для положительных целых a. На самом деле:
1 <= a <= (1 + sqrt( 1 + 4*c ))/2, где c = (b-1)/3.

[b70]

Сообщение от The Chief b70, мне нужен был оценочный результат для положительных целых a. На самом деле: a <= (1 +- sqrt( 1 + 4*c ))/2, где c = (b-1)/3.

Вероятно, имелось ввиду:
((1 - sqrt( 1 + 4*c ))/2) <= a<= ( (1 + sqrt( 1 + 4*c ))/2), при b>=1/4 )))

[The Chief]

b70, да, пардон. Именно так, только нижняя граница = 1. b>=1/4 входит в условие «a, b - положительные целые».

PS: нужно было для оценки верхней границы цикла for a = 1 to … при известном b. Для больших b оценка int(sqrt(b/3)) даёт хороший результат.

PPS: ещё бы попробовать прикинуть нижнюю границу (начало цикла)… но я там зависимость формульно не могу вывести.

[panda-34]

Дополнительно стоит проверить в целых числах равенство b == 1 - 3 a + 3 a^2, при вычислении "<=" с плавающей точкой, мимо "=" можно и пролететь.

[b70]

Сообщение от The Chief PPS: ещё бы попробовать прикинуть нижнюю границу (начало цикла)… но я там зависимость формульно не могу вывести.

при подстановке b=1 в нижнюю границу, начало цикла по целому а=1... вроде так.

[The Chief]

b70, нет, это неравенство определяет только верхнюю границу цикла. Нутром чую, что нижняя — кубический корень из b (from b^(1/3) to sqrt(b/3), работает для b>27, у меня b >> 1000), но доказать не могу.

---------- Сообщение добавлено 14.11.2013 15:12 ----------

panda-34, настолько точно не надо. Хотя да, проверить надо, это будет особый случай и вообще в цикл можно будет не входить.

[b70]

The Chief, а, понял. Ну, чем мог...

[The Chief]

Есть, нашёл ограничение на начало цикла. from (b/2)^(1/3) to (b/3)^(1/2), плюс проверка нескольких особых случаев. Всем спасибо. Пошёл писать код.

[b70]

Сообщение от The Chief Есть, нашёл ограничение на начало цикла. from (b/2)^(1/3) to (b/3)^(1/2), плюс проверка нескольких особых случаев. Всем спасибо. Пошёл писать код.

Не за что.
Однако, вероятно, имелось ввиду следующее:
from (int((b/2)^(1/3))+1) to (int((b/3)^(1/2))
Удачи!!

[The Chief]

Сообщение от b70 int

Да. Оптимизация, блин, такая оптимизация…