Ramanujan’s Third Problem

Posted on

A person born here would revolutionize mathematics forever. Would give a different perspective to how we interpret infinite sums and series. Would suggest new ways of thinking about difficult mathematical problems such as the score problem. Someone born here, raised by their mother alone, with no higher education, no computer to help them, just through hard, hard work, would accomplish so much in so little time.

I continue to be amazed by the work and life of Srinivasa Ramanujan. I think one of his most important contributions was to come up with a formula for the partition problem:

What fascinates me most is that mathematicians like him never had the power of computers at their disposal. One of Ramanujan’s very interesting anecdotes happened when he was already very ill in England and was visited by GH Hardy who was driving a taxi numbered 1729. When he told Ramanujan about it, he hoped that it was not a sign of bad luck given that “1729 looked like such a dull and ordinary number”, for which Ramanujan replied:

No, it’s a very interesting number; it is the smallest number that can be expressed as the sum of two cubes in two different ways.

Imagine Ramanujan with his hands on a computer. It could even extend this statement by looking for numbers that match the following criteria:

“The smallest number expressible as the sum of N powers of P in K different ways”

For example, for P=9, N=9 and K=2, you will find this number: 458143414265583

458143414265583 = 1^9 + 2^9 + 4^9 + 14^9 + 16^9 + 18^9 + 20^9 + 37^9 + 41^9
458143414265583 = 1^9 + 2^9 + 5^9 + 8^9 + 15^9 + 22^9 + 25^9 + 33^9 + 42^9

The code is at the bottom, well done, ACC.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace Ramanujan1729
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string MAXLEN = "1000000000000000";

            if (args.Length == 1 && args[0].Equals("-all"))
            {
                for (int p = 3; p <= 10; p++)
                {
                    for (int n = 2; n <= 10; n++)
                    {
                        bool breakPoint = false;
                        for (int c = 2; c <= 5; c++)
                        {
                            try
                            {
                                Console.WriteLine("p={0}, n={1}, c={2}", p, n, c);
                                if (!SumOfPowers(0,
                                                1,
                                                "",
                                                p,
                                                n,
                                                c,
                                                new Hashtable(),
                                                BigInteger.Parse(MAXLEN)))
                                {
                                    break;
                                }
                                Console.WriteLine();
                            }
                            catch (OutOfMemoryException e)
                            {
                                Console.WriteLine("Error: {0}", e.Message);
                                Console.WriteLine("Continuing...");
                                breakPoint = true;
                                break;
                            }
                        }

                        if (breakPoint) break;
                    }
                }
                return;
            }
            else if (args.Length != 3)
            {
                Console.WriteLine("Usage: Ramanujan1729.exe   ");
                Console.WriteLine("Example: Ramanujan1729.exe 3 2 2");
                return;
            }
            SumOfPowers(0, 
                        1, 
                        "", 
                        Int32.Parse(args[0]), 
                        Int32.Parse(args[1]), 
                        Int32.Parse(args[2]), 
                        new Hashtable(), 
                        BigInteger.Parse(MAXLEN));
        }

        static bool SumOfPowers(BigInteger sum,
                                BigInteger startNumber,
                                string numbers,
                                int power,
                                int n,
                                int uniqueComb,
                                Hashtable htSum,
                                BigInteger MAX)
        {
            if (sum > MAX || htSum.Count >= 10000000) return false;

            if (n == 0)
            {
                if (!htSum.ContainsKey(sum)) htSum.Add(sum, new Hashtable());
                Hashtable combinations = (Hashtable)htSum[sum];
                if (!combinations.ContainsKey(numbers.Trim())) combinations.Add(numbers.Trim(), true);

                if (combinations.Count == uniqueComb)
                {
                    Console.WriteLine("Found: n = {0}", sum);
                    foreach (string num in combinations.Keys)
                    {
                        Console.WriteLine(num);
                    }
                    return true;
                }
                return false;
            }

            for (BigInteger i = startNumber, p = BigInteger.Pow(i, power); p <= MAX; i++, p = BigInteger.Pow(i, power))
            {
                if (SumOfPowers(sum + p, i + 1, numbers + " " + i.ToString(), power, n - 1, uniqueComb, htSum, MAX)) return true;
            }

            return false;
        }
    }
}

Leave a Reply

Your email address will not be published.