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 browsing the Monastery: (9)
As of 2014-09-17 11:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (73 votes), past polls