Разложение числа на взаимнопростые составляющие

[j0sur]

Если написал не туда, пожалуста, перенесите в нужную ветку.
Есть число, допустим 19. Нужно разложить его на взаимнопростые числа, сумма которых будет равна 19(в данном случае 3, 4, 5, 7).
Реальные числа будут иметь размер 9-15 знаков...
Заранее благодарен за помощь.

[ИСН]

Для большинства чисел формально подходит такой вариант: два слагаемых, $\lfloor {n-1\over2}\rfloor$ и $\lfloor {n\over2}\rfloor+1$. Нравится? Нет? Почему?

[j0sur]

Извините, забыл написать, что таких чисел должно быть 4. Если использовать Ваш метод, то есть верояность получить два четных и два нечетных числа в результате.
А вот еще такой вопрос, наверняка есть числа, которые невозможно разложить на 4 взаимнопростых. Как их быстро отсеять?

[ИСН]

Мой (предыдущий) метод давал два числа, так что с учётом вновь появившегося условия использовать его невозможно вовсе, а не "есть вероятность". Но ладно.
Теперь так: $1,\,1,\,1,\,n-3$. Их четыре и они взаимно просты. Годится? Нет?

[j0sur]

ИСН в сообщении #605216 писал(а):

Мой (предыдущий) метод давал два числа, так что с учётом вновь появившегося условия использовать его невозможно вовсе, а не "есть вероятность". Но ладно.
Теперь так: $1,\,1,\,1,\,n-3$. Их четыре и они взаимно просты. Годится? Нет?

Тоже нет, к сожалению. Нужно 4 максимально большие и не равные 1-це.

[Someone]

Что значит "максимально большие"? Чтобы наименьшее было как можно больше?

[j0sur]

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

Что значит "максимально большие"? Чтобы наименьшее было как можно больше?

Да, если есть возможность.

[Someone]

Может быть, попробовать рассмотреть отдельно числа вида $n=12k+r$ для $0\leqslant r<12$. Не утверждаю, что $12$ - наилучший вариант.

[ИСН]

Тогда так. Для $n=8k$ разложение будет: $2k-p,\,2k-1,\,2k+1,\,2k+p$, где p - наименьшее простое, не делящее n. Для остальных вариантов (8k+1, 8k+2...) можно подобрать что-нибудь примерно в этом же роде, но возиться надо будет долго.

[j0sur]

ИСН в сообщении #605317 писал(а):

Тогда так. Для $n=8k$ разложение будет: $2k-p,\,2k-1,\,2k+1,\,2k+p$, где p - наименьшее простое, не делящее n. Для остальных вариантов (8k+1, 8k+2...) можно подобрать что-нибудь примерно в этом же роде, но возиться надо будет долго.

Отличный вариант, спасибо. А вот если я захочу разложить число уже на 6 взаимнопростых, то мне просто нужно будет представить его в виде 12k, найти еще одно простое q и найти 2k-q и 2k+q?

[ИСН]

Для тех чисел, которые делятся на 12 - да. Только там не какое-нибудь "ещё одно", а именно следующее простое.