Sum-Product numbers

[Jim Nastos]

On 2/2/06, Eric W. Weisstein <eww at wolfram.com> wrote:
> http://www.research.att.com/~njas/sequences/A114457
>
> gives the smallest k such that abs(S(k)P(k)-k) equals n, where S(k) is the
> sum and P(k) is the product of decimal digits of k.
>
> a(n) is small for 0<=n<=99, except for n=33 and 69. Brute-force searching
> for a(33) shows that, if it exists, it must be > 10^11.  Does anyone have
> any ideas on how to find its value?  (Or even show it exists?)

 Since the sought-after number,k, can not have 0 in its digits, we
know that if k=a(33) has d digits, then
d <= S(k)   and                  S(k) <= 9d
dP(k) <= S(k)P(k)    and   S(k)P(k) <= 9dP(k)
dP(k) <= k +/- 33    and   k +/- 33 <= 9dP(k)
so
(k-33)/9d <= P(k) <= (k+33)/d

for 12 digits, this is (k-33)/108  <=  P(k)  <=  (k+33)/12
Since k is over 10^11, these are very tight bounds on the product of
digits. Simply removing 0 from the digits of k cuts out over 71% of
the search space, and if these bounds are easily-checkable, it can cut
out a bit more. (For instance, the lower bound says that if each of
the digits of k are less than 6, k won't work.)

J