My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <map>
       
#include <unordered_map>
       
#include <vector>
       
#include <cmath>
       
 
       
// compare x and 137x

       
const unsigned int Signature = 137;
       
 
       
// copied from problem 119

       
unsigned int digitSum(unsigned long long x)
       
{
       
  unsigned int result = 0;
       
  while (x > 0)
       
  {
       
    result += x % 10;
       
    x      /= 10;
       
  }
       
  return result;
       
}
       
 
       
// the brute-force algorithm is surprisingly fast for limit < 10^8

       
unsigned long long bruteForce(unsigned long long limit)
       
{
       
  unsigned long long count = 0;
       
  for (unsigned long long i = 0; i < limit; i += 9) // observation: always multiples of 9
       
    if (digitSum(i) == digitSum(i * Signature))
       
      count++;
       
 
       
  return count;
       
}
       
 
       
// different container types:
       
// std::vector:        0.027s
       
// std::unordered_map: 0.120s
       
// std::map:           0.415s

       
#define FAST
       
#ifdef  FAST
       
const long long Unknown = -1;
       
std::vector<long long> cache((18+1) * 137 * 240, Unknown); // see search() for the constants
       
#else
       
std::unordered_map<unsigned int, long long> cache;
       
//std::map<unsigned int, long long> cache;

       
#endif
       
 
       
// count all numbers where digitSum(x) == digitSum(137x)

       
unsigned long long search(unsigned int numDigits, unsigned int u = 0, int v = 0)
       
{
       
  // memoize
       
  unsigned int id = numDigits;
       
  id *= 137;
       
  id += u;       // 0..136
       
  id *= 240;
       
  id += v + 120; // -116..+116
       
#ifdef FAST
       
  if (cache[id] != Unknown)
       
    return cache[id];
       
#else
       
  auto lookup = cache.find(id);
       
  if (lookup != cache.end())
       
    return lookup->second;
       
#endif
       
 
       
  // only one digit left ?
       
  if (numDigits == 1)
       
  {
       
    // digitSum(137d + u) must be identical to digit + v
       
    // check every possible digit 0..9
       
    unsigned int result = 0;
       
    for (unsigned int digit = 0; digit <= 9; digit++)
       
      if (digitSum(Signature * digit + u) + v == digit)
       
        result++;
       
    cache[id] = result;
       
    return result;
       
  }
       
 
       
  // "shave off" one digit and continues with recursion ...
       
  unsigned long long result = 0;
       
  for (auto digit = 0; digit <= 9; digit++)
       
  {
       
    auto nextU = (Signature * digit + u) / 10;
       
    auto nextV = (Signature * digit + u) % 10 + v - digit;
       
    result += search(numDigits - 1, nextU, nextV);
       
  }
       
 
       
  cache[id] = result;
       
  return result;
       
}
       
 
       
int main()
       
{
       
  // analyze all numbers below 10^18
       
  unsigned int limit = 18;
       
  std::cin >> limit;
       
 
       
  //std::cout << bruteForce(pow(10, limit)) << std::endl;
       
  std::cout << search(limit) << std::endl;
       
  return 0;
       
}

This solution contains 11 empty lines, 16 comments and 12 preprocessor commands.