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

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

Уважаемые софорумники, размышляя о факторизации больших чисел получил результат с которым хочу поделиться.
Пусть имеем число N, перебирая простые числа до $\sqrt{N}$ мы находим делитель N либо убеждаемся, что число N - простое. Для небольших чисел такой алгоритм проходит, но для достаточно больших чисел сам перебор становится затруднительным, очень много времени уходит на процесс. Плюс к этому добавляется время на определение самих простых чисел.
Путем нехитрых рассуждений получил рекурентную формулу, которая на определенном шаге выдает делитель указанного числа N. Во эта формула:
$a(n+1)=\frac{(\sqrt{N^2+2*N*a(n)^2} -\sqrt{N^2-2*N*a(n)^2)}}{2*a(n)}$, где $a(0)=1$.
Процесс завершается, если $a(n)>\sqrt{N}$.
В этой процедуре полностью отсутствует процесс поиска простых, к тому же
с каждым шагом растет разность $a(n+1)-a(n)$.

[Sonic86]

Че-то неправильно, $N=65$ сразу дает стационарную последовательность $1,000118$

-- Чт авг 26, 2010 15:45:38 --

да и вообще они так все у меня стабилизируются.

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

У вас точность не достаточная. Очень быстро ошибки накапливаются.

[hurtsy]

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

Че-то неправильно, $N=65$ сразу дает стационарную последовательность $1,000118$

-- Чт авг 26, 2010 15:45:38 --

да и вообще они так все у меня стабилизируются.

Рост очень медленный. Да и, имхо, целочисленные значения эта рекурентная формула не дает.

assasin в сообщении #347438 писал(а):

Что-то запашок у этой формулы...Теоремой Ферма попахивает...

Не-а. Возможно шутка, возможно троль.
Хорошо бы, топик-стартер нашел бы все делители числа 100! и сообщил время счета и тактовую частоту процессора.

[venco]

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

Во эта формула:
$a(n+1)=\frac{(\sqrt{N^2+2*N*a(n)^2} -\sqrt{N^2-2*N*a(n)^2)}}{2*a(n)}$, где $a(0)=1$.
Процесс завершается, если $a(n)>\sqrt{N}$.

Приведите Ваш вариант последовательности для, например, $N=4$ и $N=6$.

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

venco в сообщении #347480 писал(а):

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

Во эта формула:
$a(n+1)=\frac{(\sqrt{N^2+2*N*a(n)^2} -\sqrt{N^2-2*N*a(n)^2)}}{2*a(n)}$, где $a(0)=1$.
Процесс завершается, если $a(n)>\sqrt{N}$.

Приведите Ваш вариант последовательности для, например, $N=4$ и $N=6$.

В этом как раз и проблема для меня показать всю последовательность для конкретного числа. Появляется много корней и я не могу упростить выражение. Есть ли возможность перевести рекурентную формулу в обычную? Как, например, ряд чисел Фиббоначи.

[venco]

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

В этом как раз и проблема для меня показать всю последовательность для конкретного числа.

Вы хотя бы численно посчитайте - там делителями и не пахнет.

[Someone]

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

Путем нехитрых рассуждений получил рекурентную формулу, которая на определенном шаге выдает делитель указанного числа N. Во эта формула:
$a(n+1)=\frac{(\sqrt{N^2+2*N*a(n)^2} -\sqrt{N^2-2*N*a(n)^2)}}{2*a(n)}$, где $a(0)=1$.
Процесс завершается, если $a(n)>\sqrt{N}$.

Ерунда это всё, никаких простых делителей так не получается.
И прежде всего нужно заметить, что подкоренное выражение во втором корне становится отрицательным при $a>\sqrt{\frac N2}$, так что если наименьший простой делитель больше $\sqrt{\frac N2}$, то мы его и не получим.
Численный эксперимент с использованием системы компьютерной математики Mathematica 5.1 для $N=6$ дал такой результат:

1 1.014611872354576488857608608305853341919663026964091127678921391652905656360285047622432940409856917
2 1.030372918425301562651044413949148909765888509014193678337941579725468906289566818394177557910234138
3 1.047458232847430207611718991659457615152068854982857708000385867768669916428064466997535127216464072
4 1.066084526681627200595058050568228650377316364109273637199912476931968947550467929176549150828368554
5 1.086524167118275866865764708691191076769886501148660089310489566278416546970204168903467421052253003
6 1.109125608903990069614988598454603775453407942614297513603039810140277271613381142648348631103615541
7 1.134344032214090468977456296913898146986630758857830414237055806651080155685500839310718446811971756
8 1.162788938833654094554336853854949796758460534685608068721569592014944426094027887616294659470989654
9 1.195301293301719918295585580603316544784250164211353451815296007255663420650756754072226691778050341
10 1.233085195133445231021506683965654452198243760081228258932499628733447088889307833904083564571687247
11 1.277947708051978520176114185946876757085941165048564190786341216014612837458209669846993134689620912
12 1.332774038146921783394198689362228921391679793509062377700414372448707739971647836802233198539755504
13 1.402582927958756474494299515912517445192271230988591894355909491155667675961099627254843149356216581
14 1.497294731209751696939166915963434669546870688962123022936884345485546901919762332682943840709502774
15 1.641276310570229536077255639552221459501712970077830488806386658602174038683076891489720507516943737
16 1.934168863221923636633144413840958637217524755976083592099428456013760254806970565784806256798992741
17 2.325030740958322694164085729959856054399253391733806157410665405546410812914030411733820971338273574-
  -0.770864484587785996114129824353277495482288589815753968388655740824554691738961664498895117254778707 i

