view release on metacpan or  search on metacpan

lib/Math/Prime/Util.pm  view on Meta::CPAN

amount of time for large inputs.  Calculating the C<10^12th> prime takes
about 1 second, the C<10^13th> prime takes under 10 seconds, and the
C<10^14th> prime (3475385758524527) takes under 30 seconds.  Think about
whether a bound or approximation would be acceptable, as they can be
computed analytically.

If the result is larger than a native integer size (32-bit or 64-bit), the
result will take a very long time.  A later version of
L<Math::Prime::Util::GMP> may include this functionality which would help for
32-bit machines.


=head2 nth_prime_upper

Returns a proven upper bound on the Nth prime.
See L</nth_prime_lower> for details common to both functions.

=head2 nth_prime_lower

  my $lower_limit = nth_prime_lower($n);
  my $upper_limit = nth_prime_upper($n);
  # For all $n:   $lower_limit  <=  nth_prime($n)  <=  $upper_limit

Returns a proven lower bound on the Nth prime.  No sieving is
done, so these are fast even for large inputs.

For tiny values of C<n>. exact answers are returned.  For small inputs, an
inverse of the opposite prime count bound is used.  For larger values, the
Dusart (2010) and Axler (2013) bounds are used.


=head2 nth_prime_approx

  say "The one trillionth prime is ~ ", nth_prime_approx(10**12);

Returns an approximation to the C<nth_prime> function, without having to
generate any primes.  For values where the nth prime is smaller than
C<2^64>, the inverse Riemann R function is used.  For larger values,
the inverse logarithmic integral is used.

The value returned will not necessarily be prime.  This applies to all
the following nth prime approximations, where the returned value is
close to the real value, but no effort is made to coerce the result
to the nearest set element.


=head2 nth_twin_prime

Returns the Nth twin prime.  This is done via sieving and counting, so
is not very fast for large values.

=head2 nth_twin_prime_approx

Returns an approximation to the Nth twin prime.  A curve fit is used for
small inputs (under 1200), while for larger inputs a binary search is done
on the approximate twin prime count.

=head2 nth_semiprime

Returns the Nth semiprime, similar to where a C<forsemiprimes> loop would
end after C<N> iterations, but much more efficiently.

=head2 nth_semiprime_approx

Returns an approximation to the Nth semiprime.  The approximation is
orders of magnitude better than the simple C<n log n / log log n>
approximation for large C<n>.  E.g. for C<n=10^12> the simple estimate
is within 3.6%, but this function is within 0.000012%.

=head2 nth_almost_prime

  say "500th number with exactly 3 factors: ", nth_almost_prime(3,500);

A C<k>-almost prime is a product of C<k> prime numbers,
counted with multiplicity.  That is, there are exactly C<k> prime
factors (which do not have to be distinct from each other).

Given non-negative integers C<k> and C<n>, returns the
C<n>-th C<k>-almost prime.
With C<k=1> this is the nth prime.
With C<k=2> this is the nth semiprime.

The implementation does a binary search lookup with
L</almost_prime_count> so is reasonably efficient for large values.

C<undef> is returned for C<n == 0> and for all C<k == 0>
other than C<n == 1>.

=head2 nth_almost_prime_approx

A fast approximation of the C<n>-th C<k>-almost prime.

=head2 nth_almost_prime_lower

Quickly returns a lower bound for the C<n>-th C<k>-almost prime.
The actual nth k-almost-prime will be greater than or equal to this result.

=head2 nth_almost_prime_upper

Quickly returns an upper bound for the C<n>-th C<k>-almost prime.
The actual nth k-almost-prime will be less than or equal to this result.


=head2 nth_omega_prime

Given non-negative integers C<k> and C<n>, returns the
C<n>-th C<k>-omega prime.
This is the C<n>-th integer divisible by exactly C<k> different primes.

The implementation does a binary search lookup with
L</omega_prime_count> so is reasonably efficient for large values.

C<undef> is returned for C<n == 0> and for all C<k == 0>
other than C<n == 1>.


=head2 nth_ramanujan_prime

Returns the Nth Ramanujan prime.  For reasonable size values of C<n>, e.g.
under C<10^8> or so, this is relatively efficient for single calls.  If
multiple calls are being made, it will be much more efficient to get the

lib/Math/Prime/Util.pm  view on Meta::CPAN

