Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

Re^4: Challenge: Another Infinite Lazy List

by Roy Johnson (Monsignor)
on Mar 19, 2005 at 00:04 UTC ( #440831=note: print w/replies, xml ) Need Help??

in reply to Re^3: Challenge: Another Infinite Lazy List
in thread Challenge: Another Infinite Lazy List

Here's a filter that is O(F=number of factors * P=product of factors) + O(N) to check N numbers. It takes advantage of the fact that the output is periodic: if N is a member, then N + P is also a member. This could be written caching-style, so you only have to do your gcd check if you don't yet have a result for N % P; that would improve your order of efficiency without the potential big up-front cost.
use strict; use warnings; { my @bases = (2,3,5); my $product = 1; $product *= $_ for @bases; my @key; for my $test (0..$product-1) { $key[$test] = grep {$test % $_ == 0} @bases; } print "Key is <@key>\n"; my $iteration = 1; sub limbic_sequence { $iteration = shift if (@_); while ($iteration++) { return $iteration if ($key[$iteration % @key]); } } } print join ', ', map limbic_sequence, 1..50; print "\n"; printf "First after 100000 is: %d\n", limbic_sequence(100000); print join ', ', map limbic_sequence, 1..50; print "\n";

Caution: Contents may have been coded under pressure.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://440831]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (10)
As of 2017-06-23 22:02 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (555 votes). Check out past polls.