Partitions of a number

In mathematics there are still many open problems, but they are getting more and more bizarre to even be comprehended. One open problem that is easy to grasp is the following: given a positive integer N, let a partition of N be defined as a summation of positive numbers K = n1+n2+…+nn for 1 <= ni <= N, such that K = N. How many such K’s exist? In other words, how many different ways are there to express a number N as a summation of positive numbers? For example, the number 4 can be written as:
1) 1+1+1+1
2) 1+1+2
3) 1+3
4) 2+2
5) 4
Hence, there are a total of 5 different partitions of the number 4. What would be the formula of #Partitions(N)? No one knows… It is known to be exponential, though. Now, switching to algorithms, how do we write a code to generate all the partitions of a number? Code itself is very suitable for functional language: a base case when the target number reaches 0, followed by the induction where we change not only the starting number (avoiding repetition) but the target number (target becomes target-currentNumber). And that’s it. Code is below. Notice that for each interaction we call the same function recursively for ~(N-1), so we have a time complexity of N*(N-1)*(N-2)*…*1, also known as O(N!). Brutal. It can’t run, for instance, for a N >= 100.
        static void CalculatePartitionsAddition(int Target, int startingPoint, string currentNumbers, ref int totalNumberPartitions, bool printPartitions)
        {
            if (Target <= 0)
            {
                if(printPartitions) Console.WriteLine(currentNumbers);
                totalNumberPartitions++;
                return;
            }
            for (int i = startingPoint; i <= Target; i++)
            {
                CalculatePartitionsAddition(Target - i, i, currentNumbers + i.ToString() + " ", ref totalNumberPartitions, printPartitions);
            }
        }

Now a Segway question becomes: what about the partitions using multiplication instead of addition? Code is very similar, but the execution time is way faster because the induction call is gated on the condition that Target be divisible by the currentNumber. That cuts down the search space significantly – to give you an idea, you can easily run the code to get the multiplication partitions for N = 1 billion (result = 22,652 multiplication partitions). Full code (C#) down below:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Partitions
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            if (args.Length != 3 || !Int32.TryParse(args[0], out n))
            {
                Console.WriteLine("Partitions.exe <positive integer> <addition or multiplication or both> <print partitions: yes or no>");
                return;
            }
            bool printPartitions = args[2].Equals("yes", StringComparison.CurrentCultureIgnoreCase);
            int totalNumberPartitions = 0;
            switch (args[1])
            {
                case "addition":
                    CalculatePartitionsAddition(n, 1, "", ref totalNumberPartitions, printPartitions);
                    Console.WriteLine("#Partitions({0}) = {1}", n, totalNumberPartitions);
                    break;
                case "multiplication":
                    CalculatePartitionsMultiplication(n, 2, "", ref totalNumberPartitions, printPartitions);
                    Console.WriteLine("#Partitions({0}) = {1}", n, totalNumberPartitions);
                    break;
                case "both":
                    CompareAdditionAndMultiplicationPartitions(n, printPartitions);
                    break;
            }
        }
        static void CompareAdditionAndMultiplicationPartitions(int maxN, bool printPartitions)
        {
            for (int i = 1; i <= maxN; i++)
            {
                int additionPartitions = 0;
                CalculatePartitionsAddition(i, 1, "", ref additionPartitions, printPartitions);
                int multiplicationPartitions = 0;
                CalculatePartitionsMultiplication(i, 2, "", ref multiplicationPartitions, printPartitions);
                Console.WriteLine("For N = {0}: Addition Partitions = {1} and Multiplication Partitions = {2}", i, additionPartitions, multiplicationPartitions);
            }
        }
        static void CalculatePartitionsAddition(int Target, int startingPoint, string currentNumbers, ref int totalNumberPartitions, bool printPartitions)
        {
            if (Target <= 0)
            {
                if(printPartitions) Console.WriteLine(currentNumbers);
                totalNumberPartitions++;
                return;
            }
            for (int i = startingPoint; i <= Target; i++)
            {
                CalculatePartitionsAddition(Target - i, i, currentNumbers + i.ToString() + " ", ref totalNumberPartitions, printPartitions);
            }
        }
        static void CalculatePartitionsMultiplication(int Target, int startingPoint, string currentNumbers, ref int totalNumberPartitions, bool printPartitions)
        {
            if (Target <= 1)
            {
                if (printPartitions) Console.WriteLine(currentNumbers);
                totalNumberPartitions++;
                return;
            }
            for (int i = startingPoint; i <= Target; i++)
            {
                if (Target % i == 0)
                {
                    CalculatePartitionsMultiplication(Target/i, i, currentNumbers + i.ToString() + " ", ref totalNumberPartitions, printPartitions);
                }
            }
        }
    }
}

Comparing the addition & multiplication partitions for 1 <= N <= 75:

