## 136 - Ugly Numbers

Moderator: Board moderators

Mpouzas
New poster
Posts: 1
Joined: Sat Oct 06, 2007 12:36 am
Well it's a quite tricky problem...

The problem is clearly stated, It doesn't say to calculate the 1500'th and then print it. It just says to print the num...

ofcourse you have to come up with an algorithm that calculates the num...

since you find it, and believe me it takes a long time to do so... Just print the BLOODY NUMBER!!!:D

so a code like the one below
//////////////////////////////////////
#include <iostream>

int main( void ) {
std::cout << "The 1500'th number is " << 0000000000<< '.'
<< std::endl;
return 0;

}
/////////////////////////////////////

will just do

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

### Without storing already calculated numbers...

Hio wrote:I tried with a straight-to-the-problem solution, i mean i made a procedure that returns 1 if a given number is ugly and 0 otherwize. Well as you can suppose the result needs a lot of time.
The function is that:

[...]

If some one can find a way to speed this up. I will be greatfull for help.
Thanks
Hi, Hio.

I guess it's "a bit" late for this reply to be helpful to you, but perhaps it could be for someone else (including myself).

If when you ask for "a way to speed this up" you mean a way to solve this problem as it is described, in former posts of this same thread you may find very smart ways to do so. But if you mean a way to calculate ugly numbers without storing all the already calculated previous ones, as you are doing in your algorithm, I believe this could help you.

My first attempt to solve this problem was exactly this way. I wrote a function with which you may calculate the next ugly number from the previous one N in a time in O( [log(N)]^3) with very good constants. I made just a prototype of the algorithm in Octave, as it took an execution time of about 6s to reach the 1500th number, which in practical terms means that the equivalent Pascal/C/C++ algorithm hardly could get below the problem time limit, so I gave up with this idea.

Here you may find my Octave function. I believe it's quite easy to read, though you don't know programming in Octave (BTW, it also works perfectly in MATLAB).

Code: Select all

``````function [res, pruebas] = sigp235(num)
% function [res, pruebas] = sigp235(num)
%
% Returns in 'ret' the lesser number which is greater or equal to 'num'
% that can be factorized in 2, 3, and 5, i.e., can be expressed as
% res = 2^i * 3^j * 5^k, with i, j, and k natural.
% So if 'num' matches this property, it returns the same value 'num'.
% If two results are specified in the call, returns in 'pruebas'
% the number of attempts evaluated (candidate numbers considered).
%

%
p2max = ceil (log(num) / log(2));
p3max = ceil (log(num) / log(3));
p5max = ceil (log(num) / log(5));
%
maxp2 = 2^p2max;
maxp3 = 3^p3max;
maxp5 = 5^p5max;
%
best_est = min (maxp2, min (maxp3, maxp5));
if best_est == num,
res = best_est;
if nargout == 2,
pruebas = 3;
end
return;
end;
%
pbas = 3;
%
f5 = maxp5;
for p5 = 1:p5max,
f5 = f5 / 5;
factor5 = num / f5;
p3max = ceil (log(factor5) / log(3));
f3 = 3^p3max;
for p3 = 0:p3max,
factor53 = factor5 / f3;
p2max = ceil (log (factor53) / log(2));
f2 = 2^p2max;
for p2 = 0:p2max,
attempt = f5 * f3 * f2;
pbas = pbas + 1;
if attempt == num,
res = num;
if nargout == 2,
pruebas = pbas;
end
return;
elseif attempt > num && attempt < best_est,
best_est = attempt;
elseif attempt < num,
break;
end
f2 = f2 / 2;
end
f3 = f3 / 3;
end
end
res = best_est;
if nargout == 2,
pruebas = pbas;
end
``````
With this function you may easily calculate the N'th ugly number by means of the following simple script:

Code: Select all

``````nfound = 1; tried = 1;
for nfound=2:N,
tried = sigp235 (tried+1);
end
printf ("%d => %lu\n", N, tried);
``````
If anyone else has a better way to calculate ugly numbers without storing all the previous ones, I would appreciate it if he/she were so nice to share his/her knowledge with me.

c u,

rahat089
New poster
Posts: 2
Joined: Sat May 02, 2009 5:03 pm

### Re: 136 Ugly number WA

i am gettin wrong ans with this code...can anyone plz help me out with this???

#include<stdio.h>
int p;
int q;
int r;
int ugly[1501]={0};
int main()
{
int P,Q,R;
ugly[0]=1;
p=q=r=0;
int i=1;
while(ugly[1499]==0)
{
P=(ugly[p])*2;
Q=(ugly[q])*3;
R=(ugly[r])*5;
if((P<Q)&&(P<R))
{
ugly=P;
i++;
p++;
}
else if((Q<P)&&(Q<R))
{
ugly=Q;
i++;
q++;
}
else if((R<P)&&(R<Q))
{
ugly=R;
i++;
r++;
}
else if(P==Q)
{
q++;
}
else if(P==R)
{
r++;
}
else if(R==Q)
{
r++;
}

}
printf("The 1500'th ugly number is %d",ugly[1499]);
return 0;
}

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Contact:

### Re: 136 Ugly Number Presentation Error

You're just missing "\n";
remove after accepted

prodhan
New poster
Posts: 2
Joined: Sat Oct 17, 2009 3:07 am

### Re: 136 Ugly Number Presentation Error

where to include "\n"
I am trying it in more & more in diff positions but getting WA.

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

### Re: 136 Ugly Number Presentation Error

Code: Select all

``printf("The 1500'th ugly number is %d.\n",ugly[1499]);``
There you go. Remove your code afterwards .

mustak0715
New poster
Posts: 3
Joined: Tue Oct 26, 2010 3:42 am