Given a non-negative integer C<n>, returns the C<n>-th lucky number.
This is done by sieving lucky numbers to C<n> then performing
a reverse calculation to determine the value at the nth position.
This is much more efficient than generating all the lucky numbers
up to the nth position, but is much slower than L</nth_prime>.

=head2 nth_lucky_approx

Given a single non-negative integer C<n>, quickly returns a
good estimate of the C<n>-th lucky number.

=head2 nth_lucky_lower

Given a single non-negative integer C<n>, quickly returns a
lower bound of the C<n>-th lucky number.
The actual value will always be greater than or equal to the result.

=head2 nth_lucky_upper

Given a single non-negative integer C<n>, quickly returns an
upper bound of the C<n>-th lucky number.
The actual value will always be less than or equal to the result.


=head2 minimal_goldbach_pair

Given a single non-negative integer C<n>, returns the smallest prime C<p>
such that C<p + q = n> and both C<p> and C<q> are primes.
Only the single value C<p> is returned, with C<q = n-p> and C<< p <= q >>.
Both C<p> and C<q> are prime.

C<undef> is returned if no such C<p> exists.  This will happen for values
less than C<4> and for all odd C<n> where C<n != 2+q> for a prime C<q>.
The Goldbach Conjecture famously states that a C<p> exists for
all even C<n> greater than C<2>.

This function is reasonably fast even for larger values of C<n> as it can
terminate after the first pair is found.  On Macbook M1, average time is
under 1 microsecond for 32-bit even inputs, under 10 microseconds for 64-bit
even inputs, and 1 millisecond for 105 bit even inputs.

=head2 goldbach_pair_count

Given a single non-negative integer C<n>, returns the number of pairs of
primes C<p> and C<q> where C<< p <= q >> and C<< p + q = n >>.

If no such pairs exist, C<0> is returned.

=head2 goldbach_pairs

Given a single non-negative integer C<n>, returns a list containing each C<p>
for all prime pairs C<p> and C<q> where C<< p <= q >> and C<p + q = n>.
The number of elements returned is the same as L</goldbach_pair_count>.

If no such pairs exist, an empty list is returned.


=head2 is_happy

Given a single non-negative integer C<n>, returns the number of iterations
required for the map of sum of squared base-10 digits to converge to C<1>,
or C<0> if it does not converge to the value C<1>.

This returns the height using the OEIS A090425 definition of height, which is
zero for non-happy numbers, 1 for C<n=1>, 2 for numbers that produce 1 after
a single iteration, etc.
This is one more than the definitions used in many papers
(e.g. Cai and Zhou 2008) where C<n=1> is considered to have height 0.

An optional base and exponent may be given (default base 10 exponent 2).
The base must be between 2 and 36, and the exponent between 0 and 10.
The input C<n> is read as a decimal number, so giving input such as "1001"
will be treated as the decimal C<1001> regardless of base.

With base 10 and exponent 2,
non-zero values produce L<OEIS series A007770|http://oeis.org/A007770>.
The values themselves produce L<OEIS series A090425|http://oeis.org/A090425>.



=head2 is_smooth

  my $is_23_smooth = is_smooth($n, 23);

Given two non-negative integer inputs C<n> and C<k>,
returns C<1> if C<|n|> is C<k>-smooth, and C<0> otherwise.
This uses the OEIS definition: Returns true if no prime factors
of C<n> are larger than C<k>.

The values for C<n=0> and C<n=1> use the definition along with noting
that C<factor(0)> returns 0 and C<factor(1)> returns an empty list.

The result is identical to:

  sub is_smooth { my($n,$k)=@_; return 0+(vecnone { $_ > $k } factor($n)); }

but shortcuts are taken to avoid fully factoring if possible.

This corresponds to Mathematica's C<SmoothIntegerQ[n]> resource function.

=head2 is_rough

  my $is_23_rough = is_rough($n, 23);

Given two non-negative integer inputs C<n> and C<k>,
returns C<1> if C<|n|> is C<k>-rough, and C<0> otherwise.
This uses the OEIS definition: Returns true if no prime factors
of C<n> are smaller than C<k>.

The values for C<n=0> and C<n=1> use the definition along with noting
that C<factor(0)> returns 0 and C<factor(1)> returns an empty list.

The result is identical to:

  sub is_rough { my($n,$k)=@_; return 0+(vecnone { $_ < $k } factor($n)); }

but shortcuts are taken to avoid fully factoring if possible.


=head2 is_powerful