SPOJ.com - Problem PROG0339

PROG0339 - Kaprekar series

no tags

The algorithm for building a Kaprekar series was discovered in 1949 by the Indian mathematical Dattaraya Ramachandra Kaprekar. The algorithm was originally described for numbers with four digits, but it can be easily generalized for numbers with $k$ digits.

The figure above shows the number of steps required to end with a value which is equal to the next value, the Kaprekar series and this for the starting numbers $n = 0, 1, \ldots, 9999$ distributed over rows of length 100. Numbers with fewer than four digits will be supplemented with additional zeroes in front, so that the Kaprekar series converges to 6174 for all values $n$.

The Kaprekar series for a number $n$ is a list of which the first element is $n$. The next number is calculated as the difference $K(n) = n' - n''$ between the number $n'$ which exists out of digits of $n$ sorted from high to low, and the number $n''$ which exists out of digits of $n$ sorted from low to high. This next number is added to the end of the list and the process is repeated. Keep repeating this process until the difference is 0, equal to the previous number or has already occurred in the list. A number that has occurred in the list is not added to the list before ending the series.

Assignment

Write a function kaprekarseries to which a number $n \in \mathbb{N}$ is to be passed as an argument. This function should return the Kaprekar series for the integer $n$ as a result.

Example

>>> kaprekar_series(677)
[677, 99, 0]
>>> kaprekar_series(9876)
[9876, 3087, 8352, 6174]
>>> kaprekar_series(55500)
[55500, 54945, 50985, 92961, 86922, 75933, 63954, 61974, 82962]

Het algoritme voor het opbouwen van een Kaprekarketen werd in 1949 ontdekt door de Indische wiskundige Dattaraya Ramchandra Kaprekar. Het algoritme werd oorspronkelijk beschreven voor getallen met vier cijfers, maar het kan makkelijk veralgemeend worden voor getallen met $k$ cijfers.

Bovenstaande figuur toont het aantal stappen die nodig zijn om de Kaprekarketen te laten eindigen op een waarde die gelijk is aan de volgende waarde, en dit voor de startgetallen $n = 0, 1, \ldots, 9999$ verdeeld over rijen van lengte 100. Hierbij worden getallen met minder dan vier cijfers vooraan aangevuld met extra nullen, zodat de Kaprekarketen voor alle waarden $n$ convergeert naar 6174.

De Kaprekarketen voor een getal $n$ is een lijst waarvan het eerste element het getal $n$ zelf is. Het volgende getal wordt berekend als het verschil $K(n) = n' - n''$ tussen het getal $n'$ dat bestaat uit de cijfers van $n$ maar gesorteerd in aflopende volgorde, en het getal $n''$ dat bestaat uit de cijfers van $n$ maar gesorteerd in oplopende volgorde. Dit volgende getal wordt achteraan de lijst toegevoegd. Blijf deze procedure herhalen om op basis van het laatste getal in de lijst telkens het volgende getal te berekenen en aan de lijst toe te voegen. De procedure eindigt als het volgende getal gelijk is aan nul, gelijk is aan het vorige getal, of als het reeds in de lijst voorkomt. Een getal dat reeds in de lijst voorkwam moet finaal niet nogmaals aan de lijst toegevoegd worden.

Opgave

Schrijf een functie kaprekarketen waaraan een getal $n \in \mathbb{N}$ als argument moet doorgegeven worden. Deze functie moet de Kaprekarketen voor het getal $n$ als resultaat teruggeven.

Voorbeeld

>>> kaprekarketen(677)
[677, 99, 0]
>>> kaprekarketen(9876)
[9876, 3087, 8352, 6174]
>>> kaprekarketen(55500)
[55500, 54945, 50985, 92961, 86922, 75933, 63954, 61974, 82962]

Submit solution!

Added by:	Peter Dawyndt
Date:	2013-02-22
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None