# Efficient algorithms for computing Digits Sums Numbers

Is there any efficient way to generate these numbers?

The sequence OEIS A038367: Numbers $n$ with property that (product of digits of $n$) is divisible by (sum of digits of $n$).

First few: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 22, 30, 36, 40, 44, 50, \ldots$

Suppose I want to generate $10^9$th such number. Is there any efficient mathematical theory/research paper to generate such a number.

Actually, I have to write a program to generate $10^9$ such numbers, and the execution time limit is only $20$ seconds. So the normal or simple way will take a month to produce the result, so their might be some complex or special efficient methods? Can you please help me in solving this mathematical problem?

-
First, note that any number with a 0 digit is in the set (this is most of the first 10^9). Next, note that there are only a small number of possible denominators. –  deinst Apr 3 '12 at 17:41
If it is for a programming contest, just generate them offline, and make a lookup table of those and submit a program to enumerate that table. Can't get faster than that! –  Aryabhata Apr 3 '12 at 18:52
Well ,there are people who had developed the idea to run this program in 0.58 seconds... codechef.com/APRIL12/problems/PDSNUM –  Maths123 Apr 3 '12 at 19:03
@ChopraJack A simple brute force counter (the only optimization is skipping numbers with 0 digits) runs on my machine in just over 3 seconds. I strongly suspect that the 0.58 second run is due more to careful coding than exploiting mathematical subtleties. –  deinst Apr 4 '12 at 0:40
Why are 22 and 44 in that list? –  user34497 Jun 25 '12 at 22:03

I'd be surprised if there were a method of doing this that's significantly faster than the obvious one. However, I think your estimate that the obvious method would take a month is way off. We can expect these numbers to be rather dense, since the product of the digits will typically contain lots of small factors and the sum will often be a product of a few small factors. I wouldn't be surprised if the time limit of $20$ seconds was chosen such that you can solve the problem with the obvious method, but only if you code efficiently. The most important aspect to get right for a fast implementation is not to compute the sums and products from scratch for each number but to only adjust for the last digit as it changes.

-
Or perhaps don't compute the products at all (and do expensive trial divisions) -- just look up the prime factorization of each sum is a table (the sums cannot be very large) and check that its factors are found among the digits. Bit tricks can be used to fit the exponents of 2,3,5,7 into a single machine word and test for divisibility in two or tree instructions. Still, 20 seconds sounds rather tight for sequential code on desktop hardware. Be sure to unroll that inner loop... –  Henning Makholm Apr 3 '12 at 17:45
@Henning: Packing the factors into bits is a good idea. One would have to use one bit for every potential factor of every potential prime in order to test for the presence of enough factors of each prime with bit operations. However, nowadays division doesn't take all that long, and the memory access for the table lookup would probably take at least as long. Also, as deinst points out, most numbers qualify because they contain a $0$, so I don't think the $20$ seconds is all that tight; it gives you about $20$ nanoseconds per number, which is something like $40$ cycles. –  joriki Apr 3 '12 at 18:01
In fact, since the ones that contain a $0$ in one of the higher digits are easily dealt with en bloc, you actually have a lot more time than that for the more difficult numbers. –  joriki Apr 3 '12 at 18:05
Yes, didn't notice the $0$ property. I somehow got into my head that "$0$s are allowed" would mean that they were implicitly ignored when forming the product. As for bit packing, the only primes we need to track are 2,3,5 and 7, because those are the only prime factors a nonzero product of digits can have -- a sum with any larger prime factor would be marked with a single shared "never a factor" bit. Since the digit sum can never be larger than about 100, the table would be very small and certainly fit in a L1 cache. –  Henning Makholm Apr 3 '12 at 18:16

Let $a_1,.., a_k$ be the digits of your number $n$, listed increasingly. Note that if $n$ has this property, then all numbers with exactly those digits have this property.

Lets say that $a_1=...=a_m=1$ and $a_{m+1} >1$.

$$a_{m+1}...a_{k} =2^\alpha 3^\beta 5^\gamma 7^\beta \,.$$

This suggests the following simple generating algorithm:

Step 1: generate numbers of the form $2^\alpha 3^\beta 5^\gamma 7^\beta$.

