kaprekar.cpp

/* find loops in kaprekar's operation sequence
 * written by [email protected]
 * USAGE: kaprekar <digit>
 */

#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>

#define FIND_MAX 100

typedef unsigned long long int    ull_int;
typedef std::map<ull_int,ull_int> kap_memo;
typedef std::set<ull_int>         loop_set;

static kap_memo  memo;

int     find_loops(int);
ull_int kap_calc(ull_int, int);
ull_int memo_kap_calc(ull_int, int);
void    print_loop(ull_int*, int, int);


int main(int argc, char *argv[]) {
  int count;
  int digit=0;

  memo.clear();

  digit = atoi(argv[1]);
  std::cout << "Kaprekar loops by " << digit << "-digit" << std::endl;

  count = find_loops(digit);
  std::cout << "count: " << count << std::endl << std::endl;

  std::cout << "memo size: " << memo.size() << std::endl;

  return 0;
}


int find_loops(int digit) {
  ull_int  max = pow(10, digit) - 1;
  ull_int  seq[FIND_MAX+1];
  loop_set loops;
  int      start;
  int      count = 0;
  int      per = 0;

  loops.clear();
  loops.insert(0ull);

  for (ull_int i=9ull; i<=max; i+=9) {
    if (i > max*per/100) {
      std::clog << ".." << per << "% "<< i << " done." << std::endl;
      per+=5;
    }

    seq[0] = i;
    seq[1] = kap_calc(i, digit);
    for (int j=1; j<FIND_MAX-1; j++) {
      seq[j+1] = memo_kap_calc(seq[j], digit);

      if (loops.find(seq[j+1]) != loops.end()) break;

      start = j;
      while (start>=0 && seq[j+1]!=seq[start])
        start--;

      if (start != -1) {
        loops.insert(seq + start, seq + j+1);
        count++;
        print_loop(seq, start, j+1);
        break;
      }
    }
  }

  return count;
}


ull_int kap_calc(ull_int n, int digit) {
  ull_int bigger, smaller, temp;
  int     buf[20];

  temp = n;
  for (int i=0; i<digit; i++) {
    buf[i] = (int)(temp / pow(10, (digit-i-1)));
    temp -= buf[i] * pow(10, (digit-i-1));
  }

  std::sort(buf, buf + digit);

  smaller = 0;
  bigger  = 0;
  for (int i=0; i<digit; i++) {
    smaller *= 10;
    smaller += buf[i];
    bigger  *= 10;
    bigger  += buf[digit-i-1];
  }

  return bigger - smaller;
}


ull_int memo_kap_calc(ull_int n, int digit) {
  ull_int ret;

  kap_memo::iterator it = memo.find(n);
  if (it != memo.end() ) return (*it).second;

  ret = kap_calc(n, digit);

  try {
    if (memo.find(n) == memo.end())
      memo.insert(std::make_pair(n, ret));
  }
  catch (std::bad_alloc e) {
    memo.clear();
    std::clog << "!! bad_alloc memoize !!" << std::endl;
  }

  return ret;
}


void print_loop(ull_int* loop, int start, int end) {
  std::cout << end - start << " : ";
  for (int i=start; i<end; i++)
    std::cout << loop[i] << " ";
  std::cout << std::endl;
}

loops.txt

Kaprekar loops by 1-digit
count: 0

Kaprekar loops by 2-digit
5 : 9 81 63 27 45 
count: 1

Kaprekar loops by 3-digit
1 : 495 
count: 1

Kaprekar loops by 4-digit
1 : 6174 
count: 1

Kaprekar loops by 5-digit
2 : 53955 59994 
4 : 61974 82962 75933 63954 
4 : 62964 71973 83952 74943 
count: 3

Kaprekar loops by 6-digit
7 : 420876 851742 750843 840852 860832 862632 642654 
1 : 549945 
1 : 631764 
count: 3

Kaprekar loops by 7-digit
8 : 7509843 9529641 8719722 8649432 7519743 8429652 7619733 8439552 
count: 1

Kaprekar loops by 8-digit
7 : 43208766 85317642 75308643 84308652 86308632 86326632 64326654 
1 : 63317664 
3 : 64308654 83208762 86526432 
1 : 97508421 
count: 4

Kaprekar loops by 9-digit
1 : 554999445 
14 : 753098643 954197541 883098612 976494321 874197522 865296432 763197633 844296552 762098733 964395531 863098632 965296431 873197622 865395432 
1 : 864197532 
count: 3

Kaprekar loops by 10-digit
3 : 8655264432 6431088654 8732087622 
7 : 8633086632 8633266632 6433266654 4332087666 8533176642 7533086643 8433086652 
3 : 8653266432 6433086654 8332087662 
1 : 9753086421 
3 : 8321088762 8765264322 6543086544 
3 : 9751088421 9775084221 9755084421 
1 : 6333176664 
1 : 9975084201
count: 8