Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where $\phi$ is Euler's totient function.

What might a smart algorithm for this look like? I can approach this with raw CPU power and metaheuristic search, but maybe the partition can be found analytically? I am mostly interested in $N$ = 8, 16, 32, 64, 128 in case that somehow simplifies the problem.

share|cite|improve this question
Here's a suggestion, I don't know how good it is. Precompute a list of "sparsely totient numbers," see Given $N$, find the largest sparsely totient number $x$ not exceeding $2^N$, let $t_M=x$, then apply recursively to $2^N-x$ to get $t_{M-1},\dots,t_2$, then let $t_1$ be whatever's left over. Maybe instead of largest s.t.n not exceeding $2^N$, use largest s.t.n not exceeding $2^N/M$. – Gerry Myerson Jan 18 '13 at 4:46
It maybe a great idea. I read that the ith primorial multiplied by the ith prime is sparsely totient, and used that to quickly build a list (not all sparse totients, but for rough minimization may be OK). I tried building the partition for $2^{64}$ in the style of Euclid's algorithm for GCD -- I took the biggest number in the list < $2^{64}$ and took the remainder of dividing by it, then took the biggest sparse totient in the list under the remainder and took the remainder of dividing by it, etc. etc. Turns out a linear combination of those sparse totients exactly partitioned it. Coincidence? – Joseph Garvin Jan 22 '13 at 15:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.