
Math Events Math Events, Competitions, Meetups  Local, Regional, State, National, International 
 LinkBack  Thread Tools  Display Modes 
May 30th, 2014, 09:28 AM  #1 
Math Team Joined: Apr 2010 Posts: 2,780 Thanks: 361  my earlier riddle
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#d1&&d[t]==9,t++); y=#d; while(d[y]==2,y);\\print(y," ",yt); if(yt>0, u=y1; forstep(i=u,t+1,1,if(d[y1]==d[i1],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 non9 digit from the left. y=1; while(y#d1&&d[y]==9,y++); t=#d; forstep(i=t,y+1,1,if(d[i1]!=d[i],t=i1;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,#s1, 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=m7; i=q; while(n>0, m=i; while(binomial(m+1,i)<=n,m++); r=10*r+m+3i; n=binomial(m,i);i; ); a=q#digits(r); r=((9*r+2)*10^a2)/9;r } Last edited by skipjack; January 28th, 2015 at 12:32 AM. 
May 30th, 2014, 11:18 AM  #2 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,618 Thanks: 2608 Math Focus: Mainly analysis and algebra 
Is there any reason you haven't looked at 1s? They clearly contribute nothing to the product while increasing the sum.

May 30th, 2014, 11:37 AM  #3 
Math Team Joined: Apr 2010 Posts: 2,780 Thanks: 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? 

Tags 
earlier, riddle 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Yet another riddle  hermes2014  Applied Math  10  March 15th, 2015 03:34 AM 
new riddle  Hoempa  New Users  189  June 23rd, 2013 03:31 PM 
Riddle  rebecca  Applied Math  2  November 6th, 2011 04:12 PM 
help with a riddle  adenthet  Computer Science  1  August 29th, 2009 07:43 PM 
riDDLE !  lisalotte  New Users  4  January 21st, 2008 03:14 PM 