view release on metacpan or  search on metacpan

lib/Math/NumSeq/ErdosSelfridgeClass.pm  view on Meta::CPAN

  my ($self, $i) = @_;

  Math::NumSeq::Primes->pred($i)
      or return 0;

  my $offset = ($self->{'p_or_m'} eq '+' ? 1 : -1);
  my $ret = 0;
  my @this = ($i);
  while (@this) {
    $ret++;
    my %next;
    foreach my $prime (@this) {
      my ($good, @primes) = _prime_factors($prime + $offset);
      return undef unless $good;

      @next{@primes} = ();  # hash slice, for uniq
    }
    delete @next{2,3}; # hash slice, not 2 or 3
    @this = keys %next;
  }
  return $ret;
}

sub pred {
  my ($self, $value) = @_;
  return ($value >= 0
          && $value == int($value));
}

1;
__END__

=for stopwords Ryde Math-NumSeq ie Erdos Selfridge Erdos-Selfridge

=head1 NAME

Math::NumSeq::ErdosSelfridgeClass -- Erdos-Selfridge classification of primes

=head1 SYNOPSIS

 use Math::NumSeq::ErdosSelfridgeClass;
 my $seq = Math::NumSeq::ErdosSelfridgeClass->new;
 my ($i, $value) = $seq->next;

=head1 DESCRIPTION

This is a class number for primes by Erdos and Selfridge, or 0 for
composites.  The default is "class+"

    0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 1, 0, 2, 0, 0, ...
    starting i=1,

A prime p is classified by factorizing p+1 into primes, then on each of
those primes q factorizing q+1, and so on, repeating until reaching entirely
2s and 3s.  p=2 or p=3 interchange on factorizing p+1 (2+1=3 and 3+1=2*2).

A prime p where p+1 factorizes to all 2s or 3s is class 1.  For example i=11
has 11+1=12=2*2*3 which is all 2s and 3s so class 1.  2 and 3 themselves are
class 1 too, since their p+1 factorizing gives 2s and 3s.

Further primes are classified by how many iterations of the p+1 factorizing
is necessary to reach 2s and 3s.  For example prime p=3847 is iterated as

    3847+1 = 2*13*37

    then 13+1 = 2*7
         37+1 = 2*19

    then 7+1 = 2*2*2
         19+1 = 2*2*5

    then 5+1 = 2*3

So 3847 is class 4 as it took 4 steps to reach all 2s and 3s.  Some of the
factors become 2s and 3s earlier, but the steps continue until all factors
are reduced to 2s and 3s.

=head2 Class -

Option C<p_or_m =E<gt> '-'> applies the same procedure to prime
factors of p-1, giving a "class-" number.

    0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, ...

It sometimes happens that class+ is the same as class-, but in general the
two are unrelated.

=head2 Primes Only

Option C<on_values =E<gt> 'primes'> selects the classes of just the
primes,

    1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 2, 1, 1, 2, 2, 2, 1, 4, ...

=head1 FUNCTIONS

See L<Math::NumSeq/FUNCTIONS> for behaviour common to all sequence classes.

=over 4

=item C<$seq = Math::NumSeq::ErdosSelfridgeClass-E<gt>new ()>

=item C<$seq = Math::NumSeq::ErdosSelfridgeClass-E<gt>new (p_or_m =E<gt> $str, on_values =E<gt> $str)>

Create and return a new sequence object.

C<p_or_m> (a string) can be

    "+"    factors of p+1 (the default)
    "-"    factors of p-1

C<on_values> (a string) can be

    "all"      classify all integers
    "primes"   classify just the primes

=back

=head2 Random Access

=over