numbertheory

package
v0.0.10 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 10, 2023 License: BSD-3-Clause Imports: 4 Imported by: 1

Documentation

Overview

Package numbertheory is maths primarily concerned with integers and integer-valued functions.

https://en.wikipedia.org/wiki/Number_theory

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func AliquotSum 

func AliquotSum[A maths.Integer](n A) uint64

AliquotSum returns the sum of all proper divisors of n (all divisors except n itself).

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Aliquot_sum

https://oeis.org/A001065

Example 
n := AliquotSum(60)
fmt.Printf("The aliquot sum of 60 is %v.\n", n)

Output:

The aliquot sum of 60 is 108.

func Coprime added in v0.0.8 

func Coprime[A maths.Integer](a, b A) bool

Coprime returns whether two integers share no common divisors other than 1.

Time complexity: O(log n) - where n is whichever number is smaller Space complexity: O(1)

https://en.wikipedia.org/wiki/Coprime_integers

Example 
a := 2 * 3 * 5
b := 7 * 11 * 13
r := Coprime(a, b)
fmt.Printf("coprime(%d, %d) is %v.\n", a, b, r)

Output:

coprime(30, 1001) is true.

func DigitSum added in v0.0.8 

func DigitSum[A maths.Integer](n, b A) A

DigitSum returns the sum of the individual digits of n within the given radix/base.

If b=1, returns n (unary numeral system)

If b<1 or n<=0, returns 0. Caller can verify it was an error by checking if n>0. A future version of this function may handle negative n.

Time complexity: O(log_b n) Space complexity: O(1)

https://en.wikipedia.org/wiki/Digit_sum

Example 
n := DigitSum(9045, 10)
fmt.Printf("The digit sum of 9045 in base-10 is %v.\n", n)

Output:

The digit sum of 9045 in base-10 is 18.

func DigitalRoot added in v0.0.8 

func DigitalRoot[A maths.Integer](n, b A) A

DigitalRoot returns a single digit after iteratively summing the digits of n in a given radix/base.

Time complexity: O(1) Space complexity: O(1)

https://en.wikipedia.org/wiki/Digital_root

Example 
n := DigitalRoot(9045, 10)
fmt.Printf("The digital root of 9045 in base-10 is %v.\n", n)

Output:

The digital root of 9045 in base-10 is 9.

func ExtendedGCD added in v0.0.10 

func ExtendedGCD[Integer maths.Integer](a, b Integer) (Integer, Integer, Integer)

ExtendedGCD computes the GCD and the coefficients of Bézout's identity for integers a and b, which are the integers x and y such that ax + by = gcd(a,b).

Time complexity: O(log n) Space complexity: O(1)

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Example 
gcd, x, y := ExtendedGCD(48, 18)
fmt.Printf("The extended GCD of 18 and 48 is (%v, %v, %v).", gcd, x, y)

Output:

The extended GCD of 18 and 48 is (6, -1, 3).

func GCD added in v0.0.8 

func GCD[A maths.Integer](a, b A) A

GCD returns the largest positive integer that divides a and b.

Time complexity: O(log n) - where n is whichever number is smaller Space complexity: O(1)

https://en.wikipedia.org/wiki/Greatest_common_divisor

Example 
gcd := GCD(48, 18)
fmt.Printf("The GCD of 18 and 48 is %v.", gcd)

Output:

The GCD of 18 and 48 is 6.

func LCM added in v0.0.8 

func LCM[A maths.Integer](a, b A) A

LCM returns the smallest positive integer that is divisible by both a and b.

Time complexity: O(log n) - where n is whichever number is smaller Space complexity: O(1)

https://en.wikipedia.org/wiki/Least_common_multiple

Example 
lcm := LCM(48, 18)
fmt.Printf("The LCM of 18 and 48 is %v.", lcm)

Output:

The LCM of 18 and 48 is 144.

func Mobius 

func Mobius[A maths.Integer](n A) int8

Mobius (Möbius function μ(n)) returns 0 if n is not square-free, -1 if n is square-free and has an odd number of prime factors, or 1 if n is square-free and has an even number of prime factors.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Mobius_function

https://oeis.org/A008683

Example 
n := Mobius(70)
fmt.Printf("The möbius of 70 is %v.\n", n)

Output:

The möbius of 70 is -1.

func ModExp added in v0.0.10 

func ModExp[A maths.Integer](base, exponent, modulus A) int64

ModExp is exponentiation performed over a modulus.

Time complexity: O(log n) - where n is the exponent Space complexity: O(1)

https://en.wikipedia.org/wiki/Modular_exponentiation

Example 
n := ModExp(2, 256, 1_000_000_007)
fmt.Printf("The modular exponentiation of 2^256 %% (10^6+7) is %v.\n", n)

Output:

The modular exponentiation of 2^256 % (10^6+7) is 792845266.

func NumberOfDivisors 

func NumberOfDivisors[A maths.Integer](n A) uint64

NumberOfDivisors returns the number of divisors of n.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Divisor_function

https://oeis.org/A000005

Example 
n := NumberOfDivisors(48)
fmt.Printf("The number-of-divisors of 48 is %v.\n", n)

Output:

The number-of-divisors of 48 is 10.

func Politeness 

func Politeness[A maths.Integer](n A) uint64

Politeness returns the number of ways n can be expressed as the sum of consecutive numbers.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Polite_number

https://oeis.org/A069283

Example 
n := Politeness(42)
fmt.Printf("The politeness of 42 is %v.\n", n)

Output:

