Есть ли формула?

[Kualaderzila]

Существует ли формула остатка или целой части от деления натурального числа на натуральное в явном виде с использованием только сложения/вычитания и умножения/деления? Я гуманитарий, поэтому не бейте, если ошибся с веткой форума, не так поставил вопрос! Спасибо!

[DmitriyMB]

Kualaderzila в сообщении #326334 писал(а):

Существует ли формула остатка или целой части от деления натурального числа на натуральное в явном виде с использованием только сложения/вычитания и умножения/деления? Я гуманитарий, поэтому не бейте, если ошибся с веткой форума, не так поставил вопрос! Спасибо!

Нет

[gris]

Думаю, что нет, как не существует явной (без рекурсии, сумм с переменными пределами, условий, функций) формулы для квадрата числа только через сложение и вычитание.

[shwedka]

А мне кажется, что ответ на вопрос в топике положительный. Я знаю формулу,
включающую, правда, две бесконечные операции, но без тех гадостей, о которых пишет gris.

[meduza]

Для начала автору тему нужно определиться, что он имеет ввиду под "формулой".

[gris]

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

[Бодигрим]

А зачем вам такая формула?

[deep blue]

В справочнике функций остаток по модулю может быть представлен через элементарные функции ( с использованием тангенса и котангенса ).
Я как-то придумал формулу, выражающую остаток c использованием синуса, модуля и суммы с переменным пределом. Причем, в ней можно разложить синус в усеченный ряд Тейлора и таким образом оставить только сумму с переменным пределом, модуль, возведение в целую степень и умножение на Пи. Она основана на выражении $a_k=\frac{\sin(k2\pi/m)+t}{|\sin(k2\pi/m)+t|}$ просуммировав $a_k$ и взяв модуль, получим: $s = |\sum\limits_{k=1}^n a_k|$ а $n\mod m = s либо $n\mod m = m-s$ (взависимости от знака $a_n$) это тоже несложно учесть в итоговой формуле, которую я попозже постараюсь написать.
$t$ - какое-нибудь малое число, меньшее $\sin(2\pi/m)$ видимо подойдет $0.01(2\pi/m)^{2}$ . n,m -положительные целые

[deep blue]

Подкорректировал ошибки в формуле, вроде сейчас стало правильно. Для любых m,n>0

$n\mod m = m/2 + a_n(\sum\limits_{k=0}^{n-1} a_k - m/2)$
где $a_k=\frac{\sin(k\pi/m+0.01\pi/m)}{|\sin(k\pi/m+0.01\pi/m)|}$

Проверим для n=11 и m=5
$a_k=1,1,1,1,1,-1,-1,-1,-1,-1,1,1,...$
индекс $k$ отсчитывается от нуля, тогда:
$11\mod 5 = 5/2 + 1(1 - 5/2) = 1$

[Бодигрим]

Так можно просто взять какую-нибудь периодическую тригонометрическую функцию и обратную к ней. Типа

$$n\pmod m={m\over\pi} \left({\pi\over2}+\arctan\tan \left({\pi n\over m}-{\pi\over2}\right)\right),$$

если я не накосячил с областями определения.

[venco]

Бодигрим в сообщении #326616 писал(а):

Так можно просто взять какую-нибудь периодическую тригонометрическую функцию и обратную к ней.

Рекурсия - см. Рекурсия.
Вы не забыли, что для вычисления тригонометрических функций аргумент сначала приводят к первому периоду, используя операцию получения остатка от деления?
Т.е. теоретически, конечно, можно и синус большого аргумента считать через ряд, т.к. он всегда сходится, но это уже мозахизм.
Проще остаток через вычитание посчитать.

[Бодигрим]

Ну, вроде бы всем очевидно, что самый рациональный с вычислительной точки зрения способ - это посчитать остаток как результат деления с остатком. Но если уж "мадам знает толк в извращениях", то вот вам всякие аналитические формулы. Считайте через ряды или извращайтесь с аналитическими оценками. Это даже иногда плодотворно оказывается - тот же метод тригонометрических сумм в теории чисел.

Раз уж вспомнил про метод тригсумм, то вот еще вариант с комплексными числами:

$$ n\pmod m = {m\ln e^{2\pi i n/m} \over 2\pi i}$$

[Kualaderzila]

Большое спасибо всем, не ожидал такого большого количества таких разных ответов! Отдельные благодарности deep blue и Бодигриму. Возможно, метод тригсумм, поможт мне в моих "извращениях".

[Профессор Снэйп]

$$ n \mathop{\mathrm{mod}} m = n - m \cdot \left\lfloor \frac{n}{m} \right\rfloor $$