How to calculate the digit products of the consecutive numbers efficiently?

Question

I'm trying to calculate the product of digits of each number of a sequence of numbers, for example:

21, 22, 23 ... 98, 99 ..

would be:

2, 4, 6 ... 72, 81 ..

To reduce the complexity, I would consider only the [consecutive numbers] in a limited length of digits, such as from 001 to 999 or from 0001 to 9999.

However, when the sequence is large, for example, 1000000000, repeatedly extract the digits and then multiply for every number would be inefficient.

The basic idea is to skip the consecutive zeros we will encounter during the calculation, something like:

using System.Collections.Generic;
using System.Linq;
using System;

// note the digit product is not given with the iteration
// we would need to provide a delegate for the calculation
public static partial class NumericExtensions {
    public static void NumberIteration(
            this int value, Action<int, int[]> delg, int radix=10) {
        var digits=DigitIterator(value, radix).ToArray();
        var last=digits.Length-1;
        var emptyArray=new int[] { };
        var pow=(Func<int, int, int>)((x, y) => (int)Math.Pow(x, 1+y));
        var weights=Enumerable.Repeat(radix, last-1).Select(pow).ToArray();

        for(int complement=radix-1, i=value, j=i; i>0; i-=1)
            if(i>j)
                delg(i, emptyArray);
            else if(0==digits[0]) {
                delg(i, emptyArray);

                var k=0;

                for(; k<last&&0==digits[k]; k+=1)
                    ;

                var y=(digits[k]-=1);

                if(last==k||0!=y) {
                    if(0==y) { // implied last==k
                        digits=new int[last];
                        last-=1;
                    }

                    for(; k-->0; digits[k]=complement)
                        ;
                }
                else {
                    j=i-weights[k-1];
                }
            }
            else {
                // receives digits of a number which doesn't contain zeros 
                delg(i, digits);

                digits[0]-=1;
            }

        delg(0, emptyArray);
    }

    static IEnumerable<int> DigitIterator(int value, int radix) {
        if(-2<radix&&radix<2)
            radix=radix<0?-2:2;

        for(int remainder; 0!=value; ) {
            value=Math.DivRem(value, radix, out remainder);
            yield return remainder;
        }
    }
}

This is only for the enumeration of numbers, to avoid numbers which contain zeros to be calculated in the first place, the digit products are not yet given by the code; but generate the digit products by providing a delegate to perform the calculation will still take time.

How to calculate the digit products of the consecutive numbers efficiently?

Answer 1

EDIT: The "start from anywhere, extended range" version...

This version has a signficantly extended range, and therefore returns an IEnumerable<long> instead of an IEnumerable<int> - multiply enough digits together and you exceed int.MaxValue. It also goes up to 10,000,000,000,000,000 - not quite the full range of long, but pretty big :) You can start anywhere you like, and it will carry on from there to its end.

class DigitProducts
{
    private static readonly int[] Prefilled = CreateFirst10000();

    private static int[] CreateFirst10000()
    {
        // Inefficient but simple, and only executed once.
        int[] values = new int[10000];
        for (int i = 0; i < 10000; i++)
        {
            int product = 1;
            foreach (var digit in i.ToString())
            {
                product *= digit -'0';
            }
            values[i] = product;
        }
        return values;
    }