The politeness of 42 is 3.

func PolygonalNumber 

func PolygonalNumber[A maths.Integer, B maths.Integer](s A, n B) (uint64, error)

PolygonalNumber returns the nth s-gon number. If s < 3, returns an error.

Time complexity: O(1) Space complexity: O(1)

https://en.wikipedia.org/wiki/Polygonal_number

Example 
var n uint64 = 30
p, _ := PolygonalNumber(3, n)
fmt.Printf("The %vth triangular number is %v.\n", n, p)

p, _ = PolygonalNumber(4, n)
fmt.Printf("The %vth square number is %v.\n", n, p)

p, _ = PolygonalNumber(5, n)
fmt.Printf("The %vth pentagonal number is %v.\n", n, p)

Output:

The 30th triangular number is 465.
The 30th square number is 900.
The 30th pentagonal number is 1335.

func PolygonalRoot 

func PolygonalRoot[A maths.Integer, B maths.Integer](s A, x B) (float64, error)

PolygonalRoot returns the s-gonal root of x. If s < 3, returns an error.

Time complexity: O(1) Space complexity: O(1)

https://en.wikipedia.org/wiki/Polygonal_number

Example 
var x uint64 = 465
p, _ := PolygonalRoot(3, x)
fmt.Printf("The triangular root of %v is %v.\n", x, p)

x = 900
p, _ = PolygonalRoot(4, x)
fmt.Printf("The square root of %v is %v.\n", x, p)

x = 1335
p, _ = PolygonalRoot(5, x)
fmt.Printf("The pentagonal root of %v is %v.\n", x, p)

Output:

The triangular root of 465 is 30.
The square root of 900 is 30.
The pentagonal root of 1335 is 30.

func PolygonalSides 

func PolygonalSides[A maths.Integer, B maths.Integer](n A, x B) float64

PolygonalSides returns the number of sides that the nth polygonal number with a value of x has.

Time complexity: O(1) Space complexity: O(1)

https://en.wikipedia.org/wiki/Polygonal_number

Example 
var x uint64 = 465
p := PolygonalSides(30, x)
fmt.Printf("The 30th polygonal number that has a value of %v has %v sides.\n", x, p)

x = 900
p = PolygonalSides(30, x)
fmt.Printf("The 30th polygonal number that has a value of %v has %v sides.\n", x, p)

x = 1335
p = PolygonalSides(30, x)
fmt.Printf("The 30th polygonal number that has a value of %v has %v sides.\n", x, p)

Output:

The 30th polygonal number that has a value of 465 has 3 sides.
The 30th polygonal number that has a value of 900 has 4 sides.
The 30th polygonal number that has a value of 1335 has 5 sides.

func PrimeFactorization 

func PrimeFactorization[A maths.Integer](n A) []uint64

PrimeFactorization returns the prime factorization of n.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Integer_factorization

Example 
var n uint64 = 51561510
r := PrimeFactorization(n)
fmt.Printf("The prime factorization of %v is %v.\n", n, r)

Output:

The prime factorization of 51561510 is [2 3 5 7 11 13 17 101].

func Primorial added in v0.0.4 

func Primorial[A maths.Integer](n A) (uint64, error)

Primorial returns the product of all primes up to n. n must be 0 <= n <= 52.

Time complexity: O(1) Space complexity: O(1)

https://en.wikipedia.org/wiki/Primorial

https://oeis.org/A002110

Example 
n, _ := Primorial(30)
fmt.Printf("The primorial of 30 is %v.\n", n)

Output:

The primorial of 30 is 6469693230.

func Radical 

func Radical[A maths.Integer](n A) uint64

Radical returns the product of the distinct primes dividing n.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Radical_of_an_integer

https://oeis.org/A007947

Example 
r := Radical(60)
fmt.Printf("The radical of 60 is %v.\n", r)

Output:

The radical of 60 is 30.

func SumOfDivisors 

func SumOfDivisors[A maths.Integer](n A) uint64

SumOfDivisors returns the sum of the divisors of n.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Divisor_function

https://oeis.org/A000203

Example 
r := SumOfDivisors(60)
fmt.Printf("The sum-of-divisors of 60 is %v.\n", r)

Output:

The sum-of-divisors of 60 is 168.

func Totient 

func Totient[A maths.Integer](n A) uint64

Totient (Euler's totient) returns the number of positive integers up to a given integer n that are relatively prime to n.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Euler's_totient_function

https://oeis.org/A000010

Example 
r := Totient(60)
fmt.Printf("Euler's totient of 60 is %v.\n", r)

Output:

Euler's totient of 60 is 16.

func TotientK 

func TotientK[A maths.Integer, B maths.Integer](n A, k B) uint64

TotientK (Jordan's totient) returns the number of k-tuples of positive integers that are less than or equal to n and that together with n form a coprime set of k + 1 integers.

Time complexity: O(sqrt n) Space complexity: O(log n)

https://en.wikipedia.org/wiki/Jordan's_totient_function

https://oeis.org/A007434 (k=2)

Example 
r := TotientK(60, 2)
fmt.Printf("The J₂ of 60 is %v.", r)

Output:

The J₂ of 60 is 2304.

Types

This section is empty.

Source Files

View all Source files

Directories

Path Synopsis
Package primefactorization is maths primarily concerned with the prime factorization of an integer as well as functions that can easily be computed when the prime factorization of an integer is already known.
 Package primefactorization is maths primarily concerned with the prime factorization of an integer as well as functions that can easily be computed when the prime factorization of an integer is already known.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.