An interesting (slow) factoring algorithm Thursday, Apr 7 2011 

Math.CO and Math.NT and Math.REC and Mathematics , , , , , , mixedmath 3:37 am

After my previous posts (I, II) on perfect partitions of numbers, I continued to play with the relationship between compositions and partitions of different numbers. I ended up stumbling across the following idea: which numbers can be represented as a sum of consecutive positive integers? This seems to be another well-known question, but I haven’t come across it before.

(more…)

 

Perfect Partitions II Thursday, Mar 31 2011 

Expository and Math.CO and Math.REC and Mathematics mixedmath 12:50 am

In continuation of my previous post on perfect partitions, I seek to extend the previous result to all numbers, not just one less than a prime power.

Previously, we had:

The number of perfect partitions of the number p^\alpha -1 is the same as the number of compositions of the number \alpha .

Today, we will find a relation for the number of perfect partitions of any positive integer n . The first thing we note is that every number n can be written uniquely as:

n = {p_1}^{\alpha _1}{p_2}^{\alpha _2} *...* {p_n}^{\alpha_n} - 1 , where each of the p are distinct primes.

Parallel to the last result, we can see that the number of perfect partitions of the number {p_1}^{\alpha _1}{p_2}^{\alpha _2} *...* {p_n}^{\alpha_n} - 1 is the same as the number of ways to factor

\dfrac{x^{{p_1}^{\alpha _1}{p_2}^{\alpha _2} *...* {p_n}^{\alpha_n} - 1} - 1}{x - 1} .

This can immediately be proved by extending the previous post: still use finite geometric series and the positivity of the terms to show that each exponent can be reached in exactly one way. The different factors would again be of the form:

\dfrac{1 - x^\gamma}{1-x^\delta} where \delta | \gamma .

In this fashion, we see that the number of perfect partitions are the same as the number of ordered factorizations of {\alpha _1}{\alpha _2} *...* {\alpha_n}. But we haven’t really considered this yet. How many ordered factorizations are there? This is unfortunately beyond the scope of this post, but Sloane’s has that sequence here, and there is a Dirichlet generating function: f(s) = \dfrac{1}{2 - \zeta(s)}.

As an aside that made more sense in the original post, I consider the number of compositions of a number. How many compositions are there for a number n?

I hadn’t seen this before, but upon consideration I see that it is a very simple exercise that one might encounter. Imagine we are thinking of the number of compositions of n. Then n = 1 + 1 + 1 ... + 1. But then each ‘+’ symbol might be replaced by a separator, so that for example 1 + 1 + 1 might be 1 + 1, 1 = 2, 1. So we see that there are always 2^{n-1} different compositions of the number n. So we now know the number of partitions of each number n!

 

Perfect Partitions Monday, Mar 28 2011 

Expository and Math.CO and Math.REC and Mathematics , , , , , , mixedmath 11:32 pm

I was playing with a variant of my Containers of Water question where we were instead interested in solid weights on a scale. It occurred to me that, as is often the case, I should consider easier problems first and see what comes of them. Ultimately, this led me down a path towards the idea of a ‘perfect partition’ and a few papers published in the late 1800s by MacMahon. Here’s how that went:

(more…)