Вариант факторизации

[Sonic86]

Александр Побережный писал(а):

Сторона N может быть диагональю нового прямоугольника с такой же площадью

Не понял. В смысле площадь $=N$ и диагональ $=N$?

[Побережный Александр]

Именно так! А что вас смущает?

[hurtsy]

Побережный Александр
Не корысти рад, а в порядке мозговой атаки. У Вас еще есть возможности итерировать от $N$ уменьшая. Собственно можно с любого места начать и в любом направлении двигаться. Боюсь все равно перебор. С уважением,

[Someone]

Побережный Александр в сообщении #347622 писал(а):

Я применил геометрический подход. Число $N=1*N$. Геометрически это прямоугольник со сторонами 1 и N. Сторона N может быть диагональю нового прямоугольника с такой же площадью. Такой прямоугольник можно построить единственным образом. Новый прямоугольник будет иметь стороны $a(1)$ и $\frac{N}{a(1)}$.
В новом прямоугольнике на большей стороне строиться следующий прямоугольник со сторонами $a(2)$ и $\frac{N}{a(2)}$.

А как Вы свою формулу получили?

Побережный Александр в сообщении #347672 писал(а):

Но для меня остается открытым вопрос: будет ли содержать данная цепочка прямоугольников прямоугольник с целыми сторонами при произвольном фиксированном N. Можно ли это доказать?

Доказать это, очевидно, нельзя, поскольку уже в трёх рассмотренных примерах ни одного прямоугольника с целыми сторонами, кроме исходного, не получается. Может быть, удастся доказать, что и никогда не получается, но вряд ли это просто (и непонятно, зачем это нужно, поскольку и так ясно, что надежд крайне мало).

[Sonic86]

Александр Побережный писал(а):

Именно так! А что вас смущает?

Ну тогда для первого прямоугольника стороны равны $1,N$ и диагональ равна $\sqrt{N^2+1}$, а не $N$.
Или я что-то не понял?

[hurtsy]

Sonic86 в сообщении #347861 писал(а):

Александр Побережный писал(а):

Именно так! А что вас смущает?

Ну тогда для первого прямоугольника стороны равны $1,N$ и диагональ равна $\sqrt{N^2+1}$, а не $N$.
Или я что-то не понял?

$N$ - диагональ нового прямоугольника. С уважением,

[Побережный Александр]

hurtsy в сообщении #347668 писал(а):

скорость роста для больших $N$ очень маленькая

Если фиксируется число N, то перебор в начале идет очень медленно. Но чем ближе к концу шаг перебора увеличивается. Чтобы проскочить зону медленного перебора, предлагается следующий вариант. Если предполагать, что цепочка прямоугольников содержит прямоугольники с целыми сторонами, то рассмотрим новое число 2N и для этого числа применим рекурентную формулу, причем $a(k)=2$. Таким образом, мы перескакиваем область медленного роста от 1 до 2. А вычисления остановятся на на делителе числа N больше 2.

-- Вс авг 29, 2010 01:06:20 --

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

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

Три частных примера не являются доказательством. Они могут содержать ошибки или быть исключениями из правила. Поэтому вопрос пока остался.

[dmd]

Побережный Александр в сообщении #347622 писал(а):

Я применил геометрический подход. Число $N=1*N$. Геометрически это прямоугольник со сторонами 1 и N. Сторона N может быть диагональю нового прямоугольника с такой же площадью. Такой прямоугольник можно построить единственным образом. Новый прямоугольник будет иметь стороны $a(1)$ и $\frac{N}{a(1)}$.
В новом прямоугольнике на большей стороне строиться следующий прямоугольник со сторонами $a(2)$ и $\frac{N}{a(2)}$.
Если построить цепочку таких прямоугольников, все они будут иметь одинаковую площадь. Каждый последующий будет толще предыдущего, то есть все больше будет приближаться формой к квадрату.

Думаеца мне, что формула итераций меньшей стороны прямоугольника должна быть такой:
$a(n+1)=\frac{N}{a(n)}\sqrt{\frac{1}{2}\left(1-\sqrt{1-4 \frac{a(n)^4}{N^2}}\right)}$