И где здесь хоть один простой делитель числа $N=6$?
Подчёркиваю, что вычисления выполнялись точно, а результаты распечатаны с точностью 100 значащих цифр.

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

Спасибо за полезную информацию! Видимо ошибка в логических рассуждениях...

[alex1910]

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

Не-а. Возможно шутка, возможно троль.
Хорошо бы, топик-стартер нашел бы все делители числа 100! и сообщил время счета и тактовую частоту процессора.

Делители 100! выписываются на бумажке за пять минут.
Без компьютера.

Вы шутите или тролль? :)

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

Уважаемый Someone, можно вас попросить провести аналогичные вычисления для числа 33?

[Someone]

Вычисления-то сделать нетрудно, да писанины потом много. Ну ладно.
Сначала для $N=8$
Попытку точного вычисления мне до конца довести не удалось. Вы же сами пробовали подставлять и видели, что радикалы громоздятся на радикалы и радикалами погоняют. В результате вычисления начинают катастрофически замедляться.
Это - команда программы Mathematica. Ваше число $N$ здесь обозначено $\mathrm{NN}$, так как символ $\mathrm N$ занят для обозначения функции, вычисляющей выражение с заданной точностью. Результаты я привожу выборочно, так как их объём очень большой.
$\mathrm{NN=8;a=1;For[k=1,2a^2\leq NN,k++,a=\frac{\sqrt{NN^2+2a^2NN}-\sqrt{NN^2-2a^2NN}}{2a};Print[k,''\ '',N[a,100]]]}$

1 1.008034339861824805763454654450807736995626211602290192430180531917175817458009724666536443243067399
2 1.016404471602633948450791398129272044383930892302930148810446162722586739364848419181380540571185370
3 1.025136639013782927502687304811932712589305644528113600610257677726429985301428391785910901211145467
4 1.034260164599902179364990770339513865369104346315043137420504688011258303769191750379036104490044383
5 1.043807940799878330143322392140874957801197434373130157853529855314623848980205173904042985083100449
...
17 1.212510355704249188329673444004618289702287203159409284438719081311873933275531950622516867700240632
18 1.234301251520168460683010879569698589914295090297227590462718602272146422546975997817254047352378456
Aborted

Поэтому вместо точного вычисления нужно ограничиться приближённым с достаточной точностью. Система Mathematica контролирует ошибки округления и выводит результат с реальной точностью. Обратите внимание, что в последующих таблицах количество цифр к концу уменьшается.
$\mathrm{NN=8;a=1;For[k=1,2a^2\leq NN,k++,a=N[\frac{\sqrt{NN^2+2a^2NN}-\sqrt{NN^2-2a^2NN}}{2a},100];Print[k,''\ '',N[a,100]]]}$

1 1.008034339861824805763454654450807736995626211602290192430180531917175817458009724666536443243067399
2 1.016404471602633948450791398129272044383930892302930148810446162722586739364848419181380540571185370
3 1.025136639013782927502687304811932712589305644528113600610257677726429985301428391785910901211145467
4 1.03426016459990217936499077033951386536910434631504313742050468801125830376919175037903610449004438
5 1.04380794079987833014332239214087495780119743437313015785352985531462384898020517390404298508310045
...
17 1.21251035570424918832967344400461828970228720315940928443871908131187393327553195062251686770
1.2343012515201684606830108795696985899142950902972275904627186022721464225469759978172540474
19 1.2582383773321788764481573700244028385762853331672064087466850651245594986034650653069547286
...
28 1.74848158363359761041898390083447251273843883661240318925744772771128430377337406887724
29 1.9280176418464445445925878668199736899289970663418362127568480684228486329535986629440
30 2.3301174055882199096527870921281292621390504210763423225868168338629473952032006458966

Здесь, как видите, первоначальной точности в 100 значащих цифр с большим запасом хватило, хотя в последнем (тридцатом) числе их получилось заметно меньше (на 14).
Ничего похожего на делители числа $N=8$, как видите, нет, а количество итераций очень большое (аж 30).

Теперь для $N=33$, о котором Вы спрашивали.
$\mathrm{NN=33;a=1;For[k=1,2a^2\leq NN,k++,a=N[\frac{\sqrt{NN^2+2a^2NN}-\sqrt{NN^2-2a^2NN}}{2a},100];Print[k,''\ '',N[a,100]]]}$

