Attacking a hard problem

  Recently I decided to resume my activities on Project Euler at night (no, I don't play xbox at night, although I do watch Netflix & Amazon Streaming!). Since I got to 192 problems solved on Project Euler, I decided to take a break since the problems were getting excruciatingly complicated (I mean, having to go deep into Diophantine Equations, Pell's Equation, all possible Fermat Theorems was just too much). I then switched to HackerRank which is a little more academic and less brutal than Project Euler. But after solving 166 problems on HackerRank, again it got painful. So I decided to give it another try to Project Euler, and have solved 5 more problems in the past week (I now have 197 problems solved. Goal is 200).

  My username on both is Relentless. With all that meaning and stuff.

  Project Euler problems, especially the ones after #146, are in general hard problems (module a dozen or so easy ones). I wanted to tell in this post how I tackle them.

  The problem in question is this one, problem 387, solved by < 2,000 people. Here is the problem copied/pasted.

A Harshad or Niven number is a number that is divisible by the sum of its digits.
201 is a Harshad number because it is divisible by 3 (the sum of its digits.)
When we truncate the last digit from 201, we get 20, which is a Harshad number.
When we truncate the last digit from 20, we get 2, which is also a Harshad number.
Let's call a Harshad number that, while recursively truncating the last digit, always results in a Harshad number a right truncatable Harshad number.
Also:
201/3=67 which is prime.
Let's call a Harshad number that, when divided by the sum of its digits, results in a prime a strong Harshad number.
Now take the number 2011 which is prime.
When we truncate the last digit from it we get 201, a strong Harshad number that is also right truncatable.
Let's call such primes strong, right truncatable Harshad primes.
You are given that the sum of the strong, right truncatable Harshad primes less than 10000 is 90619.
Find the sum of the strong, right truncatable Harshad primes less than 10¹⁴.

So here are the way to tackle problems like this:
1) Sit down and read it carefully. There is a tendency to be intimated by the jargons, numbers and length of the problem. Don't. Once you read it carefully and you understand exactly what the author is talking about and what she wants, you'll feel more in peace.
2) Research. There is no shame in doing some research - as matter of fact they encourage you to research some of the concepts. For instance, go ahead and Bing about Harshad numbers and you'll find a ton of interesting information about it. Read it.
3) Look at what the problem is asking for. This will give you a hint of the algorithm to be used. In this case, the problem is asking for the sum of the given numbers. That means you'll have to find all the given numbers. Why is that important? Most likely what this means is that this is not a Dynamic Programming problem, which is great - those are really-really hard to wrap your head around.  If the question was the count of solutions, then we'd be in dire straits
4) Look at the upper bound given. In this case is 10^14, also known as 100000000000000, also known as intractable for a simple -for loop.
5) Have a Util library with a ton of shit that you may need. Any fancy method that you may need, from methods to solve linear equations to others to do primality testing for really large numbers. I've got a 5,000 lines-of-code library with supporting methods.

3 and 4 should tell you one important thing: you can't do a -for loop and check whether or not each number is a candidate solution. Instead, you will likely have to generate each candidate all the way to the boundary. Generation implies some kick-ass formula to skip a bunch of elements. When you do 2, you will find a quick way to generate Harshad numbers. Finally 5 comes handy to do a quick primality testing using Miller-Rabin methods. Putting all that together with a simple recursion and you get the solution in few secs.

Code is below. Love you all!!! Marcelo.

        public static void Problem387()
        {
            long harshadNumber = 0;
            long sumOfDigits = 0;
            long max = 100000000000000;
            BigInteger result = 0;
            Problem387HarshadNumbers(harshadNumber,
                                     sumOfDigits,
                                     max,
                                     ref result);
            Console.WriteLine();
            Console.WriteLine("Solution: {0}", result);
        }
        private static void Problem387HarshadNumbers(long harshadNumber,
                                                     long sumOfDigits,
                                                     long max,
                                                     ref BigInteger result)
        {
            if(harshadNumber >= max)
            {
                return;
            }
            if (harshadNumber > 0)
            {
                long candidate = harshadNumber / sumOfDigits;
                if (Util.IsPrimeMillerRabin(candidate))
                {
                    for (int i = 1; i < 10; i += 2)
                    {
                        long primeCandidate = 10 * harshadNumber + i;
                        if (primeCandidate < max && Util.IsPrimeMillerRabin(primeCandidate))
                        {
                            result += primeCandidate;
                            Console.WriteLine(primeCandidate);
                        }
                    }
                }
            }
            for (int i = (harshadNumber == 0 ? 1 : 0); i < 10; i++)
            {
                long newHarshadNumber = 10 * harshadNumber + i;
                long newSumeOfDigits = sumOfDigits + i;
                if (newHarshadNumber % newSumeOfDigits == 0)
                {
                    Problem387HarshadNumbers(newHarshadNumber, newSumeOfDigits, max, ref result);
                }
            }
        }