Skip to content

Instantly share code, notes, and snippets.

@PythonJedi
Created November 8, 2017 05:48
Show Gist options
  • Save PythonJedi/63283d8baa96219d8d1bfdf61c895762 to your computer and use it in GitHub Desktop.
Save PythonJedi/63283d8baa96219d8d1bfdf61c895762 to your computer and use it in GitHub Desktop.
Much faster implementation of Kaprekar's function
/*
* Attempt to find fixed points of a particularly interesting function.
*
* Kaprekar's function sorts the digits of n ascending and descending, then
* returns the descending minus the ascending. The fixed points of this
* function, as well as the attractor classes are very interesting.
*/
#include<stdio.h>
#include<limits.h>
void kaprekar(unsigned int, unsigned int *);
void reverse(unsigned int, unsigned int *);
void sort_digits(unsigned int, unsigned int *);
int main(int argc, char *argv[]) {
for (unsigned int i = 0; i <= UINT_MAX/10; i++) {
printf("%d", i);
unsigned int k;
kaprekar(i, &k);
if (i == k)
printf("\n"); // Newline to leave fixedpoint in console output
else
printf("\x1B[G"); // Return to beginning of line to overwrite
}
return 0;
}
void kaprekar(unsigned int x, unsigned int *result) {
unsigned int ascending, descending;
sort_digits(x, &descending);
reverse(descending, &ascending);
*result = descending-ascending;
}
void reverse(unsigned int x, unsigned int *result) {
*result = 0;
while (x > 0) {
*result = *result*10 + x%10;
x /= 10;
}
}
void sort_digits(unsigned int x, unsigned int *result) {
unsigned int mask[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
*result = 0;
while (x > 0) {
unsigned int d = x%10;
unsigned int rem = *result % mask[d];
*result = (*result - rem) * 10 + d*mask[d] + rem;
x /= 10; // Pop digit
for (int i = d+1; i < 10; i++) { // increment masks after inserted digit
mask[i] *= 10;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment