A few weeks ago, I posted the following riddle:

How many positive integers less than 1000 have the product of digits <= the sum of their digits?

I've done some research to this question and extensions (higher upperbounds) with some other people and got some algorithm to find these amounts.

Briefly,

To find the number of positive integers less than 10^n that have the product of digits <= the sum of their digits, split in numbers containing at least one 0 in its digits and numbers that contain no 0 in their digits.

Finding the amount with 0's is fairly easy; there are \(\displaystyle 10^n - \frac{9^{n+1}-1}{8}\) of them.

For no 0's, for now please see this code:

A more bruteforce-method is as follows:

I wrote a more comprehensive explanation in Dutch. If anyone likes, I could try to translate to English.

How many positive integers less than 1000 have the product of digits <= the sum of their digits?

I've done some research to this question and extensions (higher upperbounds) with some other people and got some algorithm to find these amounts.

Briefly,

To find the number of positive integers less than 10^n that have the product of digits <= the sum of their digits, split in numbers containing at least one 0 in its digits and numbers that contain no 0 in their digits.

Finding the amount with 0's is fairly easy; there are \(\displaystyle 10^n - \frac{9^{n+1}-1}{8}\) of them.

For no 0's, for now please see this code:

Code:

```
addhelp(productless, "The number of positive integers containing no zero's with product of digits <= sum of digits.")
productless(n)={my(i=[2],t,maxd=maxg1(n));
t=n;
while(#i<=maxd,
if(score(i)<=n,
t+=qperms1(i,n);i=nextnumberL(i),i=nextnumberS(i)
)
);print(p," ",q);t
}
addhelp(maxg1, "The highers amount of digits in such number being > 1")
maxg1(n)=floor(log(n+ceil(log(n)/log(2)))/log(2))+(n<=2)
nextnumberS(n)={my(d=n,r,i);
t=1;
while(t-#d-1&&d[t]==9,t++);
y=#d;
while(d[y]==2,y--);\\print(y," ",y-t);
if(y-t>0,
u=y-1;
forstep(i=u,t+1,-1,if(d[y-1]==d[i-1],u--));
d[u]++;\\++;\\d[t]++;
for(i=u+1,y,d[i]=2);\\for(i=t+1,y,d[i]=2);
r=d
,
v=vector(#d+1);for(i=1,#v,v[i]=2;r=v);r)
}
nextnumberL(n)={my(r,d=n);
if(d[#d]!=9,
\\Find the last non-9 digit from the left.
y=1;
while(y-#d-1&&d[y]==9,y++);
t=#d;
forstep(i=t,y+1,-1,if(d[i-1]!=d[i],t=i-1;break));
if(t!=#d,d[t+1]++;for(i=t+2,#d,d[i]=2),d[y]++;for(i=y+1,#d,d[i]=2));r=d
,
d=vector(#d+1);for(i=1,#d,d[i]=2);r=d
);r
}
addhelp(qperms, "The amount of searched numbers containing these digits in [2,9] and all others (if any) being 1.")
qperms(s, n)={my(r=0,e=1);
if(score(s)<=n,
r=(#s)!;
for(i=1,#s-1,
if(s[i]!=s[i+1],r/=e!;e=1,e++)
);
r/=e!;r*=(binomial(n+1,#s+1)-binomial(score(s),#s+1))
);r
}
addhelp(score, "Least number of digits the number has containing these digits.")
score(s)=prod(i=1,#s,s[i])-vecsum(s)+#s
```

Code:

```
addhelp(productless1, "The number of positive integers containing no zero's with product of digits <= sum of digits.")
productless1(n)={my(maxd=maxg1(n),t=n,d);
for(i=1,binomial(8+maxd,8),d=digits(desnumber(i));
if(score(d)<=n,t+=qperms(d,n));
);t
}
desnumber(n)={
my(q,m=8,i,r=0);
while(binomial(m+1,8)<=n,m++);
n-=binomial(m,8);
q=m-7;
i=q;
while(n>0,
m=i;
while(binomial(m+1,i)<=n,m++);
r=10*r+m+3-i;
n-=binomial(m,i);i--;
);
a=q-#digits(r);
r=((9*r+2)*10^a-2)/9;r
}
```

Last edited by a moderator: