Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

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.


Comment on Re^4: Challenge: Another Infinite Lazy List
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://440831]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2015-07-30 01:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls