Jon Awbrey: move old intro to talk page

2010-02-04T12:22:46Z

move old intro to talk page

New page

==Place for Discussion==

<br><math>\cdots</math><br>

==Idea (Old Version)==

Let <math>\text{p}_i</math> be the <math>i^\text{th}</math> prime, where the positive integer <math>i</math> is called the ''index'' of the prime <math>\text{p}_i</math> and the indices are taken in such a way that <math>\text{p}_1 = 2.</math> Thus the sequence of primes begins as follows:

{| align="center" cellpadding="6" width="90%"
|
<math>\begin{matrix}
\text{p}_1 = 2, &
\text{p}_2 = 3, &
\text{p}_3 = 5, &
\text{p}_4 = 7, &
\text{p}_5 = 11, &
\text{p}_6 = 13, &
\text{p}_7 = 17, &
\text{p}_8 = 19, &
\ldots
\end{matrix}</math>
|}

The prime factorization of a positive integer <math>n</math> can be written in the following form:

{| align="center" cellpadding="6" width="90%"
| <math>n ~=~ \prod_{k = 1}^{\ell} \text{p}_{i(k)}^{j(k)},</math>
|}

where <math>\text{p}_{i(k)}^{j(k)}</math> is the <math>k^\text{th}</math> prime power in the factorization and <math>\ell</math> is the number of distinct prime factors dividing <math>n.</math> The factorization of <math>1</math> is defined as <math>1</math> in accord with the convention that an empty product is equal to <math>1.</math>

Let <math>I(n)</math> be the set of indices of primes that divide <math>n</math> and let <math>j(i, n)</math> be the number of times that <math>\text{p}_i</math> divides <math>n.</math> Then the prime factorization of <math>n</math> can be written in the following alternative form:

{| align="center" cellpadding="6" width="90%"
| <math>n ~=~ \prod_{i \in I(n)} \text{p}_{i}^{j(i, n)}.</math>
|}

For example:

{| align="center" cellpadding="6" width="90%"
|
<math>\begin{matrix}
9876543210
& = & 2 \cdot 3^2 \cdot 5 \cdot {17}^2 \cdot 379721
& = & \text{p}_1^1 \text{p}_2^2 \text{p}_3^1 \text{p}_7^2 \text{p}_{32277}^1.
\end{matrix}</math>
|}

Each index <math>i</math> and exponent <math>j</math> appearing in the prime factorization of a positive integer <math>n</math> is itself a positive integer, and thus has a prime factorization of its own.

Continuing with the same example, the index <math>32277</math> has the factorization <math>3 \cdot 7 \cdot 29 \cdot 53 = \text{p}_2^1 \text{p}_4^1 \text{p}_{10}^1 \text{p}_{16}^1.</math> Taking this information together with previously known factorizations allows the following replacements to be made:

{| align="center" cellpadding="6" width="90%"
|
<math>\begin{array}{rcl}
2 & \mapsto & \text{p}_1^1
\\[6pt]
3 & \mapsto & \text{p}_2^1
\\[6pt]
7 & \mapsto & \text{p}_4^1
\\[6pt]
32277 & \mapsto & \text{p}_2^1 \text{p}_4^1 \text{p}_{10}^1 \text{p}_{16}^1
\end{array}</math>
|}

This leads to the following development:

{| align="center" cellpadding="6" width="90%"
|
<math>\begin{array}{lll}
9876543210
& = & \text{p}_1^1 \text{p}_2^2 \text{p}_3^1 \text{p}_7^2 \text{p}_{32277}^1
\\[12pt]
& = & \text{p}_1^1 \text{p}_{\text{p}_1^1}^{\text{p}_1^1} \text{p}_{\text{p}_2^1}^1 \text{p}_{\text{p}_4^1}^{\text{p}_1^1} \text{p}_{\text{p}_2^1 \text{p}_4^1 \text{p}_{10}^1 \text{p}_{16}^1}^1
\end{array}</math>
|}

Continuing to replace every index and exponent with its factorization until no index or exponent remains unfactored produces the following development:

{| align="center" cellpadding="6" width="90%"
|
<math>\begin{array}{lll}
9876543210
& = & \text{p}_1^1 \text{p}_2^2 \text{p}_3^1 \text{p}_7^2 \text{p}_{32277}^1
\\[18pt]
& = & \text{p}_1^1 \text{p}_{\text{p}_1^1}^{\text{p}_1^1} \text{p}_{\text{p}_2^1}^1 \text{p}_{\text{p}_4^1}^{\text{p}_1^1} \text{p}_{\text{p}_2^1 \text{p}_4^1 \text{p}_{10}^1 \text{p}_{16}^1}^1
\\[18pt]
& = & \text{p}_1^1 \text{p}_{\text{p}_1^1}^{\text{p}_1^1} \text{p}_{\text{p}_{\text{p}_1^1}^1}^1 \text{p}_{\text{p}_{\text{p}_1^2}^1}^{\text{p}_1^1} \text{p}_{\text{p}_{\text{p}_1^1}^1 \text{p}_{\text{p}_1^2}^1 \text{p}_{\text{p}_1^1 \text{p}_3^1}^1 \text{p}_{\text{p}_1^4}^1}^1
\\[18pt]
& = & \text{p}_1^1 \text{p}_{\text{p}_1^1}^{\text{p}_1^1} \text{p}_{\text{p}_{\text{p}_1^1}^1}^1 \text{p}_{\text{p}_{\text{p}_1^{\text{p}_1^1}}^1}^{\text{p}_1^1} \text{p}_{\text{p}_{\text{p}_1^1}^1 \text{p}_{\text{p}_1^{\text{p}_1^1}}^1 \text{p}_{\text{p}_1^1 \text{p}_{\text{p}_2^1}^1}^1 \text{p}_{\text{p}_1^{\text{p}_1^2}}^1}^1
\\[18pt]
& = & \text{p}_1^1 \text{p}_{\text{p}_1^1}^{\text{p}_1^1} \text{p}_{\text{p}_{\text{p}_1^1}^1}^1 \text{p}_{\text{p}_{\text{p}_1^{\text{p}_1^1}}^1}^{\text{p}_1^1} \text{p}_{\text{p}_{\text{p}_1^1}^1 \text{p}_{\text{p}_1^{\text{p}_1^1}}^1 \text{p}_{\text{p}_1^1 \text{p}_{\text{p}_{\text{p}_1^1}^1}^1}^1 \text{p}_{\text{p}_1^{\text{p}_1^{\text{p}_1^1}}}^1}^1
\end{array}</math>
|}

The <math>1</math>'s that appear as indices and exponents are formally redundant, conveying no information apart from the places they occupy in the resulting syntactic structure. Leaving them tacit produces the following expression:

{| align="center" cellpadding="6" width="90%"
|
<math>\begin{array}{lll}
9876543210
& = & \text{p} \text{p}_{\text{p}}^{\text{p}} \text{p}_{\text{p}_{\text{p}}} \text{p}_{\text{p}_{\text{p}^{\text{p}}}}^{\text{p}} \text{p}_{\text{p}_{\text{p}} \text{p}_{\text{p}^{\text{p}}} \text{p}_{\text{p} \text{p}_{\text{p}_{\text{p}}}} \text{p}_{\text{p}^{\text{p}^{\text{p}}}}}
\end{array}</math>
|}

An expression of this form may be referred to as the ''doubly recursive factorization'' (DRF) or ''drift'' of the positive integer from which it derives.

Directory talk:Jon Awbrey/Papers/Riffs and Rotes - Revision history

Jon Awbrey: move old intro to talk page