PROG0348 - Ruth-Aaron pair
The legendary baseball player Babe Ruth hit an unseen lifetime record of 714 home runs. This record stood until April 8, 1974, when it was surpassed by Hank Aaron's record-breaking 715th home run. Carl Pomerance — mathematician at the University of Georgia at the time Aaron broke Ruth's record — introduced a new concept in mathematics based on this event. The inspiration came when a student of one of Pomerance's colleagues noticed that the sums of the prime factors of 714 and 715 are equal. He therefore defined a Ruth-Aaron pair as a pair of consecutive natural numbers $(n, n + 1)$ such that the sums of the prime factors of $n$ and $n + 1$ are equal.
Each positive integer $n \in \mathbb{N_0}$ can be written as a product of prime numbers. $$\begin{eqnarray}10 &=& 2 \times 5\\12 &=& 2 \times 2 \times 3\\13 &=& 13\\100 &=& 2 \times 2 \times 5 \times 5 \end{eqnarray}$$ This decomposition in prime factors is unique, except for the order of the prime factors. The pair $(714, 715)$ is a Ruth-Aaron pair as $$\begin{eqnarray}714 &=& 2 \times 3 \times 7 \times 17\\715 &=& 5 \times 11 \times 13\end{eqnarray}$$ and $2 + 3 + 7 + 17 = 29 = 5 + 11 + 13$. The pair $(9, 10)$ is not a Ruth-Aaron pair as $2 + 5 \not= 3 + 3$.
Assignment
- Write a function isPrime that takes a positive integer $n \in \mathbb{N_0}$. The function must return a Boolean that indicates whether or not $n$ is prime.
- Write a function primeFactors that takes a positive integer $n \in \mathbb{N_0}$. The function must return the list of prime factors of $n$, sorted in increasing order.
- Write a function isRuthAaron that takes two positive integers $m, n \in \mathbb{N_0}$. The function must return a Boolean that indicates whether or not the pair $(m, n)$ is a Ruth-Aaron pair. Note that $(m, n)$ can only be a Ruth-Aaron pair if the integer $n$ immediately follows the integer $m$. The pair $(714, 715)$ is a Ruth-Aaron pair, but the pair $(715, 714)$ isn't.
Example
>>> isPrime(2) True >>> isPrime(6) False >>> isPrime(12) False >>> primeFactors(12) [2, 2, 3] >>> primeFactors(17) [17] >>> primeFactors(18) [2, 3, 3] >>> isRuthAaron(5, 6) True >>> isRuthAaron(10, 11) False >>> isRuthAaron(15, 16) True >>> isRuthAaron(8281, 8280) False
References
- Babai L, Pomerance C, Vértesi
P (1998). The Mathematics of Paul Erdos. Notices
Amer. Math. Soc. 45,
19-23.
- Drost JL (1997). Ruth/Aaron Pairs. J. Recr. Math. 28(2), 120-122.
- Erdos P, Pomerance C (1978).
On the Largest Prime Factors of $n$ and $n+1$. Aeq.
Math. 17, 311-321.
- Hoffman P (1998). The Man Who
Loved Only Numbers: The Story of Paul Erdos and the Search for
Mathematical Truth. New York: Hyperion.
- Mackenzie D (1997).
Mathematics: Homage to an Itinerant Master. Science
275, 759.
- Nelson C, Penney DE, Pomerance C
(1974). 714 and 715. J.
Recr. Math. 7, 87-89.
- Peterson I (2005). MathTrek:
Playing with Ruth-Aaron Pairs. Sci.
News 168, 2005.
- Pomerance C (2002). Ruth-Aaron
Numbers Revisited. In Paul
Erdos and his Mathematics. I. Papers
from the Conference Held in Budapest, July 4-11, 1999 (Ed. G.
Halász, L. Lovász, M. Simonovits, and V. T. Sós).
Berlin: Springer-Verlag, 567-579.
De legendarische baseballspeler Babe Ruth sloeg in zijn hele carrière een nooit gezien aantal van 714 homeruns. Dat record bleef standhouden tot 8 April 1974, toen Hank Aaron 715-de homerun van zijn carrière sloeg. Carl Pomerance — wiskundige aan de Universiteit van Georgia op het ogenblik dat Aaron het record van Ruth verbrak — baseerde zich op die gebeurtenis om een nieuw concept te introduceren in de wiskunde. Een student van een collega had immers opgemerkt dat de som van de priemfactoren van 714 en 715 gelijk is. Daarop definieerde Pomerance een Ruth-Aaron paar als een paar opeenvolgende natuurlijke getallen $(n, n + 1)$ (zoals 714 en 715) waarvoor de som van de priemfactoren gelijk is.
Elk natuurlijk getal $n \in \mathbb{N_0}$ kan geschreven worden als een product van priemgetallen. $$\begin{eqnarray}10 &=& 2 \times 5\\12 &=& 2 \times 2 \times 3\\13 &=& 13\\100 &=& 2 \times 2 \times 5 \times 5 \end{eqnarray}$$ Deze zogenaamde ontbinding in priemfactoren is uniek, afgezien van de volgorde van de priemfactoren. Het paar $(714, 715)$ is een Ruth-Aaron paar omdat $$\begin{eqnarray}714 &=& 2 \times 3 \times 7 \times 17\\715 &=& 5 \times 11 \times 13\end{eqnarray}$$ en $2 + 3 + 7 + 17 = 29 = 5 + 11 + 13$. Het paar $(9, 10)$ is geen Ruth-Aaron paar omdat $2 + 5 \not= 3 + 3$.
Opgave
- Schrijf een functie isPriem waaraan een getal $n \in \mathbb{N_0}$ moet doorgegeven worden. De functie moet een Booleaanse waarde teruggeven die aangeeft of $n$ al dan niet een priemgetal is.
- Schrijf een functie priemfactoren waaraan een getal $n \in \mathbb{N_0}$ moet doorgegeven worden. De functie moet een lijst met priemfactoren van $n$ teruggeven, waarbij de priemfactoren in oplopende volgorde gesorteerd staan.
- Schrijf een functie isRuthAaron waaraan twee getallen $m, n \in \mathbb{N_0}$ moeten doorgegeven worden. De functie moet een Booleaanse waarde teruggeven die aangeeft of het paar $(m, n)$ al dan niet een Ruth-Aaron paar is. Merk op dat $(m, n)$ enkel een Ruth-Aaron paar kan zijn als het getal $n$ onmiddellijk volgt op het getal $m$. Het paar $(714, 715)$ is een Ruth-Aaron paar, maar het paar $(715, 714)$ is dat niet.
Voorbeeld
>>> isPriem(2) True >>> isPriem(6) False >>> isPriem(12) False >>> priemfactoren(12) [2, 2, 3] >>> priemfactoren(17) [17] >>> priemfactoren(18) [2, 3, 3] >>> isRuthAaron(5, 6) True >>> isRuthAaron(10, 11) False >>> isRuthAaron(15, 16) True >>> isRuthAaron(8281, 8280) False
Bronnen
- Babai L, Pomerance C, Vértesi
P (1998). The Mathematics of Paul Erdos. Notices
Amer. Math. Soc. 45,
19-23.
- Drost JL (1997). Ruth/Aaron Pairs. J. Recr. Math. 28(2), 120-122.
- Erdos P, Pomerance C (1978).
On the Largest Prime Factors of $n$ and $n+1$. Aeq.
Math. 17, 311-321.
- Hoffman P (1998). The Man Who
Loved Only Numbers: The Story of Paul Erdos and the Search for
Mathematical Truth. New York: Hyperion.
- Mackenzie D (1997).
Mathematics: Homage to an Itinerant Master. Science
275, 759.
- Nelson C, Penney DE, Pomerance C
(1974). 714 and 715. J.
Recr. Math. 7, 87-89.
- Peterson I (2005). MathTrek:
Playing with Ruth-Aaron Pairs. Sci.
News 168, 2005.
- Pomerance C (2002). Ruth-Aaron Numbers Revisited. In Paul Erdos and his Mathematics. I. Papers from the Conference Held in Budapest, July 4-11, 1999 (Ed. G. Halász, L. Lovász, M. Simonovits, and V. T. Sós). Berlin: Springer-Verlag, 567-579.
Added by: | Peter Dawyndt |
Date: | 2013-03-30 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | PY_NBC |
Resource: | None |