Math::NumberTheory

Raku package with Number theory functions.

The function names and features follow the Number theory functions of Wolfram Language.

Remark: Raku has some nice built-in Number theory functions, like, base, gcd, mod, polymod, expmod, is-prime. They somewhat lack generality, hence their functionalities are extended with this package. For example, is-prime works with lists and Gaussian integers.

Installation

From Zef ecosystem:

zef install Math::NumberTheory

From GitHub:

zef install https://github.com/antononcube/Raku-Math-NumberTheory

Usage examples

GCD

The infix operator gcd for calculating the Greatest Common Divisor (GCD) is extended to work with rational numbers and Gaussian integers:

Rationals

For rational numbers r1 and r2, r1 gcd r2 gives the greatest rational number r for which r1/r and r2/r are integers.

use Math::NumberTheory;
<1/3> gcd <2/5> gcd <1/7>
==> {.raku}()

# <1/105>

Gaussian integers

GCD for two Gaussian integers (complex numbers with integer real and imaginary parts):

(10 + 15i) gcd (-3 + 2i)

# -3+2i

105 gcd (7 + 49i)

# 7+14i

Here is verification of the latter:

say 105 / (7 + 14i);
say (7 + 49i) / (7 + 14i);

# 3-6i
# 3+1i

Prime number testing

The built-in sub is-prime is extended to work with Gaussian integers:

say is-prime(2 + 1i);
say is-prime(5, :gaussian-integers);

# True
# False

Another extension is threading over lists of numbers:

is-prime(^6)

# (False False True True False True)

Factor integers

Gives a list of the prime factors of an integer argument, together with their exponents:

factor-integer(factorial(20))

# [(2 18) (3 8) (5 4) (7 2) (11 1) (13 1) (17 1) (19 1)]

Remark: By default factor-integer uses Pollard's Rho algorithm -- specified with method => 'rho' -- as implemented at RosettaCode, [RC1], with similar implementations provided by "Prime::Factor", [SSp1], and "Math::Sequences", [RCp1].

Do partial factorization, pulling out at most k distinct factors:

factor-integer(factorial(20), 3, method => 'trial')

# [(2 18) (3 8) (5 4)]

Chinese remainders

Data:

my @data = 931074546, 117172357, 482333642, 199386034, 394354985;

# [931074546 117172357 482333642 199386034 394354985]

Keys:

#my @keys = random-prime(10**9 .. 10**12, @data.elems);
my @keys = 274199185649, 786765306443, 970592805341, 293623796783, 238475031661;

# [274199185649 786765306443 970592805341 293623796783 238475031661]

Remark: Using these larger keys is also a performance check.

Encrypted data:

my $encrypted = chinese-remainder(@data, @keys);

# 6681669841357504673192908619871066558177944924838942629020

Decrypted:

my @decrypted = @keys.map($encrypted mod *);

# [931074546 117172357 482333642 199386034 394354985]

Modular exponentiation and modular inversion

The sub power-mod extends the built-in sub expmod. The sub modular-inverse is based on power-mod.

expmod gives an error and no result when the 1st argument cannot be inverted with the last argument:

expmod(30, -1, 12)

#ERROR: Error in mp_exptmod: Value out of range
# Nil

power-mod returns Nil:

power-mod(30, -1, 12).defined

# False

Number-base related

There are several subs that provide functionalities related to number systems representation.

For example, here we find the digit-breakdown of :

100.&factorial.&digit-count

# {0 => 30, 1 => 15, 2 => 19, 3 => 10, 4 => 10, 5 => 14, 6 => 19, 7 => 7, 8 => 14, 9 => 20}

Here is an example of using real-digits:

real-digits(123.55555)

# ([1 2 3 5 5 5 5 5] 3)

Non-integer bases can be also used:

my $r = real-digits(π, ϕ);

# ([1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1] 3)

Here we recover from the Golden ratio representation obtained above:

$r.head.kv.map( -> $i, $d { $d * ϕ ** ($r.tail - $i - 1)  }).sum.round(10e-12);

# 3.1415926535899996

The sub phi-number-system can be used to compute Phi number system representations:

.say for (^7)».&phi-number-system

# ()
# (0)
# (1 -2)
# (2 -2)
# (2 0 -2)
# (3 -1 -4)
# (3 1 -4)

Remark: Because of the approximation of the Golden ratio used in “Math::NumberTheory”, in order to get exact integers from phi-digits we have to round using small multiples of 10.

CLI

