interestingb.cpp

#include <stdio.h>
#include <assert.h>
#include <inttypes.h>
#include <vector>

typedef unsigned int uint_t;
const uint_t D = 10;


class Solver {
    std::vector<uint_t> cnts;


    void do_solve(std::vector<uint8_t> &v, uint64_t sum, uint64_t prod, uint64_t n, uint8_t d)
    {
        uint_t l = v.size();
        for (uint8_t j = d; j >= 2; j--) {
            v.push_back(j);
            uint64_t sumj = sum + j;
            uint64_t prodj = prod * j;
            uint64_t nj = (prodj - sumj) + l + 1;
#if 0
            if (nj <= n) {
                printf("%" PRIu64 ": ", n);
                for (uint8_t x: v)
                    printf("%u ", (uint_t) x);
                printf("\n");
            }
#endif
            if (nj <= n) {
                cnts[nj]++;
                do_solve(v, sumj, prodj, n, j);
            }
            v.pop_back();
        }
    }

 public:
    void solve(uint64_t n)
    {
        cnts.clear();
        cnts.resize(n + 1, 0);

        std::vector<uint8_t> v;
        do_solve(v, 0, 1, n, D - 1);

        for (uint_t i = 2; i <= n; i++) {
            printf("%6u: %u \n", i, cnts[i]);
        }
    }

};


int main()
{
    Solver s;
    s.solve(1000000);

    return 0;
}