    public static IEnumerable<long> GetProducts(long startingPoint)
    {
        if (startingPoint >= 10000000000000000L || startingPoint < 0)
        {
            throw new ArgumentOutOfRangeException();
        }
        int a = (int) (startingPoint / 1000000000000L);
        int b = (int) ((startingPoint % 1000000000000L) / 100000000);
        int c = (int) ((startingPoint % 100000000) / 10000);
        int d = (int) (startingPoint % 10000);

        for (; a < 10000; a++)
        {
            long aMultiplier = a == 0 ? 1 : Prefilled[a];
            for (; b < 10000; b++)
            {
                long bMultiplier = a == 0 && b == 0 ? 1
                                 : a != 0 && b < 1000 ? 0
                                 : Prefilled[b];
                for (; c < 10000; c++)
                {
                    long cMultiplier = a == 0 && b == 0 && c == 0 ? 1
                                     : (a != 0 || b != 0) && c < 1000 ? 0
                                     : Prefilled[c];

                    long abcMultiplier = aMultiplier * bMultiplier * cMultiplier;
                    for (; d < 10000; d++)
                    {
                        long dMultiplier = 
                            (a != 0 || b != 0 || c != 0) && d < 1000 ? 0
                            : Prefilled[d];
                        yield return abcMultiplier * dMultiplier;
                    }
                    d = 0;
                }
                c = 0;
            }
            b = 0;
        }
    }
}

---

EDIT: Performance analysis

I haven't looked at the performance in detail, but I believe at this point the bulk of the work is just simply iterating over a billion values. A simple for loop which just returns the value itself takes over 5 seconds on my laptop, and iterating over the digit products only takes a bit over 6 seconds, so I don't think there's much more room for optimization - if you want to go from the start. If you want to (efficiently) start from a different position, more tweaks are required.

---

Okay, here's an attempt which uses an iterator block to yield the results, and precomputes the first thousand results to make things a bit quicker.

I've tested it up to about 150 million, and it's correct so far. It only goes returns the first billion results - if you needed more than that, you could add another block at the end...

static IEnumerable<int> GetProductDigitsFast()
{
    // First generate the first 1000 values to cache them.
    int[] productPerThousand = new int[1000];

    // Up to 9
    for (int x = 0; x < 10; x++)
    {
        productPerThousand[x] = x;
        yield return x;
    }
    // Up to 99
    for (int y = 1; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            productPerThousand[y * 10 + x] = x * y;
            yield return x * y;
        }
    }
    // Up to 999
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < 10; y++)
        {
            for (int z = 0; z < 10; z++)
            {
                int result = x * y * z;
                productPerThousand[x * 100 + y * 10 + z] = x * y * z;
                yield return result;
            }
        }
    }

    // Now use the cached values for the rest
    for (int x = 0; x < 1000; x++)
    {
        int xMultiplier = x == 0 ? 1 : productPerThousand[x];
        for (int y = 0; y < 1000; y++)
        {
            // We've already yielded the first thousand
            if (x == 0 && y == 0)
            {
                continue;
            }
            // If x is non-zero and y is less than 100, we've
            // definitely got a 0, so the result is 0. Otherwise,
            // we just use the productPerThousand.
            int yMultiplier = x == 0 || y >= 100 ? productPerThousand[y]
                                                 : 0;
            int xy = xMultiplier * yMultiplier;
            for (int z = 0; z < 1000; z++)
            {
                if (z < 100)
                {
                    yield return 0;
                }
                else
                {
                    yield return xy * productPerThousand[z];
                }
            }
        }
    }
}

I've tested this by comparing it with the results of an incredibly naive version:

static IEnumerable<int> GetProductDigitsSlow()
{
    for (int i = 0; i < 1000000000; i++)
    {
        int product = 1;
        foreach (var digit in i.ToString())
        {
            product *= digit -'0';
        }
        yield return product;
    }
}

Hope this idea is of some use... I don't know how it compares to the others shown here in terms of performance.

EDIT: Expanding this slightly, to use simple loops where we know the results will be 0, we end up with fewer conditions to worry about, but for some reason it's actually slightly slower. (This really surprised me.) This code is longer, but possibly a little easier to follow.

