selfref_1.cpp

// Enjoy my mess of C and C++ style programming. I wrote this in
// Haskell first, but it was too slow, so I decided to make a mess of
// everything and do the memory management myself, which resulted in
// this surprisingly fast version. But I'm too lazy to emulate the
// std::vector sort of stuff in pure C, so I cheated here and there
// when there wasn't a bottleneck.
//
// Anyway, for digit counts from 1 to 11 (where the last digit is
// *always* the "distinct numbers" digit), this prints out every fixed
// point for each possible self-referential function.
//
// I've attached the output to this Gist, to save you the trouble of
// running it.
//
// https://math.stackexchange.com/questions/3816844/why-the-self-referential-number-function-eventually-fixes-every-point

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

void selfref(int len, int* in, int* out) {
  for (int i = 0; i < len; i++) {
    out[i] = 0;
  }
  for (int i = 0; i < len; i++) {
    out[in[i]]++;
  }
  int distinct = 0;
  for (int i = 0; i < len; i++) {
    if (out[i] > 0)
      distinct++;
  }
  out[len - 1] = distinct;
}

void printarr(int* x, int len) {
  for (int i = 0; i < len; i++) {
    std::printf("%d", x[i]);
  }
  std::printf("\n");
}

long long asnum(int* x, int len) {
  long long result = 0ll;
  for (int i = 0; i < len; i++) {
    result = result * 10 + x[i];
  }
  return result;
}

std::vector<std::vector<int>> fixedpoints(int len) {
  int* a0 = new int[len + 2]{0};
  int* b0 = new int[len + 2]{0};
  int* c0 = new int[len + 2]{0};
  int* a = a0+1;
  int* b = b0+1;
  int* c = c0+1;

  std::vector<std::vector<int>> result;
  while (true) {
    int idx = len - 1;
    while (idx > -1) {
      if (a[idx] == len - 1) {
        a[idx] = a[idx-1];
        idx -= 1;
      } else {
        a[idx] += 1;
        goto next;
      }
    }
    break;
  next:
    selfref(len, a, b);
    selfref(len, b, c);
    if (std::memcmp(b, c, len * sizeof(int)) == 0) {
      result.push_back(std::vector<int>(b, b + len));
    }
  }

  delete[] a0;
  delete[] b0;
  delete[] c0;

  return result;
}

int main() {

  for (int len = 2; len <= 14; len++) {
    std::cout << len << ":";
    auto res = fixedpoints(len);
    std::sort(res.begin(), res.end());
    auto end = std::unique(res.begin(), res.end());
    for (auto it = res.begin(); it != end; it++) {
      std::cout << " ";
      for (auto n : *it) {
        if (n > 9)
          std::cout << "(" << n << ")";
        else
          std::cout << n;
      }
    }
    std::cout << std::endl;
  }

  return 0;
}

selfref_1.txt

2:
3:
4:
5: 12104
6: 122014 130114
7: 3022003 3103003
8: 23110105
9: 322101005 412020004
10: 4220110005 4301110005
11:
12: 622001100005 630101100005
13: 7220010100005 7301010100005
14: 82200100100005 83010100100005