### problem 136

is this correct the 1500th ugly number is 2999.
here is code where is error;
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
vector<long>ugly;
vector<long>list;
vector<long>::iterator it;
vector<long>::iterator u;

void primegenerate(long n)
{

//list.push_back(2);
for(long i=7;i<=n;i+=2)
{
list.push_back(i);//list create
}
for(long p=3;p*p<=n;p+=2)
{
for(it=list.begin()+1;it<list.end();)
{
if(*it%p==0 && *it!=p)
{
list.erase(it);//erase

}
else
it++;
}
}

i=0;
/*for(it=list.begin();it<list.end();it++,i++)
{
cout<<i<<" "<<list<<" ";
}*/
}

void print(int number)
{
//int i=0;
u=ugly.begin();
u=u+number-1;
cout<<"The "<<number<<"th ugly nmber is "<<*u;
// for(it=ugly.begin();it<ugly.end(),i<1500;it++,i++)
// {cout<<i<<" "<<*it<<endl;
// }
}

int main()
{
int counter=0;

for(long i=7;i<3000;i++)
{
if(i%2||i%3||i%5)
{

ugly.push_back(i);

//cout<<ugly[counter]<<" ";
counter++;}

}
cout<<counter;

primegenerate(1600);

//cout<<list.size();
long num,den;
u=ugly.begin();
for(u=ugly.begin();u<ugly.end();)
{
for(it=list.begin();(*it)*(*it)<=(*u)||it<list.end();it++)
{
num=*u;den=*it;
if(num%den==0)
{
ugly.erase(u);//erase
break;
}

}
u++;
}

//int number;
//while(1){

u=ugly.begin();
for(i=1;i<=6;i++)
{
ugly.insert(u,1,i);
u++;
}
//while(1){
//cin>>number;

print(1500);
//cout<<ugly.size()<<" "<<ugly[1500];

return 0;
}
u can mail me at mahmed0715@yahoo.com

dream
New poster
Posts: 3
Joined: Sat Feb 19, 2011 4:40 pm

### 136 ugly numbers run time error

#include<stdio.h>
int main()
{
unsigned long int a,b,flag,loop=6;
for(a=7;;a++)
{
if((a%2==0)||(a%3==0)||(a%5==0))
{
flag=0;
for(b=6;b<a;b++)
{
if((b%2!=0)&&(b%3!=0)&&(b%5!=0))
{
if(a%b==0)
{
flag=1;
break;
}
else
flag=2;
}
}
if(flag==2)
loop=loop+1;
}
if(loop==1500)
{
printf("The 1500'th ugly number is %li.\n",a);
break;
}
}
return 0;
}

here is my code
plz help me
what's the problem??

shiam
New poster
Posts: 8
Joined: Mon Mar 14, 2011 6:44 am

### Re: problem 136

no.. try again..it is bigger than your ans....

mainul07
New poster
Posts: 8
Joined: Fri Oct 05, 2012 1:35 pm
Location: Chittagong
Contact:

### Ugly Number(136)

#include<stdio.h>
unsigned long findmin();
unsigned long temp[3];
int main()
{
unsigned long store[3];
unsigned long result[1500];
int i,j,n;
result[1]=1;
for(i=0;i<3;i++)
store=1;
for(i=2;i<=1500;i++)
{
temp[0]=result[store[0]]*2;
temp[1]=result[store[1]]*3;
temp[2]=result[store[2]]*5;

for(j=0;j<3;j++)
store[j]++;
}

printf("The 1500'th ugly number is %lu.\n",result[1500]);

return 0;
}
unsigned long findmin()
{
int i,j;
unsigned long min=temp[0];
for(i=1;i<3;i++)
if(min>temp)
min=temp;
return 0;
}

When i submit it in uva it show WA.I can not find any error please help me
Mainul Hassan
Website:http://www.teronga.com/

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Ugly Number(136)

unsigned long result[1500];
This line only allocates space for result[0] through result[1499], then you try to print result[1500]
Check input and AC output for thousands of problems on uDebug!

mainul07
New poster
Posts: 8
Joined: Fri Oct 05, 2012 1:35 pm
Location: Chittagong
Contact:

### Re: Ugly Number(136)

Thanks
Mainul Hassan
Website:http://www.teronga.com/

nilaunog
New poster
Posts: 1
Joined: Sat Apr 06, 2013 8:51 am

### 136 Ugly number

what is the mistake of the following code?? plz help me??
#include<stdio.h>
int main()
{
long long int i=1,j,k,l;
long long int num, count=1;
while(count==1500)
{
for(i=1;i<=num;i++)
{
k=0;
if(num%i==0)
{
for(j=1;j<=i;j++)
{
if(i%j==0)
k++;

}
if(k==2)
{
l=i;
}
}
}
if((l==2)||(l==3)||(l==5))
{

count++;

}

}
printf("%d",num);

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 136 Ugly number

Output should consist of a single line as shown below, with <number> replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.
Check input and AC output for thousands of problems on uDebug!

t_sleepy
New poster
Posts: 2
Joined: Tue Oct 01, 2013 1:32 pm

### Re: 136 Ugly number

The following code is giving me wrong answer. Please tell me what is wrong with the code.

#include<stdio.h>
#define min(x,y) ((x)<(y)? x:y)
int main()
{
long u[1520];
int i,a=1,b=1,c=1,x,y,z;
u[1]=1;
u[2]=1;
u[3]=1;
for(i=2;i<=1500;i++){
x=2*u[a];
y=3*u;
z=5*u[c];
u= min (x,min(y,z));
if (u==x) a++;
if (u==y) b++;
if (u==z) c++;
}
printf("The 1500'th ugly number is %ld.",u[1500]);
return 0;
}