1 1.000459876246952656339468152412460188536815201022157024349986281936192810416165281464863492995955181
2 1.000920812264952181211013985358355925567589790964230218684300445667462747553158183861822487276315307
3 1.001382812459004578642208870363578011686013841488098377191567112073166629887432855095998656612507057
4 1.00184588126061592245081102325518521892825919714669520787538699665824483090438283565880674809786130
5 1.00231002312800124038121513756821336124872549263335357533430708868289692108755721514977586815138555
...
204 1.125
205 1.13
206 1.13
207 1.1
208 1.1
209 1.
210 1.
211 0.
Power::infy: Infinite expression 1/0. encountered. More…
∞::indet :  Indeterminate expression 0. ComplexInfinity encountered. More…
212 Indeterminate

На 211 итерации погрешности округления "съели" все 100 цифр. Конечно, ничего не стоит заказать 1000 цифр, и всё получится. Результаты будем печатать со 100 цифрами.
$\mathrm{NN=33;a=1;For[k=1,2a^2\leq NN,k++,a=N[\frac{\sqrt{NN^2+2a^2NN}-\sqrt{NN^2-2a^2NN}}{2a},1000];Print[k,''\ '',N[a,100]]]}$

1 1.000459876246952656339468152412460188536815201022157024349986281936192810416165281464863492995955181
2 1.000920812264952181211013985358355925567589790964230218684300445667462747553158183861822487276315307
3 1.001382812459004578642208870363578011686013841488098377191567112073166629887432855095998656612507057
4 1.001845881260615922450811023255185218928259197146695207875386996658244830904382835658806748097861297
5 1.002310023128001240381215137568213361248725492633353575334307088682896921087557215149775868151385549
...
210 1.129639936436405370335281140852418044035635571939603751009099740886283947286621494720200398275789775
211 1.130486737317806030718912672777333809000681115135812266698567028840030658429416886861188711999856620
212 1.131336723562924633735405156693105980220459433000082602244979191991630954690209813687150215056444503
...
509 1.988707429008923005989891243016150076763293185495661301844663952456282548129279797591526720564626142
510 2.003361322821153960366160101799556967595669668998533642289161042844695770169144303233443843899844952
...
536 2.927089610875686609358998462169006503756818244439030037255948912143039254937284009162680404921324289
537 3.039654704317656780516439355282184367255977319336084163029919926760887392591759526120004350997085347
538 3.178997720235709111224771569484930456850338963602391945245989011185748231663296342756810050435471700
539 3.359853535746898061065303959229273006368467487050391411558330354329527458010827355428991534629312811
540 3.613233166498359470367613422735499254369490419476005131488485965056607607181747862125307069392281153
541 4.025269791651694741918573307812997942793262133017198004382795089795141645736058444271262313343996215
542 5.220704685919353626802865779819466718094067675702761422273679918554857710337791951903668440272384660

Но вместо этого можно преобразовать Вашу формулу так, чтобы потеря точности была меньше.
$\mathrm{NN=33;a=1;For[k=1,2a^2\leq NN,k++,a=N[\frac{2a*NN}{\sqrt{NN^2+2a^2NN}+\sqrt{NN^2-2a^2NN}},100];Print[k,''\ '',N[a,100]]]}$

1 1.000459876246952656339468152412460188536815201022157024349986281936192810416165281464863492995955181
2 1.000920812264952181211013985358355925567589790964230218684300445667462747553158183861822487276315307
3 1.001382812459004578642208870363578011686013841488098377191567112073166629887432855095998656612507057
4 1.001845881260615922450811023255185218928259197146695207875386996658244830904382835658806748097861297
5 1.002310023128001240381215137568213361248725492633353575334307088682896921087557215149775868151385549
...
537 3.039654704317656780516439355282184367255977319336084163029919926760887392592
538 3.178997720235709111224771569484930456850338963602391945245989011185748231663
539 3.35985353574689806106530395922927300636846748705039141155833035432952745801
540 3.61323316649835947036761342273549925436949041947600513148848596505660760718
541 4.02526979165169474191857330781299794279326213301719800438279508979514164574
542 5.2207046859193536268028657798194667180940676757027614222736799185548577103

Здесь погрешности округления "съели" 24 цифры.
Как видите, по сравнению с $N=8$ количество итераций возросло в 18 раз, и также никаких делителей не обнаружилось. А с чего Вы взяли, что таким методом можно находить делители?

Думаю, что этого достаточно. Если Вам хочется ещё поэкспериментировать, сделайте это самостоятельно.

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

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

[hurtsy]

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

Попробую изложить ход моих рассуждений.

Да, красота $-$ страшная сила. Я был неправ по поводу "шутка или троль". Прошу прощения. Имхо, у Вашего красивого итерационного процесса два "противопоказания". Ваш процесс дискретный. Второе скорость роста для больших $N$ очень маленькая. Кажется геологи, говорят - "Не все то золото - что блестит". С уважением,

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

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