View source for Mixed radix

{{Short description|Type of numeral systems}}
{{numeral systems}}
{{More footnotes|date=July 2021}}

'''Mixed radix''' [[numeral system]]s are [[non-standard positional numeral systems]] in which the numerical [[radix|base]] varies from position to position. Such numerical representation applies when a quantity is expressed using a sequence of units that are each a multiple of the next smaller one, but not by the same factor. Such units are common for instance in measuring time; a time of 32 weeks, 5 days, 7 hours, 45 minutes, 15 seconds, and 500 milliseconds might be expressed as a number of minutes in mixed-radix notation as:

 ... 32, 5, 07, 45; 15,  500
 ...  ∞, 7, 24, 60; 60, 1000

or as

:32<sub>∞</sub>5<sub>7</sub>07<sub>24</sub>45<sub>60</sub>.15<sub>60</sub>500<sub>1000</sub>

In the tabular format, the digits are written above their base, and a [[semicolon]] indicates the [[radix point]].  In numeral format, each digit has its associated base attached as a subscript, and the radix point is marked by a [[full stop|full stop or period]]. The base for each digit is the number of corresponding units that make up the next larger unit. As a consequence there is no base (written as ∞) for the first (most significant) digit, since here the "next larger unit" does not exist (and one could not add a larger unit of "month" or "year" to the sequence of units, as they are not integer multiples of "week").

==Examples==
The most familiar example of mixed-radix systems is in timekeeping and calendars. Western time radices include, both cardinally and ordinally, [[decimal]] years, decades, and centuries, [[septenary]] for days in a week, [[duodecimal]] months in a year, bases 28–31 for days within a month, as well as base 52 for weeks in a year. Time is further divided into hours counted in [[base 24]] hours, [[sexagesimal]] minutes within an hour and seconds within a minute, with decimal fractions of the latter.

A standard form for dates is {{samp|2021-04-10 16:31:15}}, which would be a mixed radix number by this definition, with the consideration that the quantities of days vary both per month, and with leap years. One proposed calendar instead uses [[base 13]] months, [[Quaternary numeral system|quaternary]] weeks, and septenary days.

A mixed radix numeral system is often best expressed with a table. A table describing what can be understood as the 604800 seconds of a week is as follows, with the week beginning on hour 0 of day 0 (midnight on Sunday):

{| class="wikitable" style="text-align:right;"
! {{rh}} | Radix                
|     7 ||   24 ||     60 ||     60
|-
! {{rh}} | Denomination         
|   day || hour || minute || second
|-
! {{rh}} | Place value (seconds)
| 86400 || 3600 ||    60  ||      1
|}

In this numeral system, the mixed radix numeral 3<sub>7</sub>17<sub>24</sub>51<sub>60</sub>57<sub>60</sub> seconds would be interpreted as 17:51:57 on Wednesday, and 0<sub>7</sub>0<sub>24</sub>02<sub>60</sub>24<sub>60</sub> would be 00:02:24 on Sunday.  Ad hoc notations for mixed radix numeral systems are commonplace.

The [[Maya calendar]] consists of several overlapping cycles of different radices. A short count ''[[tzolk'in]]'' overlaps [[base 20]] named days with [[base 13|tridecimal]] numbered days. A ''[[haab']]'' consists of vigesimal days, [[octodecimal]] ''months'', and base-52 years forming a ''round''. In addition, a ''long count'' of vigesimal days, octodecimal ''winal'', then base 24 ''tun'', ''k'atun'', ''b'ak'tun'', etc., tracks historical dates.