The package provides the Command Line Interface (CLI) script number-theory. Here is its usage note:

number-theory --help

# Usage:
#   number-theory <function words...> [args...]
#   number-theory <function-words...> WHY
# 
# Examples:
#   number-theory is harshad number 23        # calls is-harshad-number(23)
#   number-theory is-happy-number 2026        # calls is-happy-number(2026)
#   number-theory divisor sigma 3 500         # calls divisor-sigma(3, 500)
#   number-theory divisor-sigma WHY           # prints &divisor-sigma.WHY
# 
# Known functions (from Math::NumberTheory):
#   abundant-number, are-coprime, chinese-remainder, cousin-primes, deficient-number, digit-count, divisor-sigma, divisors, euler-phi, factor-gaussian-integer, factor-integer, factorial, fibonacci, gcd-gaussian, gcd-rational, infix:<=>, integer-digits, integer-exponent, integer-partitions, is-abundant-number, is-composite, is-deficient-number, is-happy-number, is-harshad-number, is-perfect-number, is-prime, is-prime-gaussian, is-prime-power, kronecker-delta, lcm-gaussian, lcm-rational, mangold-lambda, modular-inverse, multiplicative-order, next-prime, perfect-number, phi-number-system, polygonal-number, power-mod, prime, primitive-root-list, random-prime, real-digits, related-primes, sexy-primes, trial-factor-integer, twin-primes
# 
# True

The script takes proper sub names as a first argument or their "conversational" form. For example, these two commands invoke the same sub:

number-theory is-happy-number 2026

# True

Using ranges:

number-theory random-prime 400..440 6

# 409
# 401
# 401
# 439
# 439
# 431

TODO

• TODO Implementation

  • DONE Gaussian integers GCD

  • DONE Gaussian integers factorization

  • DONE Moebius Mu function, Liouville lambda function

    • DONE Integers

    • DONE Gaussian integers

  • DONE Square-free test

    • DONE Integers

    • DONE Gaussian integers

  • DONE Rational numbers GCD

  • DONE Multiplicative Order

  • DONE Gaussian integers LCM

  • DONE Rational numbers LCM

  • DONE Carmichael lambda

  • DONE Integer partitions

  • DONE Number classes tests and retrievers

    • DONE Abundant number

    • DONE Deficient number

    • DONE Perfect number

    • DONE Happy number

    • DONE Harshad number

  • TODO Sum of squares representation

  • TODO Figure out which memoization approach to use:

    • Via the package "Memoize"

    • Via use experimental :cached and sub blah(...) is cached {...}

  • DONE CLI

• TODO Documentation

  • DONE Blog post about Number theory properties of 2026.

  • TODO Blog post on first non-zero digit of 10_000!

  • TODO Videos

    • DONE Neat examples 1

    • DONE Neat examples 2

    • DONE Neat examples 3

      • See also the related posts [AA1, AAn4].

    • TODO Neat examples 4

    • TODO Neat examples 5

References

Articles, blog posts, wiki-pages

[AA1] Anton Antonov, "Primitive roots generation trails", (2025), MathematicaForPrediction at WordPress.

[AA2] Anton Antonov, "Day 22 – Numerically 2026 Is Unremarkable Yet Happy", (2025), Raku Advent Calendar at WordPress.

[RC1] Rosetta Code, Prime decomposition, Section "Pure Raku".

Notebooks

[AAn1] Anton Antonov, Number theory neat examples Set 1, presentation notebook, (2025), RakuForPrediction-blog at GitHub.

[AAn2] Anton Antonov, Number theory neat examples Set 2, presentation notebook, (2025), RakuForPrediction-blog at GitHub.

[AAn3] Anton Antonov, Number theory neat examples Set 3, presentation notebook, (2025), RakuForPrediction-blog at GitHub.

[AAn4] Anton Antonov, "Primitive roots generation trails", (2025), Wolfram Community.

Packages

[RCp1] Raku Community, Math::Sequences Raku package, (2016-2024), GitHub/raku-community-modules.

[SSp1] Stephen Schulze, Prime::Factor Raku package, (2016-2023), GitHub/thundergnat.

Videos

[AAv1] Anton Antonov, "Number theory neat examples in Raku (Set 1)", (2025), YouTube/@AAA4prediction.

[AAv2] Anton Antonov, "Number theory neat examples in Raku (Set 2)", (2025), YouTube/@AAA4prediction.

[AAv3] Anton Antonov, "Number theory neat examples in Raku (Set 3)", (2025), YouTube/@AAA4prediction.