My Math Forum my earlier riddle

 Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

 May 30th, 2014, 09:28 AM #1 Math Team   Joined: Apr 2010 Posts: 2,770 Thanks: 356 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-#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 skipjack; January 28th, 2015 at 01:32 AM.
 May 30th, 2014, 11:18 AM #2 Math Team   Joined: Dec 2013 From: Colombia Posts: 6,555 Thanks: 2148 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,770 Thanks: 356 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 Linear Mode

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

 Contact - Home - Forums - Top