Sixty-six

66 is the natural number following 65 and preceding 67.


Cardinal	sixty-six
Ordinal	66th (sixty-sixth)
Factorization	$2 \cdot 3 \cdot 11$
Divisors	2, 3, 6, 11, 22, 33
Roman numeral	LXVI
Binary	1000010
Hexadecimal	42

In mathematics

66 is a sphenic number, a triangular number, a hexagonal number, and a semi-meandric number.

In science

- The atomic number of dysprosium, a lanthanide In astronomy, : Messier object M66, a magnitude 10.0 galaxy in the constellation Leo : The New General Catalogue [http://www.ngcic.org/ object] NGC 66, a peculiar barred spiral galaxy in the constellation Cetus :The Saros [http://sunearth.gsfc.nasa.gov/eclipse/SEsaros/SEsaros1-175.html number] of the solar eclipse series which began on -756 March 12 and ended on 542 May 1. The duration of Saros series 66 was 1298.1 years, and it contained 73 solar eclipses. :The Saros [http://sunearth.gsfc.nasa.gov/eclipse/LEsaros/LEsaros1-175.html number] of the lunar eclipse series which began on -671 August 12 and ended on 826 January 27. The duration of Saros series 66 was 1496.5 years, and it contained 84 lunar eclipses.

In other fields

January 27 66 is also:
- The designation of the historic Route 66, dubbed the "Mother Road" by novelist John Steinbeck.
- The designation of US Interstate 66, a freeway that runs from Virginia to Washington, D.C..
- The number of the French department Pyrénées-Orientales.
- The international direct dialling (IDD) code for Thailand.
- The year AD 66, 66 BC, or 1966.
- The total number of books in the Protestant edition of the Bible (Old Testament and New Testament combined).
- The name of a German card game, translated from sechsundsechzig.
- Number of the Hockey legend Mario Lemieux
- In Star Wars, Order 66 is a prepared order to the clone troopers to kill the Jedi commanding them. Category:Integers ko:66 ja:66

Natural number

In mathematics, a natural number is either a positive integer (, , , , ...) or a non-negative integer (, , , , , ...). The former definition is generally used in number theory, while the latter is preferred in set theory. Natural numbers have two main purposes: they can be used for counting ("there are 3 apples on the table"), and they can be used for ordering ("this is the 3rd largest city in the country"). Properties of the natural numbers related to divisibility, such as the distribution of prime numbers, are studied in number theory. Problems concerning counting, such as Ramsey theory, are studied in combinatorics.

History of natural numbers and the status of zero

The natural numbers presumably had their origins in the words used to count things, beginning with the number one. The first major advance in abstraction was the use of numerals to represent numbers. This allowed systems to be developed for recording large numbers. For example, the Babylonians developed a powerful place-value system based essentially on the numerals for 1 and 10. The ancient Egyptians had a system of numerals with distinct hieroglyphs for 1, 10, and all the powers of 10 up to one million. A stone carving from Karnak, dating from around 1500 BC and now at the Louvre in Paris, depicts 276 as 2 hundreds, 7 tens, and 6 ones; and similarly for the number 4,622. A much later advance in abstraction was the development of the idea of zero as a number with its own numeral. A zero digit had been used in place-value notation as early as 700 BC by the Babylonians, but it was never used as a final element.¹ The Olmec and Maya civilization used zero as a separate number as early as 1st century BC, apparently developed independently, but this usage did not spread beyond Mesoamerica. The concept as used in modern times originated with the Indian mathematician Brahmagupta in 628 AD. Nevertheless, zero was used as a number by all medieval computists (calculators of Easter) beginning with Dionysius Exiguus in 525, but in general no Roman numeral was used to write it. Instead, the Latin word for "nothing," nullae, was employed. The first systematic study of numbers as abstractions (that is, as abstract entities) is usually credited to the Greek philosophers Pythagoras and Archimedes. However, independent studies also occurred at around the same time in India, China, and Mesoamerica. In the nineteenth century, a set-theoretical definition of natural numbers was developed. With this definition, it was more convenient to include zero (corresponding to the empty set) as a natural number. This convention is followed by set theorists, logicians, and computer scientists. Other mathematicians, primarily number theorists, often prefer to follow the older tradition and exclude zero from the natural numbers. The term whole number is used informally by some authors for an element of the set of integers, the set of non-negative integers, or the set of positive integers.

Notation

Mathematicians use N or

\mathbb

(an N in blackboard bold) to refer to the set of all natural numbers. This set is infinite but countable by definition. To be unambiguous about whether zero is included or not, sometimes an index "0" is added in the former case, and a superscript "
- " is added in the latter case: : N₀ = ; N^- = . (Sometimes, an index or superscript "+" is added to signify "positive". However, this is often used for "nonnegative" in other cases, as R₊ = [0,∞) and Z₊ = , at least in European literature. The notation "
- ", however, is quite standard for nonzero or rather invertible elements.) Less frequently, W or

\mathbb

is used for the set of "whole numbers", which are sometimes identified with the natural numbers as defined here, sometimes with the integers. Set theorists often denote the set of all natural numbers by ω. When this notation is used, zero is explicitly included as a natural number.

Formal definitions

Historically, the precise mathematical definition of the natural numbers developed with some difficulty. The Peano postulates state conditions that any successful definition must satisfy. Certain constructions show that, given set theory, models of the Peano postulates must exist.

Peano axioms

- There is a natural number 0.
- Every natural number a has a natural number successor, denoted by S(a).
- There is no natural number whose successor is 0.
- Distinct natural numbers have distinct successors: if a ≠ b, then S(a) ≠ S(b).
- If a property is possessed by 0 and also by the successor of every natural number which possesses it, then it is possessed by all natural numbers. (This postulate ensures that the proof technique of mathematical induction is valid.) It should be noted that the "0" in the above definition need not correspond to what we normally consider to be the number zero. "0" simply means some object that when combined with an appropriate successor function, satisfies the Peano axioms. There are many systems that satisfy these axioms, including the natural numbers (either starting from zero or one).

Constructions based on set theory

The standard construction

A standard construction in set theory is to define the natural numbers as follows: :We set 0 := :and define S(a) = a U for all a. :The set of natural numbers is then defined to be the intersection of all sets containing 0 which are closed under the successor function. :Assuming the axiom of infinity, this definition can be shown to satisfy the Peano axioms. :Each natural number is then equal to the set of natural numbers less than it, so that :
- 0 = :
- 1 = = :
- 2 = = = :
- 3 = = = :and so on. When you see a natural number used as a set, this is typically what is meant. Under this definition, there are exactly n elements (in the naïve sense) in the set n and n ≤ m (in the naïve sense) iff n is a subset of m. :Also, with this definition, different possible interpretations of notations like R^{n (n-tuples vs. mappings of n into R) coincide.

Other constructions

Although the standard construction is useful, it is not the only possible construction. For example:
:one could define 0 =
:and S(a) = ,
:producing
:: 0 =
:: 1 = =
:: 2 = = , etc.
Or we could even define 0 =
:and S(a) = a U
:producing
:: 0 =
:: 1 = =
:: 2 = , etc.

For the rest of this article, we follow the standard construction described above.

Properties

One can recursively define an addition on the natural numbers by setting a + 0 = a and a + S(b) = S(a + b) for all a, b. This turns the natural numbers (N, +) into a commutative monoid with identity element 0, the so-called free monoid with one generator. This monoid satisfies the cancellation property and can therefore be embedded in a group. The smallest group containing the natural numbers is the integers.

If we define S(0) := 1, then S(b) = S(b + 0) = b + S(0) = b + 1; i.e. the successor of b is simply b + 1.

Analogously, given that addition has been defined, a multiplication × can be defined via a × 0 = 0 and a × S(b) = (a × b) + a. This turns (N, ×) into a commutative monoid with identity element 1; a generator set for this monoid is the set of prime numbers. Addition and multiplication are compatible, which is expressed in the distribution law:
a × (b + c) = (a × b) + (a × c). These properties of addition and multiplication make the natural numbers an instance of a commutative semiring. Semirings are an algebraic generalization of the natural numbers where multiplication is not necessarily commutative.

If we interpret the natural numbers as "excluding 0", and "starting at 1", the definitions of + and × are as above, except that a + 1 = S(a) and a × 1 = a.

For the remainder of the article, we write ab to indicate the product a × b, and we also assume the standard order of operations.

Furthermore, one defines a total order on the natural numbers by writing a ≤ b if and only if there exists another natural number c with a + c = b. This order is compatible with the arithmetical operations in the following sense: if a, b and c are natural numbers and a ≤ b, then a + c ≤ b + c and ac ≤ bc. An important property of the natural numbers is that they are well-ordered: every non-empty set of natural numbers has a least element.

While it is in general not possible to divide one natural number by another and get a natural number as result, the procedure of division with remainder is available as a substitute: for any two natural numbers a and b with b ≠ 0 we can find natural numbers q and r such that

:a = bq + r and r < b

The number q is called the quotient and r is called the remainder of division of a by b. The numbers q and r are uniquely determined by a and b. This, the Division algorithm, is key to several other properties (divisibility), algorithms (such as the Euclidean algorithm), and ideas in number theory.

Generalizations

Two generalizations of natural numbers arise from the two uses: ordinal numbers are used to describe the position of an element in a ordered sequence and cardinal numbers are used to specify the size of a given set.

For finite sequences or finite sets, both of these properties are embodied in the natural numbers.

Other generalizations are discussed in the article on numbers.

Footnote

¹ "... a tablet found at Kish ... thought to date from around 700 BC, uses three hooks to denote an empty place in the positional notation. Other tablets dated from around the same time use a single hook for an empty place." [http://www-history.mcs.st-and.ac.uk/history/HistTopics/Zero.html]

Category:Elementary mathematics
Category:Integers
Category:Number theory
Category:Numbers
Category:Set theory

ko:자연수

ja:自然数

th:จำนวนธรรมชาติ

65 (number)
65 is the natural number following 64 and preceding 66.

Cardinal sixty-five
Ordinal 65th (sixty-fifth)
Factorization $5 \cdot 13$
Roman numeral LXV
Binary 1000001
Hexadecimal 41

In mathematics
Sixty-five is an octagonal number. It is also a Cullen number. Given 65, the Mertens function returns 0.

This number is the magic constant of 5 by 5 magic square:

$\begin
17 & 24 & 1 & 8 & 15 \\
23 & 5 & 7 & 14 & 16 \\
4 & 6 & 13 & 20 & 22 \\
10 & 12 & 19 & 21 & 3 \\
11 & 18 & 25 & 2 & 9
\end.$

This number is also the magic constant of n-Queens Problem for n = 5.

65 can be expressed as a sum of two squares in two ways, 65 = 8² + 1² = 7² + 4².

It appears in the Padovan sequence, preceded by the terms 28, 37, 49 (it is the sum of the first two of these).

In science

- The atomic number of terbium, a lanthanide

In astronomy,

: Messier object M65, a magnitude 10.5 galaxy in the constellation Leo

: The New General Catalogue [http://www.ngcic.org/ object] NGC 65, a spiral galaxy in the constellation Cetus

:The Saros [http://sunearth.gsfc.nasa.gov/eclipse/SEsaros/SEsaros1-175.html number] of the solar eclipse series which began on -749 April 24 and ended on 513 May 20. The duration of Saros series 65 was 1262.1 years, and it contained 71 solar eclipses.

:The Saros [http://sunearth.gsfc.nasa.gov/eclipse/LEsaros/LEsaros1-175.html number] of the lunar eclipse series which began on -736 August 11 and ended on 797 February 16. The duration of Saros series 65 was 1532.5 years, and it contained 86 lunar eclipses.

In other fields
Sixty-five is also:

- A common speed limit, in miles per hour, for freeways in many U.S. states.

- The designation of Interstate 65, a freeway that runs from Alabama to Indiana.

- The code for international direct dial phone calls to Singapore.

- The standard age for retirement in the UK, Germany and other countries.

- The registry of the U.S. Navy's nuclear aircraft carrier USS Enterprise (CVN-65).

- The year AD 65, 65 BC, or 1965.
Category:Integers

ko:65

ja:65

67 (number)
67 is the natural number following 66 and preceding 68.

Cardinal sixty-seven
Ordinal 67th (sixty-seventh)
Factorization prime
Roman numeral LXVII
Binary 1000011
Hexadecimal 43

In mathematics
Sixty-seven is the 19th prime number (the next is 71), an irregular prime, a lucky prime, and the sum of five consecutive primes (7 + 11 + 13 + 17 + 19).
It is a discriminant to the Heegner number -67.

In astronomy

- Messier object M67, a magnitude 7.5 open cluster in the constellation Cancer

- The New General Catalogue object NGC 67, an elliptical galaxy in the constellation Andromeda

- The Saros number of the solar eclipse series which began on -727 February 20 and ended on 571 April 10. The duration of Saros series 67 was 1298.1 years, and it contained 73 solar eclipses. The Saros number of the lunar eclipse series which began on -660 July 1 and ended on 656 September 9. The duration of Saros series 67 was 1316.2 years, and it contained 74 lunar eclipses.

Other fields
Sixty-seven is also:

- The atomic number of holmium, a lanthanide

- The registry of the U.S. Navy's aircraft carrier USS John F. Kennedy (CV-67), named after U.S. President John F. Kennedy.

- The number of the European route E67, the Via Baltica from Prague to Helsinki.

- The number of the French department Bas-Rhin.

- Part of the name of the Ottawa 67's, founded in 1967.

- The year AD 67, 67 BC, or 1967.

Category:Integers

ko:67

ja:67

Ordinal number
Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc., whereas a cardinal number says "how many there are": one, two, three, four, etc. (See How to name numbers.)

An ordinal scale defines a total preorder of objects; the scale values themselves have a total order; names may be used like "bad", "medium", "good"; if numbers are used they are only relevant up to strictly monotonically increasing transformations (order isomorphism). See also level of measurement.
----
In mathematics, ordinal numbers are an extension of the natural numbers to accommodate infinite sequences, introduced by Georg Cantor in 1897. It is this generalization which will be explained below.

Introduction

A natural number can be used for two purposes: to describe the size of a set, or to describe the position of an element in a sequence. While in the finite world these two concepts coincide, when dealing with infinite sets one has to distinguish between the two. The notion of size leads to cardinal numbers, which were also discovered by Cantor, while the position is generalized by the ordinal numbers described here.

In set theory, the natural numbers are commonly constructed as sets, such that each natural number is the set of all smaller natural numbers:

:0 = (empty set)
:1 = =
:2 = =
:3 = =
:4 = =

etc.

Viewed this way, every natural number is a well-ordered set: the set 4, for instance, has the elements 0, 1, 2, 3 which are of course ordered as 0 < 1 < 2 < 3. A natural number is smaller than another if and only if it is an element of the other.

We don't want to distinguish between two well-ordered sets if they only differ in the "notation for their elements", or more formally: if we can pair off the elements of the first set with the elements of the second set such that if one element is smaller than another in the first set, then the partner of the first element is smaller than the partner of the second element in the second set, and vice versa. Such a one-to-one correspondence is called an order isomorphism (or a strictly increasing function) and the two well-ordered sets are said to be order-isomorphic.

Under this convention, one can show that every finite well-ordered set is order-isomorphic to one (and only one) natural number. This provides the motivation for the generalization to infinite numbers.

Modern definition and first properties

We want to construct ordinal numbers as special well-ordered sets in such a way that every well-ordered set is order-isomorphic to one and only one ordinal number.
The following definition improves on Cantor's approach and was first given by John von Neumann:

:A set S is an ordinal if and only if S is totally ordered with respect to set containment and every element of S is also a subset of S.

(Here, "set containment" is another name for the subset relationship.)
Such a set S is automatically well-ordered with respect to set containment. This relies on the axiom of well foundation: every nonempty set S has an element a which is disjoint from S.

Note that the natural numbers are ordinals by this definition. For instance,
2 is an element of 4 = , and 2 is equal to and so it is a subset of .

It can be shown by transfinite induction that every well-ordered set is order-isomorphic to exactly one of these ordinals.

Furthermore, the elements of every ordinal are ordinals themselves. Whenever you have two ordinals S and T, S is an element of T if and only if S is a proper subset of T, and moreover, either S is an element of T, or T is an element of S, or they are equal. So every set of ordinals is totally ordered. And in fact, much more is true: Every set of ordinals is well-ordered. This important result generalizes the fact that every set of natural numbers is well-ordered and it allows us to use transfinite induction liberally with ordinals.

Another consequence is that every ordinal S is a set having as elements precisely the ordinals smaller than S. This statement completely determines the set-theoretic structure of every ordinal in terms of other ordinals. It's used to prove many other useful results about ordinals. One example of these is an important characterization of the order relation between ordinals: every set of ordinals has a supremum, the ordinal obtained by taking the union of all the ordinals in the set.
Another example is the fact that the collection of all ordinals is not a set. Indeed, since every ordinal contains only other ordinals, it follows that every member of the collection of all ordinals is also its subset. Thus, if that collection were a set, it would have to be an ordinal itself by definition; then it would be its own member, which contradicts the axiom of regularity. (See also the Burali-Forti paradox).

An ordinal is finite if and only if the opposite order is also well-ordered, which is the case if and only if each of its subsets has a greatest element.

Other definitions

There are other modern formulations of the definition of ordinal. Each of these is essentially equivalent to the definition given above. One of these definitions is the following. A class S is transitive if, whenever x is an element of y and y is an element of S, then x is an element of S. An ordinal is then defined to be a class S which is transitive, and such that every member of S is also transitive.

Arithmetic of ordinals

To define the sum S + T of two ordinal numbers S and T, one proceeds as follows: first the elements of T are relabeled so that S and T become disjoint, then the well-ordered set S is written "to the left" of the well-ordered set T, meaning one defines an order on S∪T in which every element of S is smaller than every element of T. The sets S and T themselves keep the ordering they already have. This way, a new well-ordered set is formed, and this well-ordered set is order-isomorphic to a unique ordinal, which is called S + T. This addition is associative and generalizes the addition of natural numbers.

The first transfinite ordinal is ω, the set of all natural numbers.
Let's try to visualize the ordinal ω+ω: two copies
of the natural numbers ordered in the normal fashion and the second copy completely to the right of the first. If we write the second copy as then ω+ω looks like
:0 < 1 < 2 < 3 < ... < 0' < 1' < 2' < ...
This is different from ω because in ω only 0 does not have a direct predecessor while in ω+ω the two elements 0 and 0' don't have direct predecessors.
Here's 3 + ω:
:0 < 1 < 2 < 0' < 1' < 2' < ...
and after relabeling, this just looks like ω itself: we have 3 + ω = ω. But ω + 3 is not equal to ω since the former has a largest element and the latter doesn't. So our addition is not commutative.

You should now be able to see that (ω + 4) + ω = ω + (4 + ω) = ω + ω for example.

To multiply the two ordinals S and T you write down the well-ordered set T and replace each of its elements with a different copy of the well-ordered set S. This results in a well-ordered set, which defines a unique ordinal; we call it ST. Again, this operation is associative and generalizes the multiplication of natural numbers.

Here's ω2:
:0₀ < 1₀ < 2₀ < 3₀ < ... < 0₁ < 1₁ < 2₁ < 3₁ < ...
and we see: ω2 = ω + ω. But 2ω looks like this:
:0₀ < 1₀ < 0₁ < 1₁ < 0₂ < 1₂ < 0₃ < 1₃ < ...
and after relabeling, this looks just like ω and so we get 2ω = ω.
Multiplication of ordinals is not commutative.

Distributivity partially holds for ordinal arithmetic: R(S+T) = RS + RT. However, the other distributive law (T+U)R = TR + UR is not generally true: (1+1)ω is equal to 2ω = ω while 1ω + 1ω equals ω+ω. Therefore, the ordinal numbers do not form a ring.

A ring-like structure such as this, with only the left distributive law, is called a (left) nearring: however, ordinals are not quite a nearring either because they do not admit additive inverses (negation). Since a ring without negation is sometimes referred to as a rig, the ordinals may be said to form a left nearrig: a nearring without negation.

One can now go on to define exponentiation of ordinal numbers.
For finite exponents, this should be obvious, for instance $\omega^2 = \omega \omega$ using the operation of ordinal multiplication. But instead this can be visualized as a set of ordered pairs of natural numbers, ordered by a variant of lexicographical order which puts the least significant position first:

:(0,0) < (1,0) < (2,0) < (3,0) < ... < (0,1) < (1,1) < (2,1) < (3,1) < ... < (0,2) < (1,2) < (2,2) < ...

And similarly for any finite n, $\omega^n$ can be visualized as the set of n-tuples of natural numbers.

Then for $\omega^\omega$ , we might try to visualize the set of infinite sequences of natural numbers. However, if we try to use any variant of lexicographical order on this set, we find it is not well-ordered. We must add the restriction that only a finite number of elements of the sequence are different from zero. Now our ordering works, and it looks like the ordering of natural numbers written in decimal notation, except with digit positions reversed, and with arbitrary natural numbers instead of just the digits 0-9:

:(0,0,0,...) < (1,0,0,0,...) < (2,0,0,0,...) < ... <
:(0,1,0,0,0,...) < (1,1,0,0,0,...) < (2,1,0,0,0,...) < ... <
:(0,2,0,0,0,...) < (1,2,0,0,0,...) < (2,2,0,0,0,...)
:: < ... <
:(0,0,1,0,0,0,...) < (1,0,1,0,0,0,...) < (2,0,1,0,0,0,...)
:: < ...

So in general, raise an ordinal S to the power of an ordinal T, we write down copies of the well-ordered set T, and then replace each element with some element of S, with the restriction that all but a finite number of elements of the sequence must be the first element of S. We find $1^\omega = 1$ , $2^\omega = \omega$ , $2^ = \omega 2 = \omega + \omega$ . We also have the expected exponentiation laws $(S^T)^U = S^$ and $S^ = S^T S^U$ .

Cantor normal form

Ordinal numbers present an extremely rich arithmetic. Every ordinal number $\alpha>0$ can be uniquely written as $\omega^ c_1 + \omega^c_2 + \ldots + \omega^c_k$ , where $k, c_1, c_2, \ldots, c_k$ are positive integers, and $\beta_1 > \beta_2 > \ldots > \beta_k$ are ordinal numbers (possibly $\beta_k=0$ ). This decomposition of $\alpha$ is called the Cantor normal form of $\alpha$ , and can be considered the positional base-ω numeral system. The highest exponent $\beta_1$ is called the degree of $\alpha$ , and satisfies $\beta_1\le\alpha$ . In case $\beta_1<\alpha$ , we have a finite representation of α with integers only (attached to a skeleton of ωs, additions, multiplications, and exponentiations).

There are ordinal numbers which cannot be reached from ω with a finite number of the arithmetical operations addition, multiplication and exponentiation. The smallest such is denoted by ε₀. This ordinal is very important in many induction proofs, because for many purposes, transfinite induction is only required up to ε₀. Note that $\epsilon_0 = \omega^$ , so that $\epsilon_0 = \omega^$ .

$\epsilon_0$ is still countable. There exist uncountable ordinals. The smallest uncountable ordinal is equal to the set of all countable ordinals, and is usually denoted by ω₁.

Topology and limit ordinals

The ordinals also carry an interesting order topology by virtue of being totally ordered. In this topology, the sequence 0, 1, 2, 3, 4, ... has limit ω and the sequence ω, ω^ω, ω^(ω^ω), ... has limit ε₀. Ordinals which don't have an immediate predecessor can always be written as a limit of a net of other ordinals (but not necessarily as the limit of a sequence, i.e. as a limit of countably many smaller ordinals) and are called limit ordinals; the other ordinals are the successor ordinals.

The topological spaces ω₁ and its successor ω₁+1 are frequently used as text-book examples of non-countable topological spaces.
For example, in the topological space ω₁+1, the element ω₁ is in the closure of the subset ω₁ even though no sequence of elements in ω₁ has the element ω₁ as its limit. The space ω₁ is first-countable, but not second-countable, and ω₁+1 has neither of these two properties.

Some special ordinals can be used to measure the size or cardinality of sets. These are the cardinal numbers.

See also

- successor ordinal

- limit ordinal

- cardinal number

- Serial number

- Nominal number

References

- Conway, J. H. and Guy, R. K. "Cantor's Ordinal Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 266-267 and 274, 1996.

- Sierpinski, W. (1965). Cardinal and Ordinal Numbers (2nd ed.). Warszawa: Pantswowe Wydawnictwo Naukowe. Also defines ordinal operations in terms of the Cantor Normal Form.

Category:Ordinal numbers
Category:Numbers

ko:순서수

ja:順序数

simple:Ordinal number

Factorization
:This article is about the mathematical concept. For the financial term see Factoring (trade).

In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. For example, the number 15 factors into primes as 3 × 5; and the polynomial x² − 4 factors as (x − 2)(x + 2). In all cases, we obtain a product of simpler things.

The aim of factoring is usually to reduce something to "basic building blocks", such as numbers to prime numbers, or polynomials to irreducible polynomials. Factoring integers is covered by the fundamental theorem of arithmetic and factoring polynomials by the fundamental theorem of algebra.

Integer factorization for large integers appears to be a difficult problem. There is no known method to carry it out quickly. Its complexity is the basis of the assumed security of some public key cryptography algorithms, such as RSA.

A matrix can also be factorized into a product of matrices of special types, for an application in which that form is convenient. One major example of this uses an orthogonal or unitary matrix, and a triangular matrix. There are different types: QR decomposition, LQ, QL, RQ, RZ.

Another example is the factorization of a function as the composition of other functions having certain properties; for example, every function can be viewed as the composition of a surjective function with an injective function.

Factoring in mathematical logic

In mathematical logic and automated theorem proving, factoring is the technique of deriving a single, more specific atom from a disjunction of two more general unifiable atoms. For example, from ∀ X, Y : P(X, a) or P(b, Y) we can derive P(b, a).

See also

- Prime factorization algorithm

- Program synthesis

- Unique factorization

External links

- [http://library.thinkquest.org/20991/alg/factoring.html?tqskip1=1 A page about factorization, Algebra, Factoring]

- [http://wims.unice.fr/wims/wims.cgi?module=tool/algebra/factor.en WIMS Factoris] is an online factorization tool.

- [http://www.factoring-polynomials.com Polynomial Factoring] is a comprehensive tutorial resource on basic factoring of polynomials.
Category:ArithmeticCategory:algebra

Divisor
:For divisors in algebraic geometry, see divisor (algebraic geometry).

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder.

Explanation

For example, 7 is a divisor of 42 because 42/7 = 6. We also say 42 is divisible by 7 or 42 is a multiple of 7 or 7 divides 42 and we usually write 7 | 42. For example, the positive divisors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.

In general, we say m|n (read: m divides n) for any integers m and n iff there exists an integer k such that n = km. Thus, divisors can be negative as well as positive. 1 and -1 are divisors of every integer, every integer is a divisor of itself, and every integer is a divisor of 0, while 0 is a divisor only of 0 (see also division by zero). Numbers divisible by 2 are called even and those that are not are called odd.

A divisor of n that is not 1, -1, n or -n is known as a non-trivial divisor; numbers with non-trivial divisors are known as composite numbers, while prime numbers have no non-trivial divisors.

The name comes from the arithmetic operation of division: if a/b=c then a is the dividend, b the divisor, and c the quotient.

There are some rules which allow to recognize small divisors of a number from the number's decimal digits.

Further notions and facts

Some elementary rules:

- If a | b and a | c, then a | (b + c), in fact, a | (mb + nc) for all integers m, n.

- If a | b and b | c, then a | c. (transitive relation)

- If a | b and b | a, then a = b or a = -b.

The following property is important:

- If a | bc, and gcd(a,b) = 1, then a | c. (Euclid's lemma)

A positive divisor of n which is different from n is called a proper divisor (or aliquot part) of n. (A number which does not evenly divide n, but leaves a remainder, is called an aliquant part of n.)

An integer n > 1 whose only proper divisor is 1 is called a prime number.

Any positive divisor of n is a product of prime divisors of n raised to some power. This is a consequence of the Fundamental theorem of arithmetic.

If a number equals the sum of its proper divisors, it is said to be a perfect number. Numbers less than that sum are said to be deficient, while numbers greater than that sum are said to be abundant.

The total number of positive divisors of n is a multiplicative function d(n) (e.g. d(42) = 8 = 2×2×2 = d(2)×d(3)×d(7)). The sum of the positive divisors of n is another multiplicative function σ(n) (e.g. σ(42) = 96 = 3×4×8 = σ(2)×σ(3)×σ(7)).

If the prime factorization of n is given by
: $n = p_1^ \, p_2^ \, ... \, p_n^$
then the number of positive divisors of n is
: $d(n) = (\nu_1 + 1) (\nu_2 + 1) ... (\nu_n + 1),$
and each of the divisors has the form
: $p_1^ \, p_2^ \, ... \, p_n^$
where
: $\forall i : 0 \le \mu_i \le \nu_i.$

Divisibility of numbers

The relation | of divisibility turns the set N of non-negative integers into a partially ordered set, in fact into a complete distributive lattice. The largest element of this lattice is 0 and the smallest one is 1. The meet operation ^ is given by the greatest common divisor and the join operation v by the least common multiple. This lattice is isomorphic to the dual of the lattice of subgroups of the infinite cyclic group Z.

If an integer n is written in base b, and d is an integer with b ≡ 1 (mod d), then n is divisible by d if and only if the sum of its digits is divisible by d. The rules for d=3 and d=9 given above are special cases of this result (b=10).

We can generalize this method even further to find how to check divisibility of any integer in any base by any other (smaller integer). Let us say that we want to determine if d | a in base b. Then we first find a pair of integers (n, k) that solves the congruence bⁿ ≡ k (mod d). Now rather than summing the digits, we take a (which has m digits) and multiply the first m-n digits by k and add the product to the last (or more precisely, smallest) k digits and repeat if necessary. If the result is a multiple of d then the original number is divisible by d. A few examples will help demonstrate this. Since 10³ ≡ 1 (mod 37) then the number 1523836638 gives 1+523+836+638 = 1998 which gives 999 which we know is divisible by 37 due to the above congruence. Again, 10² ≡ 2 (mod 7) so 43106 gives 431×2 + 06 = 868 which gives 8×2+68 = 84 which is easily noted as being a multiple of 7. Note that there is no unique triple (n, k, d) since for example 10 ≡ 3 (mod 7) so we could also have done 4310×3 + 6 = 12936 and 1293×3 + 6 = 3885 and 388×3 + 5 = 1169 and 116×3 + 9 = 357 and 35×3 + 7 = 112 and 11×3 + 2 = 35 and 3×3 + 5 = 14 and 1×3 + 4 = 7. Clearly this is not always efficient but note that each number in this series, 43106, 12936, 3885, 1169, 357, 112, 35, 14, 7 is a multiple of 7 and many series could contain trivially identifiable multiples. This method is not necessarily useful for some numbers (for example 10⁴ ≡ 4 (mod 17) is the first n where k < 10) but lends itself to fast calculations in other cases where n and k are relatively small.

Generalization

One can talk about the concept of divisibility in any integral domain. Please see that article for the definitions in that setting.

See also

- Table of prime factors — A table of prime factors for 1-1000

- Table of divisors — A table of prime and non-prime divisors for 1-1000

- Euler's totient function

- Divisibility rule

External links

- [http://www.farfarfar.com/math/calculators/factoring/ Factoring Calculator] -- Factoring calculator that displays the prime factors and the prime and non-prime divisors of a given number.

- [http://users.adelphia.net/~j.mccranie/ webpage that has program for factoring up to 18 digit numbers]

Category:Elementary number theory
Category:Elementary arithmetic

ko:약수

ja:約数

Roman numeral
The system of Roman numerals is a numeral system originating in ancient Rome, and was adapted from Etruscan numerals. The system used in antiquity was slightly modified in the Middle Ages to produce the system we use today.
It is based on certain letters which are given values as numerals:
:I or i for one,
:V or v for five,
:X or x for ten,
:L or l for fifty,
:C or c for one hundred (centum),
:D or d for five hundred,
:M or m for one thousand (mille).

For larger numbers (five thousand and above), a bar is placed above a base numeral to indicate multiplication by 1000.

: for five thousand

: for ten thousand

: for fifty thousand

: for one hundred thousand

: for five hundred thousand

: for one million

Roman numerals are commonly used today in numbered lists (in outline format), clockfaces, pages preceding the main body of a book, chord triads in music analysis, the numbering of movie sequels, and the numbering of some sport events, like the Super Bowls or Olympic Games.

For arithmetics involving Roman numerals, see Roman arithmetic and Roman abacus.

Origins

Although the Roman numerals are now written with letters of the Roman alphabet, they were originally separate symbols. The Etruscans, for example, used I Λ X ⋔ 8 ⊕ for I V X L C M.

They appear to derive from notches on tally sticks, such as those used by Italian and Dalmatian shepherds into the 19^th century. Thus, the I descends from a notch scored across the stick. Every fifth notch was double cut (⋀, ⋁, ⋋, ⋌, etc.), and every tenth was cross cut (X), much like European tally marks today. This produced a positional system: Eight on a counting stick was eight tallies, IIIIΛIII, but this could be written ΛIII (or VIII), as the Λ implies the four prior notches. Likewise, number four on the stick was the I-notch that could be felt just before the cut of the V, so it could be written as either IIII or IV. Thus the system was neither additive nor subtractive in its conception, but ordinal. When the tallies were later transfered to writing, the marks were easily identified with the existing Roman letters I, V, X.

(A folk etymology has it that the V represented a hand, and that the X was made by placing two Vs on top of each other, one inverted.)

The tenth V or X along the stick received an extra stroke. Thus 50 was written variously as N, И, K, Ψ, ⋔, etc., but perhaps most often as a chicken-track shape like a superimposed V and I. This had flattened to ⊥ (an inverted T) by the time of Augustus, and soon thereafter became identified with the graphically similar letter L. Likewise, 100 was variously Ж, ⋉, ⋈, H, or as any of the symbols for 50 above plus an extra stroke. The form Ж (that is, a superimposed X and I) came to predominate, was written variously as >I< or ƆIC, was then shortened to Ɔ or C, with C finally winning out because, as a letter, it stood for centum (Latin for 'hundred').

The hundredth V or X was marked with a box or circle. Thus 500 was like a Ɔ superposed on a ⋌ or ⊢ (that is, like a Þ with a cross bar), becoming a struck-through D or a Ð by the time of Augustus, under the graphic influence of the letter D. It was later identified as the letter D. Meanwhile, 1000 was a circled X: Ⓧ, ⊗, ⊕, and by Augustinian times was partially identified with the Greek letter Φ. It then evolved along several independent routes. Some variants, such as Ψ and CD (more accurately a reversed D adjacent to a regular D), were historical dead ends (although folk etymology later identified D for 500 as half of Φ for 1000 because of the CD variant), while two variants of ↀ survive to this day. One, CIƆ, lead to the convention of using parentheses to indicate multiplication by 1000 (later extended to double parentheses as in ↁ, ↂ, etc.); in the other, ↀ became ∞ and ⋈, eventually changing to M under the influence of the word mille ('thousand').

Zero
In general, the number zero did not have its own Roman numeral, but the concept of zero as a number was well known by all medieval computists (responsible for calculating the date of Easter). They included zero (via the Latin word nulla meaning nothing) as one of nineteen epacts, or the age of the moon on March 22. The first three epacts were nullae, xi, and xxii (written in minuscule or lower case). The first known computist to use zero was Dionysius Exiguus in 525, but the concept of zero was no doubt well known earlier. Only one instance of a Roman numeral for zero is known. About 725, Bede or one of his colleagues used the letter N, the initial of nullae, in a table of epacts, all written in Roman numerals.

A notation for the value zero is quite distinct from the role of the digit zero in a positional notation system. The lack of a zero digit prevented Roman numerals from developing into a positional notation, and led to their gradual replacement by Arabic numerals in the early second millennium.

IIII or IV?
The notation of Roman numerals has varied through the centuries. Originally, it was common to use IIII to represent "four", because IV represented the god Jove (and later YHWH). The subtractive notation (which uses IV instead of IIII) has become universally used only in modern times. For example, Forme of Cury, a manuscript from 1390, uses IX for "nine", but IIII for "four". Another document in the same manuscript, from 1381, uses IV and IX. A third document in the same manuscript uses both IIII and IV, and IX. Constructions such as IIX for "eight" have also been discovered. In many cases, there seems to have been a certain reluctance in the use of the less intuitive subtractive notation. Its use increased the complexity of performing Roman arithmetic, without conveying the benefits of a full positional notation system.

Calendars and clocks
Clock faces that are labelled using Roman numerals conventionally show IIII for 4 o'clock and IX for 9 o'clock, using the subtractive principle in one case and not in the other. There are several suggested explanations for this, several of which may be true:

- The four-character form IIII creates a visual symmetry with the VIII on the other side, which IV would not.

- The number of symbols on the clock totals twenty I's, four V's, and four X's, so clock makers need only a single mold with five I's, a V, and an X in order to make the correct number of numerals for the clocks, cast four times for each clock:
:: V IIII IX
:: VI II IIX
:: VII III X
:: VIII I IX
:IIX and one of the IX's can be rearranged or inverted to form XI and XII. The alternative uses seventeen I's, five V's, and four X's, possibly requiring the clock maker to have several different molds.

- IIII was the preferred way for the ancient Romans to write 4, since they to a large extent avoided subtraction.

- It has been suggested that since IV is the first two letters of IVPITER, the main god of the Romans, it was not appropriate to use.

- The I symbol would be the only symbol in the first 4 hours of the clock, the V symbol would only appear in the next 4 hours, and the X symbol only in the last 4 hours. This would add to the clock's radial symmetry.

- IV is difficult to read upside down and on an angle, particularly at that location on the clock.

- Louis XIV, king of France, preferred IIII over IV, ordered his clockmakers to produce clocks with IIII and not IV, and thus it has remained.

XCIX or IC?
Rules regarding Roman numerals often state that a symbol representing 10^x may not precede any symbol larger than 10^x+1. For example, C cannot be preceded by I or V, only by X (or, of course, by a symbol representing a value larger than C). Thus, one should represent the number "ninety-nine" as XCIX, not as the "shortcut" IC. However, these rules are not universally followed.

This 'problem' manifested in questions as to why 1999 was not written simply IMM or MIM.

Year in Roman numerals
In seventeenth century Europe, using Roman numerals for the year of publication for books was standard; there were many other places it was used as well. Publishers attempted to make the number easier to read by those more accustomed to Arabic positional numerals. On British title pages, there were often spaces between the groups of digits: M DCC LXI is one example. This may have come from the French, who separated the groups of digits with periods, as: M.DCC.LXI. or M. DCC. LXI. Notice the period at the end of the sequence; many foreign countries did this for Roman numerals in general, but not necessarily Britain. (Periods were also common on each side of numerals in running text, as in "commonet .iij. viros illos".)

These practices faded from general use before the start of the twentieth century, though the cornerstones of major buildings still occasionally use them. Roman numerals are today still used on building faces for dates: 2005 can be represented as MMV.

The film industry has used them perhaps since its inception to denote the year a film was made, so that it could be redistributed later, either locally or to a foreign country, without making it immediately clear to viewers what the actual date was. This became more useful when films were broadcast on television to partially conceal the age of films. From this came the policy of the broadcasting industry, including the BBC, to use them to denote the year in which a television program was made (the Australian Broadcasting Corporation has largely stopped this practice but still occasionally lapses).

Other modern usage by English-speaking peoples
Roman numerals remained in common use until about the 14th century, when they were replaced by Arabic numerals (thought to have been introduced to Europe from al-Andalus, by way of Arab traders and arithmetic treatises, around the 11th century). The use of Roman numerals today is mostly restricted to ordinal numbers, such as volumes or chapters in a book or the numbers identifying monarchs or popes (e.g. Elizabeth II, Benedict XVI, etc.).

Sometimes the numerals are written using lower-case letters (thus: i, ii, iii, iv, etc.), particularly if numbering paragraphs or sections within chapters, or for the pagination of the front matter of a book.

Undergraduate degrees at British universities are generally graded using I, IIi, IIii, III for first, upper second (often pronounced "two one"), lower second (often pronounced "two two") and third class respectively.

Modern English usage also employs Roman numerals in many books (especially anthologies), movies (e.g., Star Wars), sporting events (e.g., the Super Bowl), and historic events (e.g., World War I, World War II ). The common unifying theme seems to be stories or events that are episodic or annual in nature, with the use of classical numbering suggesting importance or timelessness.

In chemistry, Roman numerals were used to denote the group in the periodic table of the elements. But there was not international agreement as to whether the group of metals which dissolve in water should be called Group IA or IB, for example, so although references may use them, the international norm has recently switched to Arabic numerals.

In music theory a scale degrees or diatonic functions are often identified by Roman numerals (as in chord symbols) as follows:

Modern non-English speaking usage
The above uses are customary for English-speaking countries. Although many of them are also maintained in other countries, those countries have additional uses for Roman numerals which are unknown in English-speaking regions.

The French, the Portuguese, and the Spanish use capital Roman numerals to denote centuries. For example, 'XVIII' refers to the eighteenth century, so as to avoid confusion between the '18^th century' and the '1800s'. (The Italians take the opposite approach, basing names of centuries on the digits of the years; quattrocento for example is the Italian name for the fifteenth century.) Some scholars in English-speaking countries have adopted the French method, among them Lyon Sprague de Camp.

In Germany, Poland, and Russia, mixed Roman numerals are used to record dates. Just as an old clock recorded the hour by Roman numerals while the minutes were measured in Arabic numerals, the month is written in Roman numerals while the day is in Arabic numerals: 14-VI-1789 is June the fourteenth, 1789. This is how dates are inscribed on the walls of the Kremlin, for example. This method has the advantage that days and months are not confused in rapid note-taking, and that any range of days or months can be expressed without confusion. For instance, V-VIII is May to August, while 1-V-31-VIII is May first to August thirty-first.

In Eastern Europe, especially the Baltic nations, Roman numerals are used to represent the days of the week in hours-of-operation signs displayed in windows or on doors of businesses. Monday is represented by I, which is the initial day of the week. Sunday is represented by VII, which is the final day of the week. The hours of operation signs are tables composed of two columns where the left column is the day of the week in Roman numerals and the right column is a range of hours of operation from starting time to closing time. The following example hours-of-operation table would be for a business whose hours of operation are 9:30AM to 5:30PM on Mondays, Wednesdays, and Thursdays; 9:30AM to 7:00PM on Tuesdays and Fridays; and 9:30AM to 1:00PM on Saturdays; and which is closed on Sundays.

Since the French use capital Roman numerals to refer to the quarters of the year ('III' is the third quarter), and this has become the norm in some European standards organisation, the mixed Roman-Arabic method of recording the date has switched to lowercase Roman numerals in many circles, as '4-viii-1961'. (ISO has since specified that dates should be given in all Arabic numerals, in ISO 8601 formats.)

In Romania, Roman numerals are used for floor numbering.

Alternate forms
In the Middle Ages, Latin writers used a horizontal line above a particular numeral to represent one thousand times that numeral, and additional vertical lines on both sides of the numeral to denote one hundred times the number, as in these examples:

: for one thousand
: for five thousand
: || for one hundred thousand
: || for five hundred thousand

The same overline was also used with a different meaning, to clarify that the characters were numerals. Sometimes both underline and overline were used, e. g. , and in certain font-faces, particularly Times New Roman, the capital letters when used without spaces simulates the appearance of the under/over bar, e.g. MCMLXVII, which is often exagerated when written by hand.

Sometimes 500, usually D, was written as I followed by an apostrophus, resembling a backwards C (Ɔ), while 1,000, usually M, was written as CIƆ. This is believed to be a system of encasing numbers to denote thousands (imagine the Cs as parentheses). This system has its origins from Etruscan numeral usage. The D and M symbols to represent 500 and 1,000 were most likely derived from IƆ and CIƆ, respectively.

An extra Ɔ denoted 500, and multiple extra Ɔs are used to denote 5,000, 50,000, etc. For example:

Sometimes CIƆ was reduced to an lemniscate symbol ( $\infty$ ) for denoting 1,000. John Wallis is often credited for introducing this symbol to represent infinity, and one conjecture is that he based it off of this usage, since 1,000 was hyperbolically used to represent very large numbers.

In medieval times, before the letter j emerged as a distinct letter, a series of letters i in Roman numerals was commonly ended with a flourish; hence they actually looked like ij, iij, iiij, etc. This proved useful in preventing fraud, as it was impossible, for example, to add another i to vij to get viij. This practice is now merely an antiquarian's note; it is never used. (It did, however, lead to the Dutch diphthong IJ.)

Table of Roman numerals
The "modern" Roman numerals, post-Victorian era, are shown below:

An accurate way to write large numbers in Roman numerals is to handle first the thousands, then hundreds, then tens, then units.

Example: the number 1988.

One thousand is M, nine hundred is CM, eighty is LXXX, eight is VIII.

Put it together: MCMLXXXVIII (ⅯⅭⅯⅬⅩⅩⅩⅤⅠⅠⅠ).

Unicode has a number of characters specifically designated as Roman numerals, as part of the Number Forms range from U+2160 to U+2183. For example, MCMLXXXVIII could alternatively be written as
ⅯⅭⅯⅬⅩⅩⅩⅧ. This range includes both upper- and lowercase numerals, as well as pre-combined glyphs for numbers up to 12 (Ⅻ or XII), mainly intended for the clock faces for compatibility with non–West-European encodings. The pre-combined glyphs should only be used to represent the individual numbers where the use of individual glyphs is not wanted, and not to replace compounded numbers. Similarly precombined glyphs for 5000 and 10000 exist.

The Unicode characters are present only for compatibility with other character standards which provide these characters; for ordinary uses, the regular Latin letters are preferred. Displaying these characters requires a user agent that can handle Unicode and a font that contains appropriate glyphs for them.

Games
After the Renaissance, the Roman system could also be used to write chronograms. It was common to put in the first page of a book some phrase, so that when adding the I, V, X, L, C, D, M present in the phrase, the reader would obtain a number, usually the year of publication. The phrase was often (but not always) in Latin, as chronograms can be rendered in any language that utilises the Roman alphabet.

References

-

External links

- [http://ostermiller.org/calc/roman.html Roman Numeral Conversion Calculator and Self Test]

- [http://www.ubr.com/clocks/faq/iiii.html FAQ: Roman IIII vs. IV on Clock Dials]

- [http://www.straightdope.com/classics/a2_153 Why do clocks with Roman numerals use "IIII" instead of "IV"?] (from The Straight Dope)

- [http://web.archive.org/web/20041119032330/http://www.wilkiecollins.demon.co.uk/roman/front.htm Roman Numerals listing from Archive.org]

- [http://alanwood.net/unicode/number_forms.html Roman numbers in Unicode]

Category:Ancient Rome

ko:로마 숫자

ja:ローマ数字

th:เลขโรมัน

Binary numeral system
The binary numeral system represents numeric values using two symbols, typically 0 and 1. More specifically, binary is a positional notation with a radix of two. Owing to its relatively straightforward implementation in electronic circuitry, the binary system is used internally by virtually all modern computers.

History
Ancient Indian mathematician Pingala presented the first known description of a binary numeral system in the 3rd century BC, which coincided with his discovery of the concept of zero.

The modern binary number system was fully documented by Gottfried Leibniz in the 17th century in his article Explication de l'Arithmétique Binaire. Leibniz's uses 0 and 1, like the modern binary numeral system.

In 1854, British mathematician George Boole published a landmark paper detailing a system of logic that would become known as Boolean algebra. His logical system proved instrumental in the development of the binary system, particularly in its implementation in electronic circuitry.

In 1937, Claude Shannon produced his master's thesis at MIT that implemented Boolean algebra and binary arithmetic using electronic relays and switches for the first time in history. Entitled A Symbolic Analysis of Relay and Switching Circuits, Shannon's thesis essentially founded practical digital circuit design.

In November of 1937, George Stibitz, then working at Bell Labs, completed a relay-based computer he dubbed the "Model K" (for "kitchen", where he had assembled it), which calculated using binary addition. Bell Labs thus authorized a full research program in late 1938 with Stibitz at the helm. Their Complex Number Computer, completed January 8, 1940, was able to calculate complex numbers. In a demonstration to the American Mathematical Society conference at Dartmouth College on September 11, 1940, Stibitz was able to send the Complex Number Calculator remote commands over telephone lines by a teletype. It was the first computing machine ever used remotely over a phone line. Some participants of the conference who witnessed the demonstration were John Von Neumann, John Mauchly, and Norbert Wiener, who wrote about it in his memoirs.

Representation

A binary number can be represented by any sequence of bits (binary digits), which in turn may be represented by any mechanism capable of being in two mutually exclusive states. The following sequences of symbols could all be interpreted as different binary numeric values:

1 0 1 0 0 1 1
- | | - -
x x x o x o o
n y y n

bit to express binary values. In this clock, each column of LEDs shows a binary-coded decimal numeral of the traditional sexagesimal time. ]]

The numeric value represented in each case is dependent upon the value assigned to each symbol. In a computer, the numeric values may be represented by two different voltages; on a magnetic disk, magnetic polarities may be used. A "positive", "yes", or "on" state is not necessarily equivalent to the numerical value of one; it depends on the architecture in use.

In keeping with customary representation of numerals using arabic numerals, binary numbers are commonly written using the symbols 0 and 1. When written, binary numerals are often subscripted or suffixed in order to indicate their base, or radix. The following notations are equivalent:

:100101 binary (explicit statement of format)
:100101b (a suffix indicating binary format)
:bin 100101 (a prefix indicating binary format)
:100101₂ (a subscript indicating base-2 notation)

When spoken, binary numerals are usually pronounced by pronouncing each individual digit, in order to distinguish them from decimal numbers. For example, the binary numeral "100" is pronounced "one zero zero", rather than "one hundred", to make its binary nature explicit, and for purposes of correctness. Since the binary numeral "100" is equal to the decimal value four, it would be confusing, and numerically incorrect, to refer to the numeral as "one hundred."

Counting in binary

Counting in binary is similar to counting in any other number system. Beginning with a single digit, counting proceeds through each symbol, in increasing order. Decimal counting uses the symbols 0 through 9, while binary only uses the symbols 0 and 1.

When the symbols for the first digit are exhausted, the next-higher digit (to the left) is incremented, and counting starts over at 0. In decimal, counting proceeds like so:

:00, 01, 02, ... 07, 08, 09 (rightmost digit starts over, and the 0 is incremented)
:10, 11, 12, ... 17, 18, 19 (rightmost digit starts over, and the 1 is incremented)
:20, 21, 22, ...

When the rightmost digit reaches 9, counting returns to 0, and the second digit is incremented. In binary, counting is similar, with the exception that only the two symbols 0 and 1 are used. When 1 is reached, counting begins at 0 again, with the digit to the left being incremented:

:000, 001 (rightmost digit starts over, and the second 0 is incremented)
:010, 011 (middle and rightmost digits start over, and the first 0 is incremented)
:100, 101 (rightmost digit starts over again, middle 0 is incremented)
:110, 111...

Binary Simplified!

Okay, for those of us, like me, who have trouble understanding binary, think of it like this...

We use a base ten system. What this means, exactly, is that the value of each position in a numerical value can be represented by one of ten possible symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9 We are all familiar with these and how the decimal system works using these ten symbols. When we begin counting values, we should start with the symbol 0, and proceed to 9 when counting. We call this the "ones" place.

The "ones" place, with those digits, might be thought of as a multiplication problem. 5 can be thought of as 5 X 10^0 (10 to the zeroeth power, which equals 5 X 1, since any number to the zero power is one). [10^0 = 1] As we move to the left of the ones place, we increase the power of 10 by one. Thus, to represent 50 in this same manner, it can be thought of as 5 X 10^1, or 5 X 10.

$500 = (5 - 10^2) + (0 - 10^1) + (0 - 10^0) = 5 - 100$
$5000 = (5 - 10^3) + (0 - 10^2) + (0 - 10^1) + (0 - 10^0) = 5 - 1000$

When we run out of symbols in the decimal numeral system, we "move to the left" one place and use a '1' to represent the "tens" place. Then we reset the symbol in the "ones" place back to the first symbol, zero.

Binary is a base two system which works just like our decimal system, however with only two symbols which can be used to represent numerical values: 0 and 1. We begin in the "ones" place with 0, then go up to 1. Now we are out of symbols, so to represent a higher value, we must place a '1' in the "twos" place, since we don't have a symbol we can use in the binary system for 2, like we do in the decimal system.

In the binary numeral system, the value represented as 10 is 0 times (1
- 2^1) + (0
- 2^0). Thus, it equals '2' in our decimal system.

Binary - to - Decimal equivalence:

$1 = 1 - 2^0 = 1 - 1 = 1$

$10 = (1 - 2^1) + (0 - 2^0) = 2 + 0 = 2$

$100 = (1 - 2^2) + (0 - 2^1) + (0 - 2^0) = 4 + 0 + 0 = 4$

While this is in the conversion guide, it is 'hidden', and the conversion guide makes it a little more complicated.

Binary arithmetic

Arithmetic in binary is much like arithmetic in other numeral systems. Addition, subtraction, multiplication, and division can be performed on binary numerals.

Addition

decimal, which adds two bits together, producing sum and carry bits.]]

The simplest arithmetic operation in binary is addition. Adding two single-digit binary numbers is relatively simple:

:0 + 0 = 0
:0 + 1 = 1
:1 + 0 = 1
:1 + 1 = 10 (the 1 is carried)

Adding two "1" values produces the value "10", equivalent to the decimal value 2. This is similar to what happens in decimal when certain single-digit numbers are added together; if the result exceeds the value of the radix (10), the digit to the left is incremented:

:5 + 5 = 10
:7 + 9 = 16

This is known as carrying in most numeral systems. When the result of an addition exceeds the value of the radix, the procedure is to "carry the one" to the left, adding it to the next positional value. Carrying works the same way in binary:

1 1 1 1 1 (carry)
0 1 1 0 1
+ 1 0 1 1 1
-------------
= 1 0 0 1 0 0

In this example, two numerals are being added together: 01101 (13 decimal) and 10111 (23 decimal). The top row shows the carry bits used. Starting in the rightmost column, 1 + 1 = 10. The 1 is carried to the left, and the 0 is written at the bottom of the rightmost column. The second column from the right is added: 1 + 0 + 1 = 10 again; the 1 is carried, and 0 is written at the bottom. The third column: 1 + 1 + 1 = 11. This time, a 1 is carried, and a 1 is written in the bottom row. Proceeding like this gives the final answer 100100.

Subtraction

Subtraction works in much the same way:

:0 - 0 = 0
:0 - 1 = 1 (with borrow)
:1 - 0 = 1
:1 - 1 = 0

One binary numeral can be subtracted from another as follows:

-
-
-
- (starred columns are borrowed from)
1 1 0 1 1 1 0
- 1 0 1 1 1
----------------
= 1 0 1 0 1 1 1

Subtracting a positive number is equivalent to adding a negative number of equal absolute value; computers typically use the two's complement notation to represent negative values. This notation eliminates the need for a separate "subtract" operation. For further details, see two's complement.

Multiplication

Multiplication in binary is similar to its decimal counterpart. Two numbers A and B can be multiplied by partial products: for each digit in B, the product of that digit in A is calculated and written on a new line, shifted leftward so that its rightmost digit lines up with the digit in B that was used. The sum of all these partial products gives the final result.

Since there are only two digits in binary, there are only two possible outcomes of each partial multiplication:

- If the digit in B is 0, the partial product is also 0

- If the digit in B is 1, the partial product is equal to A

For example, the binary numbers 1011 and 1010 are multiplied as follows:

1 0 1 1 (A)
× 1 0 1 0 (B)
---------
0 0 0 0 ← Corresponds to a zero in B
1 0 1 1 ← Corresponds to a one in B
0 0 0 0
+ 1 0 1 1
---------------
= 1 1 0 1 1 1 0

See also Booth's multiplication algorithm.

Division

Binary division is again similar to its decimal counterpart:

__________
1 0 1 | 1 1 0 1 1

Here, the divisor is 101, or 5 decimal, while the dividend is 11011, or 27 decimal. The procedure is the same as that of decimal long division; here, the divisor 101 goes into the first three digits 110 of the dividend one time, so a "1" is written on the top line. This result is multiplied by the divisor, and subtracted from the first three digits of the dividend; the next digit (a "1") is included to obtain a new three-digit sequence:

1
__________
1 0 1 | 1 1 0 1 1
- 1 0 1
-----
0 1 1

The procedure is then repeated with the new sequence, continuing until the digits in the dividend have been exhausted:

1 0 1
__________
1 0 1 | 1 1 0 1 1
- 1 0 1
-----
0 1 1
- 0 0 0
-----
1 1 1
- 1 0 1
-----
1 0

Thus, the quotient of 11011 divided by 101 is 101₂, as shown on the top line, while the remainder, shown on the bottom line, is 10₂. In decimal, 27 divided by 5 is 5, with a remainder of 2.

Bitwise logical operations

Though not directly related to the numerical interpretation of binary symbols, sequences of bits may be manipulated using Boolean logical operators. When a string of binary symbols is manipulated in this way, it is called a bitwise operation; the logical operators AND, OR, and XOR may be performed on corresponding bits in two binary numerals provided as input. The logical NOT operation may be performed on individual bits in a single binary numeral provided as input. Sometimes, such operations may be used as arithmetic short-cuts, and may have other computational benefits as well. For example, discarding the last bit of a binary number (also known as binary shifting), is the decimal equivalent of division by two. See Bitwise operation.

Conversion to and from other numeral systems
Decimal
This method works for conversion from any base, but there are better methods for bases which are powers of two, such as octal and hexadecimal given below.

In place-value numeral systems, digits in successively lower, or less significant, positions represent successively smaller powers of the radix. The starting exponent is one less than the number of digits in the number. A five-digit number would start with an exponent of four. In the decimal system, the radix is 10 (ten), so the left-most digit of a five-digit number represents the 10⁴ (ten thousands) position. Consider:

:97352₁₀ is equal to:
::9 times 10⁴ (9 × 10000 = 90000) plus
::7 times 10³ (7 × 1000 = 7000) plus
::3 times 10² (3 × 100 = 300) plus
::5 times 10¹ (5 × 10 = 50) plus
::2 times 10⁰ (2 × 1 = 2)

Multiplication by the radix is simple. The digits are shifted left, and a 0 is appended to the right end of the number. For example, 9735 times 10 is equal to 97350. So one way to interpret a string of digits is as the last digit added to the radix times all but the last digit. 97352 equals 9735 times 10 plus 2. An example in binary is 1101100111₂ equals 110110011₂ times 2 plus 1. This is the essence of the conversion method. At each step, write the number to be converted as 2
- k + 0 or 2
- k + 1 for an integer k, which becomes the new number to be converted.

:118₁₀ equals
::59 x 2 + 0
::(29 x 2 + 1) x 2 + 0
::((14 x 2 + 1) x 2 + 1) x 2 + 0
::(((7 x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0
::((((3 x 2 + 1) x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0
::(((((1 x 2 + 1) x 2 + 1) x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0
::1 x 2⁶ + 1 x 2⁵ + 1 x 2⁴ + 0 x 2³ + 1 x 2² + 1 x 2¹ + 0 x 2⁰
::1110110₂

So in the algorithm to convert from an integer decimal numeral to its binary equivalent, the number is divided by two, and the remainder written in the ones-place. The result is again divided by two, its remainder written in the next place to the left. This process repeats until the number becomes zero.

For example, 118₁₀, in binary, is:

Reading the sequence of remainders from the bottom up gives the binary numeral 1110110₂.

To convert from binary to decimal is the reverse algorithm. Starting from the left, double the result and add the next digit until there are no more. For example to convert 110010101101₂ to decimal:

and the result is 3245₁₀.

The fractional parts of a numbers are converted with similar methods. They are again based on the equivalence of shifting with doubling or halving.

In a fractional binary number such as .11010110101₂, the first digit is 1/2, the second 1/2², etc. So if there is a 1 in the first place after the decimal, then the number is at least 1/2, and vice versa. Double that number is at least 1. This suggests the algorithm: Repeatedly double the number to be converted, record if the result is at least 1, and then throw away the integer part.

For example, (1/3)₁₀, in binary, is:

which is the repeating fraction 0.0101...₂

Or for example, 0.1₁₀, in binary, is:

which is also a repeating fraction 0.000110011...₂ It may come as a surprise that terminating decimal fractions can have repeating expansions in binary. It is for this reason that many are surprised to discover that 0.1 + ... + 0.1, (10 additions) differs from 1 in floating point arithmetic. In fact, the only binary fractions with terminating expansions are of the form of an integer divided by a power of 2, which 1/10 is not.

The final conversion is from binary to decimal fractions. The only difficulty arises with repeating fractions, but otherwise the method is to shift the fraction to an integer, convert it as above, and then divide by the appropriate power of two in the decimal base. For example,

Another way, perhaps quicker and more efficient than the previous, of converting from binary to decimal, is to do so indirectly- first converting (x binary) or (x decimal) to (x hexidecimal) and then converting (x hexidecimal) to the opposite of the former, respectively.

Hexadecimal

Binary may be converted to and from hexadecimal somewhat more easily. This is due to the fact that the radix of the hexadecimal system (16) is a power of the radix of the binary system (2). More specifically, 16 = 2⁴, so it takes exactly four digits of binary to represent one digit of hexadecimal.

The following table shows each hexadecimal digit along with the equivalent four-digit binary sequence:

To convert a hexadecimal number into its binary equivalent, simply substitute the corresponding binary digits:

:3A₁₆ = 0011 1010₂
:E7₁₆ = 1110 0111₂

To convert a binary number into its hexadecimal equivalent, divide it into groups of four bits. If the number of bits isn't a multiple of four, simply insert extra 0 bits at the left (called padding). For example:

:1010010₂ = 0101 0010 grouped with padding = 52₁₆
:11011101₂ = 1101 1101 grouped = DD₁₆

Octal
Binary is also easily converted to the octal numeral system, since octal uses a radix of 8, which is a power of two (namely, 2³, so it takes exactly three binary digits to represent an octal digit). The correspondence between octal and binary numerals is the same as for the first eight digits of hexadecimal in the table above. Binary 000 is equivalent to the octal digit 0, binary 111 is equivalent to octal 7, and so on.

Converting from octal to binary proceeds in the same fashion as it does for hexadecimal:

:65₈ = 110 101₂
:17₈ = 001 111₂

And from binary to octal:

:101100₂ = 101 100₂ grouped = 54₈
:10011₂ = 010 011₂ grouped with padding = 23₈

Representing real numbers

Non-integers can be represented by using negative powers, which are set off from the other digits by means of a radix point (called a decimal point in the decimal system). For example, the binary number 11.01₂ thus means:

:1 times 2¹ (1 × 2 = 2) plus
:1 times 2⁰ (1 × 1 = 1) plus
:0 times 2^-1 (0 × (1/2) = 0) plus
:1 times 2^-2 (1 × (1/4) = 0.25)

For a total of 3.25 decimal.

All dyadic rational numbers p/2^a have a terminating binary numeral -- the binary representation has only finitely many terms after the radix point. Other rational numbers have binary representation, but instead of terminating, they recur, with a finite sequence of digits repeating indefinitely. For instance
:1/3₁₀ = 1/11₂ = 0.0101010101...₂
:12₁₀/17₁₀ = 1100₂ / 10001₂ = 0.10110100 10110100 10110100...₂
The phenomenon that the binary representation of any rational is either terminating or recurring also occurs in other radix-based numeral systems. See, for instance, the explanation in Decimal. Another similarity is the existence of alternative representations for any terminating representation, relying on the fact that 0.111111... is the sum of the geometric series 2^-1 + 2^-2 + 2^-3 + ... which is 1.

Binary numerals which neither terminate nor recur represent irrational numbers. For instance,

- 0.10100100010000100000100.... does have a pattern, but it is not a fixed-length recurring pattern, so the number is irrational

- 1.0110101000001001111001100110011111110... is the binary representation of √2, the square root of 2, another irrational. It has no discernible pattern, although a proof that √2 is irrational requires more than this. See irrational number.

Binary humor

- "Binary is as easy as 1, 10, 11."

- "There are 10 kinds of people in the world - those who understand binary numbers, and those who don't."

See also

- Binary-coded decimal

- Pingala

External links

- [http://www.insidereality.net/site/content/math/base_conversion.php Simple Conversion Methods]

- [http://www-history.mcs.st-andrews.ac.uk/history/Projects/Pearce/index.html Indian mathematics]

- [http://www.cut-the-knot.org/binary.shtml Base Converter] at cut-the-knot

- [http://www.cut-the-knot.org/do_you_know/BinaryHistory.shtml Binary System] at cut-the-knot

- [http://www.cut-the-knot.org/blue/frac_conv.shtml Conversion of Fractions] at cut-the-knot

- [http://leetkey.mozdev.org This FireFox extension supports ASCII/Binary conversions and typing]

- [http://www.permadi.com/tutorial/numHexToDec/ Converting Hexadecimal to Decimal]

- [http://www.permadi.com/tutorial/numDecToHex/ Converting Decimal to Hexadecimal]

- [http://www.paulschou.com/tools/xlate/ Online tool] to translate ASCII to/from Binary, Hex, Decimal and Base64

Category:Computer arithmetic
Category:Elementary arithmetic
Category:Numeration
2

ja:2進数

th:เลขฐานสอง

Sphenic number
A sphenic number (Old Greek sphen = wedge) is a positive integer that is the product of three distinct prime factors. The Möbius function returns when passed any sphenic number.

Note that this definition is more stringent than simply requiring the integer to have exactly three prime factors; e.g. 60 = 2² × 3 × 5 has exactly 3 prime factors, but is not sphenic.

All sphenic numbers have exactly eight divisors. If we express the sphenic number as $n = p \cdot q \cdot r$ , where p, q, and r are distinct primes, then the set of divisors of n will be:

: $\left\$

The first few sphenic numbers are: 30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, ...

Currently, the largest known sphenic number is (2^20,996,011 − 1)(2^24,036,583 − 1)(2^25,964,951 − 1).

External links

- [http://www.research.att.com/projects/OEIS?Anum=A007304 Sphenic numbers] from On-Line Encyclopedia of Integer Sequences.

Category:Integer sequences
Category:Prime numbers

Triangular number
A triangular number is a number that can be arranged in the shape of an equilateral triangle. The sequence of triangular numbers for n = 1, 2, 3... is:
:1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Since each row is one unit longer than the previous row it can be seen that a triangular number is the sum of consecutive integers.

The formula for the nth triangular number is ½n(n + 1) or (1 + 2 + 3 + ... + [n − 2] + [n − 1] + n).

It is the binomial coefficient
:

It can also be shown that for any n-dimensional simplex with sides of length x,
the formula

$\frac$

yields the number of points that make up the simplex. For example, a tetrahedron with sides of length 2 corresponds to the number (2)(2 + 1)(2 + 2)/6, or 4. The four points forming this configuration are the vertices of the tetrahedron.
(Note: A tetrahedron can be created by taking a number, getting the triangle of that number, and then adding to it all the triangles of the numbers before it, so a tetrahedron of 2 would have 2 triangles = 3 plus 1 triangles = 1 = 4.)

One of the most famous triangular numbers is 666, also known as the Number of the Beast. Every even perfect number is triangular.

The sum of two consecutive triangular numbers is a square number. This can be shown mathematically thus: the sum of the nth and (n-1)th triangular numbers is + . This simplifies to (½n² + ½n) + (½n² − ½n), and thus to n². Alternatively, it can be demonstrated diagrammatically, thus:

In each of the above examples, a square is formed from two interlocking triangles.

More generally, the difference between the nth m-gonal number and the nth (m+1)-gonal number is the (n-1)th triangular number. For example, the sixth heptagonal number (81) minus the sixth hexagonal number (66) equals the fifth triangular number, 15.

Also, the square of a triangular number n is the same as the sum of the cubes of the integers 1 to n.

In base 10, the digital root of a triangular number is always 1, 3, 6 or 9. Hence every triangular number is either divisible by three or has a remainder of 1 when divided by nine:
:6 = 3×2,
:10 = 9×1+1,
:15 = 3×5,
:21 = 3×7,
:28 = 9×3+1,
:...

Triangular numbers have all sorts of relations to other figurate numbers. Whenever a triangular number is divisible by 3, one third of it will be a pentagonal number. Every other triangular number is a hexagonal number.

Knowing the triangular numbers, one can reckon any centered polygonal number. The nth centered k-gonal number is obtained by the formula

$Ck_n = kT_+1$

where T is a triangular number.

There are infinitely many triangular numbers that are also square numbers; e.g., 1, 36. Some of them can be generated by a simple recursive formula:

: $S_ = 4S_n \left( 8S_n + 1\right)$ with $S_1 = 1$

All square triangular numbers are found from the recursion

: $S_n = 34S_ - S_ + 2$ with $S_0 = 0$ and $S_1 = 1$

See also

- square number

- polygonal number

- triangular square number

- centered triangular number

- tetrahedral number

- tetractys

External links

- [http://www.cut-the-knot.org/do_you_know/numbers.shtml#square Triangular numbers] at cut-the-knot

- [http://www.cut-the-knot.org/do_you_know/triSquare.shtml There exist triangular numbers that are also square] at cut-the-knot

- [http://mathworld.wolfram.com/TriangularNumber.html Mathworld]

Category:Figurate numbers

ko:삼각수

ja:三角数

Semi-meandric number
In mathematics, a meander or closed meander is a self-avoiding closed curve which intersects a line a number of times. Intuitively, a meander can be viewed as a road crossing a river through a number of bridges.

Meander

Given a fixed oriented line L in the Euclidean plane R², a meander of order n is a non-self-intersecting closed curve in R² which transversally intersects the line at 2n points for some positive integer n. Two meand}