# Partition minimizing maximum of Euler's totient function across terms

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.

-
Here's a suggestion, I don't know how good it is. Precompute a list of "sparsely totient numbers," see oeis.org/A036913. 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