A second example of a mixed-radix numeral system in current use is in the design and use of currency, where a limited set of denominations are printed or minted with the objective of being able to represent any monetary quantity; the amount of money is then represented by the number of coins or banknotes of each denomination. When deciding which denominations to create (and hence which radices to mix), a compromise is aimed for between a minimal number of different denominations, and a minimal number of individual pieces of coinage required to represent typical quantities.  So, for example, in the UK, banknotes are printed for £50, £20, £10 and £5, and coins are minted for £2, £1, 50p, 20p, 10p, 5p, 2p and 1p—these follow the [[Preferred values#1-2-5 series|1-2-5 series of preferred values]].

Prior to [[Pound Sterling#Decimalisation|decimalisation]], monetary amounts in the UK were described in terms of pounds, shillings, and pence, with 12 pence per shilling and 20 shillings per pound, so that "£1 7s 6d", for example, corresponded to the mixed-radix numeral 1<sub>∞</sub>7<sub>20</sub>6<sub>12</sub>.

[[United States customary units]] are generally mixed radix systems, with multipliers varying from one size unit to the next in the same manner that units of time do.

Mixed-radix representation is also relevant to mixed-radix versions of the [[Cooley–Tukey FFT algorithm]], in which the indices of the input values are expanded in a mixed-radix representation, the indices of the output values are expanded in a corresponding mixed-radix representation with the order of the bases and digits reversed, and each subtransform can be regarded as a Fourier transform in one digit for all values of the remaining digits.

==Manipulation==
Mixed-radix numbers of the same base can be manipulated using a generalization of manual arithmetic algorithms.  Conversion of values from one mixed base to another is easily accomplished by first converting the place values of the one system into the other, and then applying the digits from the one system against these.

[[APL programming language|APL]] and [[J programming language|J]] include operators to convert to and from mixed-radix systems.

== Factorial number system ==
{{main|Factorial number system}}

Another proposal is the so-called [[factorial]] number system:

{| class="wikitable" style="text-align:right;"
|-
! {{rh}} | Radix                    
|    8 ||   7 ||   6 ||  5 ||  4 ||  3 ||  2 || 1
|-
! {{rh}} | Place value              
|   7! ||  6! ||  5! || 4! || 3! || 2! || 1! || 0!
|-
! {{rh}} | Place value in decimal   
| 5040 || 720 || 120 || 24 ||  6 ||  2 ||  1 || 1
|-
! {{rh}} | Highest digit allowed    
|    7 ||   6 ||   5 ||  4 ||  3 ||  2 ||  1 || 0
|}

For example, the biggest number that could be represented with six digits would be 543210 which equals 719 in [[decimal]]: 5&times;5! + 4&times;4! + 3&times;3! + 2&times;2! + 1&times;1! It might not be clear at first sight but the factorial based numbering system is unambiguous and complete. Every number can be represented in one and only one way because the sum of respective factorials multiplied by the index is always the next factorial minus one:

: <math> \sum_{i=0}^{n} (([i+1]+1)-1) \cdot ([i]+1)! = ([n+1]+1)! - 1 </math>

There is a natural mapping between the integers 0, ..., ''n''!&nbsp;&minus;&nbsp;1 and [[permutation]]s of ''n'' elements in lexicographic order, which uses the factorial representation of the integer, followed by an interpretation as a [[Permutations#Numbering permutations|Lehmer code]].

The above equation is a particular case of the following general rule for any radix (either standard or mixed) base representation which expresses the fact that any radix (either standard or mixed) base representation is unambiguous and complete. Every number can be represented in one and only one way because the sum of respective weights multiplied by the index is always the next weight minus one:

: <math> \sum_{i=0}^{n} (m_{i+1} - 1) \cdot M_i  = M_{n+1} - 1 </math>, where <math>M_i = \prod_{j=1}^{i} m_j,  m_j > 1,  M_0 = 1 </math>,
which can be easily proved with [[mathematical induction]].

== Primorial number system ==

Another proposal is the number system with successive prime numbers as radix, whose place values are [[primorial]] numbers, considered by [[Subbayya Sivasankaranarayana Pillai|S. S. Pillai]],<ref>S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159–167.</ref> [[Richard K. Guy]] {{OEIS|id=A049345}}, and other authors:<ref>
József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 4, pp. 384-386.</ref><ref>E. E. Kummer, Neuer elementarer Beweis des Satzes, dass die Anzahl aller Primzahlen eine unendliche ist, Monatsberichte der Königlichen Preussische Akademie des Wissenschaften zu Berlin 1878/9, pp. 777–778.</ref><ref>
Victor Ufnarovski and Bo Åhlander, [https://cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html How to Differentiate a Number], Journal of Integer Sequences, Vol. 6, 2003, #03.3.4.</ref>

{| class="wikitable"
|-
! {{rh}} | Radix      
|     19 ||    17 ||   13 || 11 ||   7 ||  5 ||  3 ||  2
|-
! {{rh}} | Place value
| (p<sub>7</sub>=17)# || (p<sub>6</sub>=13)# || (p<sub>5</sub>=11)# || (p<sub>4</sub>=7)# || (p<sub>3</sub>=5)# || (p<sub>2</sub>=3)# || (p<sub>1</sub>=2)# || (p<sub>0</sub>=1)#
|-
! {{rh}} | Place value in decimal    
| 510510 || 30030 || 2310 || 210 || 30 ||  6 ||  2 ||  1
|-
! {{rh}} | Highest digit allowed
|     18 ||    16 ||   12 ||  10 ||  6 ||  4 ||  2 ||  1
|}

: <math> \sum_{i=0}^{n} (p_{i+1} - 1) \cdot p_i\# = p_{n+1}\# - 1 </math> where <math>p_i\# = \prod_{j=1}^{i} p_j</math>, and ''p<sub>j</sub>'' = ''j''<sup>th</sup> prime, ''p''<sub>0</sub># = ''p''<sub>0</sub> = 1.

==References==
{{Reflist}}

* [[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89684-2}}. Pages 65&ndash;66, 208&ndash;209, and 290.
* [[Georg Cantor]]. ''Über einfache Zahlensysteme'', Zeitschrift für Math. und Physik '''14'''(1869), 121&ndash;128.

== External links ==
* [https://csharpcodewhisperer.blogspot.com/2015/10/mixed-radix-numeral-system-class-and.html Mixed Radix Calculator] — Mixed Radix Calculator in C#

[[Category:Non-standard positional numeral systems]]