Числовой ряд натуральных дробей.

[Belih-Serg]

Приветствую всех!
Не занимался математикой лет двадцать, а недавно пришлось. Вот такая задача (не из учебников или олимпиад, а из практических потребностей):
Имеется два ряда чисел
$D_k=Dn_0-(S+4k)^2$, где $k$ - натуральные числа, $S$ - постоянная для данного ряда величина;
$P_k=Pn_0+192k$
При каких $k$ выражение $\frac{D_k}{P_k}$ - принимает целочисленные значения.
Подскажите, пожалуйста, методику решения такой задачи. Самостоятельно ничего придумать не смог.

[gris]

А что такое $Dn_0$ и $Pn_0$?

[Sonic86]

Т.е. у Вас выражение типа $\frac{Ak^2+Bk+C}{Dk+E}$ и надо определить, когда оно целое? Если да, то надо умножить на некую константу, поделить многочлены с остатком и задача сведется к задаче вида: когда дробь $\frac{K}{Mk+N}$ целая. Просто решить можно так: перебрать все делители числителя дроби. Или даже перебрать все значения знаменателя так, чтобы $|Mk+N|\leqslant |K|$.
Все константы надо знать заранее.

[Belih-Serg]

$Dn_0=16; Pn_0=-16$ - начальные значения рядов. Могут быть другими. $S=3$
Это конкретные ряды. Значения выбрал с близким решением.
Можно ли обойтись без перебора? Он может оказаться очень большой. Может быть, удастся свести к решению квадратного уравнения? Первый ряд квадратичный, второй линейный.

[ИСН]

Перебор по всем делителям конкретного числа никак не может быть очень большим. Проблемой может быть его факторизация, но это тоже вряд ли.

[gris]

В Вашем конкретном случае можно числитель и знаменатель разложить на множители:
$\dfrac {-(4k-1)(4k+7)}{16(12k-1)}$, откуда видно, что дробь несократима до целого.
Хотя и без разложений видно, что первый ряд состоит из нечётных чисел, а второй из чётных.

[Belih-Serg]

Ошибся. $Dn_0=25$

[gris]

Тогда $\dfrac {-(k+2)(2k-1)}{2(12k-1)}$ Знаменатель чётный, значит $k=2n$

Тогда $\dfrac {(n+1)(4n-1)}{(24n-1)}$

[Belih-Serg]

С сомножителями уже лучше. Мне это нравится. Тогда вопрос: можно ли как-то формализовать построение сомножителей и делителя, если начальные значения будут меняться? Т.е. я хочу узнать, можно ли для каждой из скобок автоматически вычислить коэфф. перед $k$ и второе слагаемое?

[gris]

Ну если только $Dn_0$ точный квадрат. Мне кажется, что при произвольных значениях параметров получить общий ответ нельзя. Да и при конкретных определить несократимость легко только в некоторых случаях.

В общем виде дробь равна $-\dfrac{16k^2+8Sk+S^2-Dn_0}{Pn_0-192k}$

В общем случае её нельзя разложить на какие-то множители, хотя и разложение помогает только в очень частных случаях.

[Sonic86]

Belih-Serg в сообщении #622918 писал(а):

С сомножителями уже лучше. Мне это нравится. Тогда вопрос: можно ли как-то формализовать построение сомножителей и делителя, если начальные значения будут меняться? Т.е. я хочу узнать, можно ли для каждой из скобок автоматически вычислить коэфф. перед $k$ и второе слагаемое?

Выделение множителей в числителе работает не всегда, а алгоритм Евклида работает всегда. Вам не нужно выделение сомножитилей, Вам нужен алгоритм Евклида. Зачем искусственно усложнять себе жизнь?

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

надо умножить на некую константу

точнее так: умножить числитель и знаменатель на нужную константу - получится эквивалентная задача.

[Belih-Serg]

Ещё немного наберусь наглости поэксплуатировать умные головы: Можно ли поподробней расписать, как это сделать, если $Dn_0$ точный квадрат?

Цитата:

Вам нужен алгоритм Евклида

Алгоритм Евклида я не знаю. Можно кратко пояснить?

Цитата:

умножить числитель и знаменатель на нужную константу - получится эквивалентная задача.

Как вычислить эту константу?
Поясняю: то, о чём я спрашиваю, надо реализовать в программе, поэтому "ручное" построение формул нежелательно. Но я с удовольствием посмотрю на ваши предложения, вдруг и у меня что-то в голове поумнеет.

[EtCetera]

Belih-Serg

Belih-Serg в сообщении #622926 писал(а):

Алгоритм Евклида я не знаю. Можно кратко пояснить?

Кратко поясняю: алгоритм Евклида.

[Belih-Serg]

Спасибо, понял. Алгоритм Евклида - это название нахождения НОД. Прошу прощения за незнание элементарных понятий. Ну не математик я. Как раз от него я и хочу избавиться, так же как и от деления.

[Belih-Serg]

Задача возникла при реализации алгоритма факторизации чисел. Это деление членов числовых рядов существенно замедлит работу программы, когда значения делителя превысят разрядность операций процессора. Посоветуйте, как обойти деление. Пытаюсь рассмотреть алгоритм, когда предполагаемое частное каждый раз корректируется и его произведение с делителем сравнивается с делимым. Если равно, это то, что мы ищем - целочисленное частное, иначе увеличиваем или уменьшаем частное на единицу, чтобы приблизиться к делимому. Для очень больших чисел такой вариант может оказаться трудоёмким.
На давно заглохшей ветке форума (здесь) Iosif1 безуспешно предложил алгоритм факторизации. Этот алгоритм работает, и особенно быстро для небольших сомножителей. Программа для него уже опробована и даёт неплохие результаты. Пока с числами в сетке процессора, но можно легко увеличить разрядность.
Таланты и гении форума помогите обойти деление.