Vipul: Created page with '==Statement== Suppose $m$ and $n$ are natural numbers. The '''coprime partition maximization problem''' for $m$ with respect to $n$ a...'

2009-04-30T21:26:19Z

Created page with '==Statement== Suppose <math>m</math> and <math>n</math> are natural numbers. The '''coprime partition maximization problem''' for <math>m</math> with respect to <math>n</math> a...'

New page

==Statement==

Suppose <math>m</math> and <math>n</math> are natural numbers. The '''coprime partition maximization problem''' for <math>m</math> with respect to <math>n</math> asks for the maximum possible value of the smallest part in any [[unordered integer partition]] of <math>m</math> for which every part is relatively prime to <math>n</math>.

==Particular cases==

===Best and worst case===

The best case for this problem is when <math>n</math> and <math>m</math> are relatively prime. In this case, the partition is the single-part partition, with the maximum being <math>m</math> itself.

The worst case for this problem is when <math>n</math> is divisible by all the primes less than or equal to <math>m</math> (in other words, the [[square-free kernel]] of the [[factorial]] of <math>m</math> divides <math>n</math>). In this case, the only permissible partition is the all ones partition, and the corresponding maximum is <math>1</math>.

===Vinogradov's theorem and its implications on partitions===

{{fillin}}

===The squareroot-size prime trick===

If <math>p</math> and <math>q</math> are two primes whose product is less than <math>m</math> such that neither divides <math>n</math>, then, by the [[postage stamp problem]], we can write <math>n</math> as a positive integer combination of <math>p</math> and <math>q</math>. Thus, <math>\operatorname{min}(p,q)</math> is a lower bound on the maximum possible value.

Coprime partition maximization problem - Revision history

Vipul: Created page with '==Statement== Suppose m and n are natural numbers. The '''coprime partition maximization problem''' for m with respect to n a...'

Vipul: Created page with '==Statement== Suppose $m$ and $n$ are natural numbers. The '''coprime partition maximization problem''' for $m$ with respect to $n$ a...'