For N = 1: Addition Partitions = 1 and Multiplication Partitions = 1
For N = 2: Addition Partitions = 2 and Multiplication Partitions = 1
For N = 3: Addition Partitions = 3 and Multiplication Partitions = 1
For N = 4: Addition Partitions = 5 and Multiplication Partitions = 2
For N = 5: Addition Partitions = 7 and Multiplication Partitions = 1
For N = 6: Addition Partitions = 11 and Multiplication Partitions = 2
For N = 7: Addition Partitions = 15 and Multiplication Partitions = 1
For N = 8: Addition Partitions = 22 and Multiplication Partitions = 3
For N = 9: Addition Partitions = 30 and Multiplication Partitions = 2
For N = 10: Addition Partitions = 42 and Multiplication Partitions = 2
For N = 11: Addition Partitions = 56 and Multiplication Partitions = 1
For N = 12: Addition Partitions = 77 and Multiplication Partitions = 4
For N = 13: Addition Partitions = 101 and Multiplication Partitions = 1
For N = 14: Addition Partitions = 135 and Multiplication Partitions = 2
For N = 15: Addition Partitions = 176 and Multiplication Partitions = 2
For N = 16: Addition Partitions = 231 and Multiplication Partitions = 5
For N = 17: Addition Partitions = 297 and Multiplication Partitions = 1
For N = 18: Addition Partitions = 385 and Multiplication Partitions = 4
For N = 19: Addition Partitions = 490 and Multiplication Partitions = 1
For N = 20: Addition Partitions = 627 and Multiplication Partitions = 4
For N = 21: Addition Partitions = 792 and Multiplication Partitions = 2
For N = 22: Addition Partitions = 1002 and Multiplication Partitions = 2
For N = 23: Addition Partitions = 1255 and Multiplication Partitions = 1
For N = 24: Addition Partitions = 1575 and Multiplication Partitions = 7
For N = 25: Addition Partitions = 1958 and Multiplication Partitions = 2
For N = 26: Addition Partitions = 2436 and Multiplication Partitions = 2
For N = 27: Addition Partitions = 3010 and Multiplication Partitions = 3
For N = 28: Addition Partitions = 3718 and Multiplication Partitions = 4
For N = 29: Addition Partitions = 4565 and Multiplication Partitions = 1
For N = 30: Addition Partitions = 5604 and Multiplication Partitions = 5
For N = 31: Addition Partitions = 6842 and Multiplication Partitions = 1
For N = 32: Addition Partitions = 8349 and Multiplication Partitions = 7
For N = 33: Addition Partitions = 10143 and Multiplication Partitions = 2
For N = 34: Addition Partitions = 12310 and Multiplication Partitions = 2
For N = 35: Addition Partitions = 14883 and Multiplication Partitions = 2
For N = 36: Addition Partitions = 17977 and Multiplication Partitions = 9
For N = 37: Addition Partitions = 21637 and Multiplication Partitions = 1
For N = 38: Addition Partitions = 26015 and Multiplication Partitions = 2
For N = 39: Addition Partitions = 31185 and Multiplication Partitions = 2
For N = 40: Addition Partitions = 37338 and Multiplication Partitions = 7
For N = 41: Addition Partitions = 44583 and Multiplication Partitions = 1
For N = 42: Addition Partitions = 53174 and Multiplication Partitions = 5
For N = 43: Addition Partitions = 63261 and Multiplication Partitions = 1
For N = 44: Addition Partitions = 75175 and Multiplication Partitions = 4
For N = 45: Addition Partitions = 89134 and Multiplication Partitions = 4
For N = 46: Addition Partitions = 105558 and Multiplication Partitions = 2
For N = 47: Addition Partitions = 124754 and Multiplication Partitions = 1
For N = 48: Addition Partitions = 147273 and Multiplication Partitions = 12
For N = 49: Addition Partitions = 173525 and Multiplication Partitions = 2
For N = 50: Addition Partitions = 204226 and Multiplication Partitions = 4
For N = 51: Addition Partitions = 239943 and Multiplication Partitions = 2
For N = 52: Addition Partitions = 281589 and Multiplication Partitions = 4
For N = 53: Addition Partitions = 329931 and Multiplication Partitions = 1
For N = 54: Addition Partitions = 386155 and Multiplication Partitions = 7
For N = 55: Addition Partitions = 451276 and Multiplication Partitions = 2
For N = 56: Addition Partitions = 526823 and Multiplication Partitions = 7
For N = 57: Addition Partitions = 614154 and Multiplication Partitions = 2
For N = 58: Addition Partitions = 715220 and Multiplication Partitions = 2
For N = 59: Addition Partitions = 831820 and Multiplication Partitions = 1
For N = 60: Addition Partitions = 966467 and Multiplication Partitions = 11
For N = 61: Addition Partitions = 1121505 and Multiplication Partitions = 1
For N = 62: Addition Partitions = 1300156 and Multiplication Partitions = 2
For N = 63: Addition Partitions = 1505499 and Multiplication Partitions = 4
For N = 64: Addition Partitions = 1741630 and Multiplication Partitions = 11
For N = 65: Addition Partitions = 2012558 and Multiplication Partitions = 2
For N = 66: Addition Partitions = 2323520 and Multiplication Partitions = 5
For N = 67: Addition Partitions = 2679689 and Multiplication Partitions = 1
For N = 68: Addition Partitions = 3087735 and Multiplication Partitions = 4
For N = 69: Addition Partitions = 3554345 and Multiplication Partitions = 2
For N = 70: Addition Partitions = 4087968 and Multiplication Partitions = 5
For N = 71: Addition Partitions = 4697205 and Multiplication Partitions = 1
For N = 72: Addition Partitions = 5392783 and Multiplication Partitions = 16
For N = 73: Addition Partitions = 6185689 and Multiplication Partitions = 1
For N = 74: Addition Partitions = 7089500 and Multiplication Partitions = 2
For N = 75: Addition Partitions = 8118264 and Multiplication Partitions = 4

And an interesting observation: the multiplication partition is nothing but the decomposition of a number into its prime factors. Running the code for N = 1000000111 (cmd line: Partitions.exe 1000000111 multiplication yes), the result is:

11 90909101
1000000111
#Partitions(1000000111) = 2