SPOJ.com - Problem PROG0348

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.

Ruth in 1918, his penultimate year with the Red Sox.

Hank Aaron with the Braves in 1960.

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.

Babe Ruth in 1918, zijn voorlaatste jaar bij de Red Sox.

Hank Aaron bij de Braves in 1960.

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.

Submit solution!

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

Informatics 1