my earlier riddle

Hoempa

Math Team
Apr 2010
2,780
361
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:
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
A more bruteforce-method is as follows:
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
}
I wrote a more comprehensive explanation in Dutch. If anyone likes, I could try to translate to English.
 
Last edited by a moderator:

v8archie

Math Team
Dec 2013
7,712
2,682
Colombia
Is there any reason you haven't looked at 1s? They clearly contribute nothing to the product while increasing the sum.
 

Hoempa

Math Team
Apr 2010
2,780
361
In a sense I look at the ones. For example, the pair 32 has product 3 * 2 = 6 and sum 3 + 2 = 5 so we'd need to add at least one 1. Say, we take upperlimit 10^9, i.e. 9 digits. Then all permutations of
321, 3211, 32111, 321111, 3211111, 32111111, 321111111 work and we find that just by looking at the upperlimit and 3 and 2. See?
 
Similar Math Discussions Math Forum Date
General Math
Geometry
Algebra
General Math