path: root/factors/digit_map.go

/* This script is part of radix_info.
   Copyright (C) 2023  Adrien Hopkins

   This program is free software: you can redistribute it and/or modify
   it under the terms of version 3 of the GNU General Public License
   as published by the Free Software Foundation.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.
*/

package factors

import "fmt"

/*
A DigitType represents the number-theoretical type of a digit in a radix.
It is composed of two parts:
  - The regularity index, which is the exponent of the smallest power
    of the radix that the digit's regular part (as defined by [Split])
    is a factor of.
  - The totative type, which is the [TotativeType] of
    the radix's totative part (as defined by [Split]).

The zero value of DigitType is the type 00,
the type that the digit zero has in every nonzero radix.
*/
type DigitType struct {
	regularity   uint8
	totativeType TotativeType
}

// TotativeType classifies the totative parts (as determined by [Split])
// of digits in radices.
type TotativeType byte

const (
	// This number does not have any totative factors
	Regular TotativeType = 0xC0
	// This number's totative part is divisible by (r - 1)
	// - this gives it the simplest possible decimal expansion
	// for a non-regular (1 digit repeating) and a simple divisibility
	// test (sum digits, like 3 or 9 in decimal)
	Omega TotativeType = 0xA0
	// This number's totative part is divisible by (r + 1)
	// - this makes it slightly more complicated than omega
	Alpha TotativeType = 0x80
	// This number's totative part is divisible by (r^2 - 1)
	// but not (r + 1) or (r - 1)
	// - these totatives straddle the line between simple and complex
	Pseudoneighbour TotativeType = 0x60
	// This number's totative part is not divisible by (r^2 - 1)
	// - it will not be nice to work with
	Opaque TotativeType = 0x40
	// This number is zero, and doesn't have a true totative type.
	// (except in radix zero, where zero is considered a factor)
	Zero TotativeType = 0x00
)

// Zero and one will always have these types.
var (
	zeroType = DigitType{regularity: 0, totativeType: Zero}
	oneType  = DigitType{regularity: 0, totativeType: Regular}
)

// Above this number, regularity indices will be shown as '+'
// instead of the number; this is to keep the code 2 characters long
const maxDisplayRegularity = 7

// The regularity index of a number in a radix - the smallest power of the
// radix that is divisible by the number's regular part.
//
// If this is zero, and the digit isn't, this digit is a totative.
func (dt DigitType) Regularity() uint8 { return dt.regularity }

// TotativeType returns the type of a number's totative part in a radix.
// This is one of the possible values of [TotativeType].
func (dt DigitType) TotativeType() TotativeType { return dt.totativeType }

// String returns a string representation of the digit type.
//
// This representation is a two-character code.
// The first character is the type's [DigitType.Regularity],
// or "+" if it is above 7.
// The second character is a character representing the [TotativeType]:
//   - [Regular] is 'R'
//   - [Omega] is 'ω'
//   - [Alpha] is 'α'
//   - [Pseudoneighbour] is 'N'
//   - [Opaque] is 'P' (to avoid confusing it with [Zero])
//   - [Zero] is '0'
func (dt DigitType) String() string {
	var rString string
	if dt.regularity > maxDisplayRegularity {
		rString = "+"
	} else {
		rString = fmt.Sprint(dt.regularity)
	}

	var tString string
	switch dt.totativeType {
	case Zero:
		tString = "0"
	case Regular:
		tString = "R"
	case Omega:
		tString = "ω"
	case Alpha:
		tString = "α"
	case Pseudoneighbour:
		tString = "N"
	case Opaque:
		tString = "P"
	}

	return rString + tString
}

// Splits a digit in a radix into its regular and totative parts
func splitPF(digit, radix PrimeFactorization) (regular, totative uint) {
	regular, totative = 1, 1
	for p, e := range digit.exponents {
		if radix.exponents[p] != 0 {
			regular *= uintpow(p, e)
		} else {
			totative *= uintpow(p, e)
		}
	}
	return regular, totative
}

/*
Split splits a digit in a radix into its regular and totative parts.
The regular part will be a divisor of some power of the radix.
The totative part will be coprime to the radix,
except if the digit or radix are zero.
The product of the regular and totative parts will be equal to the digit.

Special cases (follow from PrimeFactorize(0) = 0^1):

	Split(0, x) = 1, 0
	Split(x, 0) = 1, x
	Split(0, 0) = 0, 1
*/
func Split(digit, radix uint) (regular, totative uint) {
	return splitPF(PrimeFactorize(digit), PrimeFactorize(radix))
}

// Calculates the regularity index of a number's regular part
func calcRegularity(regular, radix uint) uint8 {
	if regular == 0 && radix == 0 {
		return 1
	}

	regularity, radixPower := uint8(0), uint(1)
	for radixPower%regular != 0 {
		regularity++
		radixPower *= radix
	}
	return regularity
}

// Calculates the totative type of a number's totative part
func calcTotativeType(totative, radix uint) TotativeType {
	switch true {
	case totative == 0:
		return Zero
	case totative == 1:
		return Regular
	case (radix-1)%totative == 0:
		return Omega
	case (radix+1)%totative == 0:
		return Alpha
	case (radix*radix-1)%totative == 0:
		return Pseudoneighbour
	default:
		return Opaque
	}
}

// Gets the regularity and totative type of one digit in a radix.
//
// In radix zero, zero is type 1R, one is type 0R, and everything else is 0P.
func GetDigitType(digit, radix uint) DigitType {
	radixPF := PrimeFactorize(radix)
	digitPF := PrimeFactorize(digit)
	regular, totative := splitPF(digitPF, radixPF)
	regularity := calcRegularity(regular, radix)
	totativeType := calcTotativeType(totative, radix)
	return DigitType{regularity, totativeType}
}

// DigitMap gets the [DigitType] of every digit in a radix.
//
// DigitMap(0) returns an empty slice.
func DigitMap(radix uint) []DigitType {
	radixPF := PrimeFactorize(radix)
	types := make([]DigitType, radix, radix)
	if radix > 0 {
		types[0] = zeroType
	}
	if radix > 1 {
		types[1] = oneType
	}
	for d := uint(2); d < radix; d++ {
		digitPF := PrimeFactorize(d)
		regular, totative := splitPF(digitPF, radixPF)
		regularity := calcRegularity(regular, radix)
		totativeType := calcTotativeType(totative, radix)
		types[d] = DigitType{regularity, totativeType}
	}
	return types
}