static IEnumerable<int> GetProductDigitsFast()
{
    // First generate the first 1000 values to cache them.
    int[] productPerThousand = new int[1000];

    // Up to 9
    for (int x = 0; x < 10; x++)
    {
        productPerThousand[x] = x;
        yield return x;
    }
    // Up to 99
    for (int y = 1; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            productPerThousand[y * 10 + x] = x * y;
            yield return x * y;
        }
    }
    // Up to 999
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < 10; y++)
        {
            for (int z = 0; z < 10; z++)
            {
                int result = x * y * z;
                productPerThousand[x * 100 + y * 10 + z] = x * y * z;
                yield return result;
            }
        }
    }

    // Use the cached values up to 999,999
    for (int x = 1; x < 1000; x++)
    {
        int xMultiplier = productPerThousand[x];
        for (int y = 0; y < 100; y++)
        {
            yield return 0;
        }
        for (int y = 100; y < 1000; y++)
        {
            yield return xMultiplier * y;
        }
    }

    // Now use the cached values for the rest
    for (int x = 1; x < 1000; x++)
    {
        int xMultiplier = productPerThousand[x];
        // Within each billion, the first 100,000 values will all have
        // a second digit of 0, so we can just yield 0.
        for (int y = 0; y < 100 * 1000; y++)
        {
            yield return 0;
        }
        for (int y = 100; y < 1000; y++)
        {
            int yMultiplier = productPerThousand[y];
            int xy = xMultiplier * yMultiplier;
            // Within each thousand, the first 100 values will all have
            // an anti-penulimate digit of 0, so we can just yield 0.
            for (int z = 0; z < 100; z++)
            {
                yield return 0;
            }
            for (int z = 100; z < 1000; z++)
            {
                yield return xy * productPerThousand[z];
            }
        }
    }
}

Answer 2

You can do this in a dp-like fashion with the following recursive formula:

n                   n <= 9
a[n/10] * (n % 10)  n >= 10

where a[n] is the result of the multiplication of the digits of n.

This leads to a simple O(n) algorithm: When calculating f(n) assuming you have already calculated f(·) for smaller n, you can just use the result from all digits but the last multiplied with the last digit.

a = range(10)
for i in range(10, 100):
    a.append(a[i / 10] * (i % 10))

You can get rid of the expensive multiplication by just adding doing a[n - 1] + a[n / 10] for numbers where the last digit isn't 0.

Answer 3

The key to efficiency is not to enumerate the numbers and extract the digits, but to enumerate digits and generate the numbers.

int[] GenerateDigitProducts( int max )
{
    int sweep = 1;
    var results = new int[max+1];
    for( int i = 1; i <= 9; ++i ) results[i] = i;
    // loop invariant: all values up to sweep * 10 are filled in
    while (true) {
        int prior = results[sweep];
        if (prior > 0) {
            for( int j = 1; j <= 9; ++j ) {
                int k = sweep * 10 + j; // <-- the key, generating number from digits is much faster than decomposing number into digits
                if (k > max) return results;
                results[k] = prior * j;
                // loop invariant: all values up to k are filled in
            }
        }
        ++sweep;
    }
}

It's up to the caller to ignore the results which are less than min.

• Demo: http://ideone.com/rMK7Sh

---

Here's a low space version using the branch-bound-prune technique:

static void VisitDigitProductsImpl(int min, int max, System.Action<int, int> visitor, int build_n, int build_ndp)
{
    if (build_n >= min && build_n <= max) visitor(build_n, build_ndp);

    // bound
    int build_n_min = build_n;
    int build_n_max = build_n;

    do {
        build_n_min *= 10;
        build_n_max *= 10;
        build_n_max +=  9;

        // prune
        if (build_n_min > max) return;
    } while (build_n_max < min);

    int next_n = build_n * 10;
    int next_ndp = 0;
    // branch
    // if you need to visit zeros as well: VisitDigitProductsImpl(min, max, visitor, next_n, next_ndp);
    for( int i = 1; i <= 9; ++i ) {
        next_n++;
        next_ndp += build_ndp;
        VisitDigitProductsImpl(min, max, visitor, next_n, next_ndp);
    }

}

static void VisitDigitProducts(int min, int max, System.Action<int, int> visitor)
{
    for( int i = 1; i <= 9; ++i )
        VisitDigitProductsImpl(min, max, visitor, i, i);
}

• Demo: http://ideone.com/AIal1L