wu :: forums
« wu :: forums - Lucky number »
Welcome, Guest. Please Login or Register.
May 4th, 2024, 10:10pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard (Moderators: ThudnBlunder, towr, Icarus, SMQ, william wu, Grimbal, Eigenray)
   Lucky number		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Lucky number  (Read 1597 times)
harsh487
Newbie
*





   


Posts: 6
Lucky number  
« on: Nov 17th, 2008, 10:34am »		 Quote Quote Modify Modify
1 2 3 4 5 6 7 8 9 ......and so on
 
1.Remove every second number
  so the now the nos are  
   1 3 5 7 9 11 13 ......
 
2.Remove every third number
   so now the nos are....
   1 3 7 9 13 15 19 .....
 
3.Remove every fourth number
   so now the nos are...
   1 3 7 13 15 19 25....
 
   and so on
 
A number is considered to be lucky if it lies in the list  
We are given a number 'n'....we have to check whether the number is lucky or not...
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Lucky number  
« Reply #1 on: Nov 17th, 2008, 11:20am »		 Quote Quote Modify Modify
You can find the nth number in O(n) (see http://www.research.att.com/~njas/sequences/A000960). So given F(n), you can find n in O(n log n) using binary search.
Quite possibly it can be done better.
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
harsh487
Newbie
*





   


Posts: 6
Re: Lucky number  
« Reply #2 on: Nov 19th, 2008, 10:40am »		 Quote Quote Modify Modify
Thanx for the link....Can u explain a little bit more how to search for the number using binary search...the problem is that we can't store the series in an array or something...so how to apply the binary search...The link u gave tells how to find the nth number.....but my question is that we are given a number, suppose  145
...Now we have to tell whether 145 lies in list or not....
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Lucky number  
« Reply #3 on: Nov 20th, 2008, 12:50am »		 Quote Quote Modify Modify
on Nov 19th, 2008, 10:40am, harsh487 wrote:
Thanx for the link....Can u explain a little bit more how to search for the number using binary search...the problem is that we can't store the series in an array or something...so how to apply the binary search...The link u gave tells how to find the nth number.....but my question is that we are given a number, suppose  145
...Now we have to tell whether 145 lies in list or not....
I'll simulate the process of determining whether 145 is a lucky number.
First we try f(1)=1 which is to small
So next we try f(2)=2, which is still too small
f(4)=13
f(8)=49
f(16)=207, so now this one is too large. If 145 is a lucky number, we must have f(x)=145 with an x between 8 and 16. Try the middle one first.
f(12)=109, which is smaller. So x > 12
f(14)=147, which is too great again, so try a small x
f(13)=133, which is too small. But there is no integer x between 13 and 14 left, so 145 can't be a lucky number.
 
Note that every f(N) can be calculated in O(N) time; we don't need to have a list of them beforehand.
So we just find the first f(2m) greater than the number we're looking for, and then do a regular binary search to find whether there's an x between 2m-1 and 2m such that f(x) is the number we want.
« Last Edit: Nov 20th, 2008, 12:50am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Lucky number  
« Reply #4 on: Nov 20th, 2008, 2:23am »		 Quote Quote Modify Modify
Here's some c++ code that seems to work.
 
Code:
int nth_lucky(int n)
{
  for(int i=n-1; i>0; i--)
    n = (n/i + (n % i > 0) + 1) * i;
  return n;
}
 
bool is_lucky(int n)
{
  int m=1, i=1, nl;
 
  while( (nl=nth_lucky(m)) < n && i++ < 8*sizeof(m) )  
    m <<= 1;
 
  if(n == nl) return true;
 
  int l = m>>1, r = m;
  while( l+1 < r)
  {
    m=(r+l)/2;
    nl=nth_lucky(m);
    if(n == nl) return true;
    else if(n < nl) r=m;
    else l=m;  
  }  
  return false;
}
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Hippo
Uberpuzzler
*****





   


Gender: male
 Posts: 919
Re: Lucky number  
« Reply #5 on: Nov 20th, 2008, 5:53am »		 Quote Quote Modify Modify
on Nov 20th, 2008, 2:23am, towr wrote:
Here's some c++ code that seems to work.
 
Code:
int nth_lucky(int n)
{
  for(int i=n-1; i>0; i--)
    n = (n/i + (n % i > 0) + 1) * i;
  return n;
}
 
bool is_lucky(int n)
{
  int m=1, i=1, nl;
 
  while( (nl=nth_lucky(m)) < n && i++ < 8*sizeof(m) )  
    m <<= 1;
 
  if(n == nl) return true;
 
  int l = m>>1, r = m;
  while( l+1 < r)
  {
    m=(r+l)/2;
    nl=nth_lucky(m);
    if(n == nl) return true;
    else if(n < nl) r=m;
    else l=m;      
  }  
  return false;
}

 
I would prefere to use font where l and 1 can be distinguished ... Smiley
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Lucky number  
« Reply #6 on: Nov 20th, 2008, 6:55am »		 Quote Quote Modify Modify
on Nov 20th, 2008, 5:53am, Hippo wrote:
I would prefere to use font where l and 1 can be distinguished ... Smiley
Yeah, but not much to be done about that, I'm afraid.
 
Here's a simpler and faster replacement for the second function.
Code:
bool is_lucky(int n)  
{
  return nth_lucky(static_cast<int>(round(sqrt(n*pi/4)))) == n;
}

Works, as far as I've tested it. Runs in about O(n), a factor log(n) better.
« Last Edit: Nov 20th, 2008, 6:56am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board