check this perl program, hope it explains the algorithm itself
>>>>>>START OF algo.pl<<<<<<<<<<<<
use warnings;
use strict;
sub is_lucky_number
{
my ($cur, $n, $last_n, $next_n, $old_n);
$cur = 1; # to remove numbers at $cur, $cur*2, ...
$n = shift @_; # current index of the input number before removing
$old_n = $n;
die unless $n > 0;
$last_n = -1; # index of the input number when after removing
every $cur-1 number
while($last_n != $n)
{
$cur++;
$next_n = $n - int($n / $cur);
if($n % $cur == 0)
{
#print "$old_n is removed at $cur-th step\n";
return 0; # input number is not lucky because it will be
removed at $cur-th step
}
$last_n = $n;
$n = $next_n;
}
return 1;
}
foreach my $input (1..100)
{
print "$input is lucky\n" if &is_lucky_number($input);
}
print "Press return to exit\n";
<>;
On Sun, Jan 4, 2009 at 2:08 AM, kannan <kven...@gmail.com> wrote:
>
> All the numbers from 1 to infinity are written in sequence:
>
> 1,2,3,4,5,6,7,8,9,10,11,12,13,14.....
> in the first iteration, every second number is removed, leaving:
> 1,3,5,7,9,11,13....
> in the second iteration, every third number in the above sequence is
> removed, thus leaving: 1,3,7,9,13....
> in the third iteration, every fourth number is removed, leaving:
> 1,3,7,13....
> like this the process goes on indefinitely.
> the numbers which are, thus, left are called lucky numbers.
>
> Given a number n(can be as big as 18 digits) you must tell if n is a
> lucky number or not.. how do i proceed?? all that i can think of is a
> naive implementation which obviously wont work because n can be as big
> as 18 digits...
> could you help me or give suggestions on how to proceed....
> (This question was asked in a practice contest which is over now)
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
