-2
$\begingroup$

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?

  • 0
    @Joe: 22 is on the list because $2\times 2=4$ is divisible by $2+2=4$, and 44 is on the list because $4\times 4=16$ is divisible by $4+4=8$.2012-06-25

3 Answers 3

5

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.

  • 1
    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.2012-04-03
2

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$.

Then your product is

$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.

  • 0
    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 :)2012-04-03
1

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!!

  • 0
    @Chopra: the usual thing to do when asking $f$or help on why your code is doing poorly is to *post your code* and ask for peer review.2012-04-04