Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^2: Elegantly map fizz to buzz

by oiskuu (Hermit)
on May 17, 2016 at 21:04 UTC ( [id://1163266]=note: print w/replies, xml ) Need Help??


in reply to Re: Elegantly map fizz to buzz
in thread Elegantly map fizz to buzz

Hi, I see you've attempted to generalize the problem by passing the moduli along as arguments. However, this complicates the matters considerably. Numbers multiple of some value form a set; all possible intersections of those form a powerset. E.g. for (3, 5, 7) you have the 305071, 305170, ..., 315171 subsets to consider.

Here's my attempt at a generic version. I'm not quite sure if it's sound in principle. (Now where are the resident mathematicians?)

#! /usr/bin/perl -wl use feature qw( signatures ); no warnings qw( experimental::signatures ); use List::Util qw( sum0 product reduce any ); sub gcd($a, $b) { !$b ? $a : gcd($b, $a % $b) } sub lcm { reduce { $a * $b / gcd($a, $b) } @_ } sub fk1($max, @A) { sum0 grep { my $x = $_; any {$x % $_ == 0} @A } 1 .. $max } sub fk2($max, @A) { sum0 map { (parity($_) || -1) * sum_every_nth($max, lcm_select($_, @A)) } 1 .. (1<<@A)-1 } sub sum_every_nth($max, $n) { int($max/$n) * int($max/$n + 1) / 2 * $n } sub lcm_select($sel, @A) { lcm @A[grep {$sel>>$_ & 1} 0..$#A] } sub parity { unpack "%1b*", pack "J", shift } my @A = (3, 5, 74017, 74027, 74047, 74077); print join ' ', 0+$_, fk1($_, @A), fk2($_, @A) while <>;
Again, the naive version and a smarter one. Subseries are summed with alternating signs according to cardinality: that way each number is tallied exactly once in the end.

Where the guarantee is given that moduli are mutually prime, one can use product() instead of lcm(). Then, if the limit $max is much greater than lcm(@A), one may reduce it first: e.g. with lcm(3, 5) you have a wheel15 going on. Etc. Talk about trivial exercises...

Replies are listed 'Best First'.
Re^3: Elegantly map fizz to buzz
by BrowserUk (Patriarch) on May 17, 2016 at 21:37 UTC
    to generalize the problem by passing the moduli along as arguments.

    If I've understood the task correctly, I think you're working the math too hard:

    sub x{ my $v=shift; my $t=0; $t += !!($v%$_) for @_; return $t!=@_ };; sub fn{ my$n; x($_, @_) and $n+=$_ for 1 .. shift; $n };; print fn( 10, 3, 5 );; 33 print fn( 10, 3, 5, 7 );; 40 print fn( 100000, 3, 5, 7, 74017, 74027, 74047, 74077 );; 2714660445

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
    In the absence of evidence, opinion is indistinguishable from prejudice.

      I suppose it would've been sensible to include use bigint; in my examples. (And make use of Math::BigInt::blcm.)

      print fn( 1e75, 3, 5, 7, 74017, 74027, 74047, 74077 );;

      All contributions are equally welcome, of course.

      Update. using bigint:

      print fk2( 1e75, 3, 5, 7, 74017, 74027, 74047, 74077 );; 2714409193835116782309092860748312946665048449396007497681808465165668 +014761062261823426471676870303814322114698720811164640573956951947124 +37887594397

        I suppose it would've been sensible to include use bigint;

        Wouldn't help very much with 1e75:

        Range iterator outside integer range at ...

        From this line of your code above:

        } 1 .. $max

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2024-03-29 13:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found