My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

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


Reply
 
LinkBack Thread Tools Display Modes
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.
Hoempa is offline  
 
May 30th, 2014, 11:18 AM   #2
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,444
Thanks: 2115

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.
v8archie is offline  
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?
Hoempa is offline  
Reply

  My Math Forum > Math Forums > Math Events

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 05:12 PM
help with a riddle adenthet Computer Science 1 August 29th, 2009 07:43 PM
riDDLE ! lisalotte New Users 4 January 21st, 2008 04:14 PM





Copyright © 2017 My Math Forum. All rights reserved.