OK, I think the only known solution is that trivial, it can be proved that
it have complexity of O(sqrt(n)),
solution
k=2
iterate {
if(k divides n) return unlucky
if(k>n) return lucky;
n=n-n/k;
k=k+1;
}
after x iteration the n will be at most n/x;
2009/1/7 Miroslav Balaz <gpsla...@googlemail.com>
> ok that was bullshit, the number of lucky numbers is about 10^9
>
> 2009/1/7 Miroslav Balaz <gpsla...@googlemail.com>
>
> You should generate all the lucky numbers, less than 10^18, there shouldy
>> not many of them. maybe 50. And then just submit program using hardwired
>> array.
>>
>> 2009/1/6 Rahul Kushwaha <rahul.kushw...@gmail.com>
>>
>> can anybody tell me which is best and correct solution
>>>
>>> On Tue, Jan 6, 2009 at 12:30 AM, Karthik Singaram Lakshmanan <
>>> karthiksinga...@gmail.com> wrote:
>>>
>>>>
>>>> Its not clear that just a primality test would close the deal...The
>>>> sequence 1,3,7,13...does not have 5 which is prime.
>>>> If you consider a number 'n' for it to be removed in round 2 (n%2)==0
>>>> For it to be removed in round 3 (n-floor(n/2))%3==0 (The floor of n/2
>>>> to accommodate all the numbers thrown out in round 2)
>>>> For it to be removed in round 4 (n-floor(n/2)-floor(n/3))%4==0 (The
>>>> floor of n/3 to accommodate all the numbers thrown out in round 3)
>>>>
>>>> Which is what is being done in the previously posted solutions..
>>>>
>>>>
>>>>
>>>
>>> >>>
>>>
>>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