Step 2 Write $2^\alpha 3^\beta 5^\gamma 7^\beta$ as product of digits in all/as many ways as possible.

Step 3 For each such product of digits, list all the divisors $d$ of $2^\alpha 3^\beta 5^\gamma 7^\beta$ which are greater or equal than the sum of those digits.

Step 4 add exactly $d-$ sum of digits $1's$ to the list. You now get the digits of such a number $n$.

Step 5 Write all the possible permutations of those digits.

-
Given that the task is to generate exactly the $10^9$-th such number, this would require some sort of at least partial sorting, which will be difficult to achieve within the specified time limit; considering that, as deinst noted, most numbers will be of this form, it seems preferable to generate them sequentially. –  joriki Apr 3 '12 at 17:54
@joriki It may be worthwhile to count the number of such integers with 9 or fewer digits combinatorially (this will be close to but less than 10^9), and then starting to iterate from 1111111111 (if necessary). I'd do things slightly differently than N.S., but the same general idea. It will however take vastly longer to code such a mess than it would to just run the brute force count. –  deinst Apr 3 '12 at 18:59
@joriki Actually if you read the post, the problem he needs to solve is generating $10^9$ numbers, finding the $10^9$-th number is just something he wanted thinking that it makes the problem easier. –  N. S. Apr 3 '12 at 20:09
@N.S.: I'm not sure what you mean by "if you read the post" -- are you implying that I didn't read the post? As it turns out, your reading of that sentence is grammatically correct, but I was right in assuming that the contradiction between the two formulations was due to lack of proficiency in English and the task is indeed to find the $n$-th of these numbers, as you can see by following the link to the competition that the OP provided in a comment under the question. –  joriki Apr 3 '12 at 20:44
Yep you are right. His post is actually asking how to find the $10^9$th number, and then he said that he has to solve a different problem (the one for which I posted the answer)... From his post I understood that he has to generate $10^9$ numbers, because that was the only "I have to" part. It turns out that actually the problem he wants to solve is completely different....And unethical :) –  N. S. Apr 3 '12 at 23:09

If you go through each number and test them individually, I believe that won't far away from 20 seconds (it might be 200 seconds, but won't take months, you'd have to just try it and see).

If you're close to 20 seconds, it's worth thinking about how you can make efficiency savings to ensure you get below 20 seconds (rather than coming up with a new method/reading research papers).

Be more efficient by reducing the number of calculations you need to do.

• The most obvious efficiency is in your digital sum calculation: rather than calculating the digital sum "fresh" each time, you could consider how to calculate the digital sum from the previous number's digital sum.

If you get this first point right, I reckon this will ~halve the time required, but maybe even better.

• For the digital product, it's harder to use this method (some of the digital products will be 0), and although I'm not sure if you will need to, I could suggest that you could set up a hash table: when you pass through 1234, save this as the set {1,2,3,4} corresponding to the digital product 24 Now, whenever you pass a number with the same digits, e.g. 4312, you can look up {1,2,3,4} and find the result is 24 without doing the calculation.

I'm not sure if this second point will realistically save much time, so you should check that you haven't beaten 20 seconds before doing that!!

-
You could have three bits per digit to code up to $7$ identical copies of each digit in a single 32-bit index; then you'd have to treat numbers with $8$ or more identical digits separately. However, just as with Henning's idea of bit-coded prime factors, I doubt that any such methods that require memory access will be faster than a simple test division. Zeros aren't a problem since numbers containing zeros should be treated en bloc anyway. –  joriki Apr 3 '12 at 18:15
@all::Tried to implement the ideas,but could n't beat the timelimit 20 seconds yet.If any one can code this problem within 20 seconds time limit,then please share ur code.Thanks! –  Maths123 Apr 3 '12 at 18:42
how many seconds are you on? or, how far can you get in 20 secs? this is important to decide where to focus your effort. –  Ronald Apr 3 '12 at 19:40
@Chopra: If understand correctly, this is a running competition? Are you saying you want us to provide you with code to solve a problem in a running competition? –  joriki Apr 3 '12 at 20:47
@Chopra: the usual thing to do when asking for help on why your code is doing poorly is to post your code and ask for peer review. –  Willie Wong Apr 4 '12 at 8:14