[hurtsy]

Побережный Александр в сообщении #348044 писал(а):

Чтобы проскочить зону медленного перебора, предлагается следующий вариант. Если предполагать, что цепочка прямоугольников содержит прямоугольники с целыми сторонами, то рассмотрим новое число 2N и для этого числа применим рекурентную формулу, причем .

Мне нравится Ваша задача только напоминанием, что геометрия в математике то же что пешка в шахматах(по Филидору) - душа. В остальном мне приходится возражать. $2N$ - уход от исходной цели факторизовать $N$. Начальная скорость зависит не от абсолютной величины $a(0)$ а от $a(0)/N$. Поэтому на "этапе разгона" можно применять прямой перебор, скажем от 2 до первого $a(0)/N>0.1$. Перебор у Вас до $\sqrt N /N$. Получается, что множество "рекурентности" может быть пустым. С уважением,

[Побережный Александр]

dmd в сообщении #348100 писал(а):

Думаеца мне, что формула итераций меньшей стороны прямоугольника должна быть такой:
$a(n+1)=\frac{N}{a(n)}\sqrt{\frac{1}{2}\left(1-\sqrt{1-4 \frac{a(n)^4}{N^2}}\right)}$

Это то же самое, если вы примените формулу Бхаскара(если я ее правильно назвал).

[Someone]

dmd, у меня сначала тоже возник такой вопрос, но потом я вспомнил, что есть такая формула (она легко выводится; предполагается, что $\beta\neq 0$):

$$\sqrt{\alpha+\beta\sqrt{A}}=\sqrt{\frac{\alpha+\sqrt{\alpha^2-A\beta^2}}2}+\frac{\beta}{|\beta|}\sqrt{\frac{\alpha-\sqrt{\alpha^2-A\beta^2}}2}$$

(не знаю, как она называется; аналогичная формула имеется и для комплексных чисел). С помощью этой формулы легко получается то выражение, которое нам продемонстрировал Побережный Александр.

Побережный Александр в сообщении #348044 писал(а):

Три частных примера не являются доказательством.

Это контрпримеры к Вашему голословному утверждению, что в построенной Вами последовательности обязательно встретятся делители числа $N$.

Побережный Александр в сообщении #348044 писал(а):

Они могут содержать ошибки или быть исключениями из правила.

Если Вы утверждаете, что в моих вычислениях есть ошибка, то будьте любезны продемонстрировать нам правильные вычисления.
Исключениями они могут быть, но тогда Ваше правило должно быть сформулировано с явным указанием исключений и доказано для всех не исключительных $N$. Доказательство, кстати, обязательно должно присутствовать независимо от наличия исключений. Пока мы видим только голословные утверждения.

Побережный Александр в сообщении #348044 писал(а):

Если предполагать, что цепочка прямоугольников содержит прямоугольники с целыми сторонами, то рассмотрим новое число 2N и для этого числа применим рекурентную формулу, причем $a(k)=2$.

Вы действительно верите, что, нагромождая квадратные корни, Вы, начав с $a(0)=1$, на каком-то шаге $k\geqslant 1$ получите $a(k)=2$? Приведите хотя бы один пример. И пусть даже получится не $2$, а хоть какое-нибудь целое число.

[Побережный Александр]

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

Побережный Александр в сообщении #348044 писал(а):

Они могут содержать ошибки или быть исключениями из правила.

Если Вы утверждаете, что в моих вычислениях есть ошибка, то будьте любезны продемонстрировать нам правильные вычисления.
Исключениями они могут быть, но тогда Ваше правило должно быть сформулировано с явным указанием исключений и доказано для всех не исключительных $N$. Доказательство, кстати, обязательно должно присутствовать независимо от наличия исключений. Пока мы видим только голословные утверждения.

Уважаемый Someone! У меня нет цели вас как-то обидеть, но машина не может быть источником доказательства. Она может быть просто поводом поразмышлять. Вот вы дали последовательность результатов вычислений для числа 6 с точностью 100 знаков. Попробуйте построить такую последовательность для числа 6 с точностью 1000 знаков. Сравните, будут ли отличаться эти две последовательности для одного и того же числа 6?