java - 求一个整数 n > 0 满足以下三个条件

Question

初学者的一些定义:flip(n) 是将七段显示字体编号旋转 180 度，因此七段字体中的 2 将翻转为 2。0,1,2,5,8 将是映射到自己。 6 -> 9、9 -> 6 和 3、4、7 未定义。因此，任何包含 3、4、7 的数字都不可翻转。更多示例:flip(112) = 211、flip(168) = 891、flip(3112) = 未定义。

(顺便说一下，我很确定 flip(1) 应该是未定义的，但是作业说 flip(168) = 891 所以关于这个赋值 flip(1) 是定义的)

原始挑战:找到满足以下三个条件的整数 n > 0:

1. 定义了 flip(n) 并且 flip(n) = n
2. 定义翻转(n*n)
3. n 可以被 2011 整除 -> n % 2011 == 0

您可以在下面找到的我们的解决方案似乎有效，但至少在 2011 年找不到答案。如果我改用 1991 年(我搜索了一些可以解决问题的“基本”数字)我很快得到一个答复，说 1515151 就是那个。因此，基本概念似乎有效，但不适用于家庭作业中给定的“基础”。 我是不是漏掉了什么？

用伪代码编写的解决方案(我们在 Small Basic 中有一个实现，我用 Java 做了一个多线程的):

for (i = 1; i < Integer.MaxValue; i++) {
  n = i * 2011;
  f = flip(n, true);
  if (f != null && flip(n*n, false) != null) {
    print n + " is the number";
    return;
  }
}


flip(n, symmetry) {
  l = n.length;
  l2 = (symmetry) ? ceil(l/2) : l;
  f = "";

  for (i = 0; i < l2; i++) {
    s = n.substr(i,1);
    switch(s) {
      case 0,1,2,5,8:
        r = s; break;
      case 6:
        r = 9; break;
      case 9:
        r = 6; break;
      default:
        r = "";
    }
    if (r == "") {
      print n + " is not flippable";
      return -1;
    } elseif (symmetry && r != n.substr(l-i-1,1)) {
      print n + " is not flip(n)";
      return -1;
    }
    f = r + f;
  }
  return (symmetry) ? n : f;
}

Answer 1

启发式(公认的是最少的实验，主要依靠直觉)，如果不优化您的搜索技术数学(例如，采用构造方法来构建一个完美的不包含 3、4、7 且可翻转对称的正方形。与优化计算相反，后者不会显着改变复杂性):

我将从满足 2 个条件的所有数字列表开始(数字和它的翻转是相同的，即翻转对称，并且它是 2011 的倍数)，小于 10^11:

192555261 611000119 862956298 988659886 2091001602 2220550222 2589226852 6510550159 8585115858 10282828201 12102220121 18065559081 18551215581 19299066261 20866099802 22582528522 25288188252 25510001552 25862529852 28018181082 28568189582 28806090882 50669869905 51905850615 52218581225 55666299955 58609860985 59226192265 60912021609 68651515989 68828282889 69018081069 69568089569 85065859058 85551515558 89285158268 91081118016 92529862526 92852225826 95189068156 95625052956 96056895096 96592826596 98661119986 98882128886 98986298686

那里有 46 个数字，根据定义和 2011 年的倍数，所有数字都是可翻转对称的，小于 10^11。看起来满足此条件的 2011 的倍数将变得越来越少，因为从统计上看，随着位数的增加，回文的倍数会越来越少。

即对于任何给定的范围，比如 [1, 10^11](如上)，有 46 个。对于宽度相等的相邻范围:[10^11+1, 2*10^11]，我们可能会猜测找到另一个46左右。但是，随着我们继续以 10 的更高次幂使用相同宽度的间隔，数字的数量是相同的(因为我们分析的是等宽度间隔)，尽管回文条件现在落在更多的数字上，因为数字的数量增加了。因此，接近无穷大时，我们期望任何固定间隔上的回文数接近 0。或者，更正式地(但没有证明)对于每个正值 N，给定间隔(预定宽度)的概率为 0 将具有多于 N 的倍数2011 年的回文数。

因此，随着穷举搜索的继续，我们可以找到的回文数将会减少。根据任何发现的回文方 block 可翻转的概率，我们假设回文方 block 均匀分布(因为我们没有分析告诉我们其他情况，也没有理由相信其他情况)，然后任何给定方 block 的概率可翻转的 d 位数长度为 (7/10)^d。

让我们从我们找到的最小的这样的正方形开始

192555261 ^ 2 = 37077528538778121

它已经有 17 位数字长，因此它被可翻转定义的概率约为 0.002(约 1/430)。但是当我们到达列表中的最后一个时:

98986298686 ^ 2 = 9798287327554005326596

长度为 24 位，被翻转定义的概率小于 1/5000。

因此，随着搜索继续以更高的数字进行，回文的数量会减少，并且任何找到的回文正方形可翻转的概率也会降低 - 一把双刃剑。

剩下的就是找到某种密度比，并相应地了解找到解决方案的可能性有多大......尽管直觉上很清楚，从概率上讲，找到解决方案的可能性要小得多(这绝不排除那个或甚至存在大量的解决方案(可能是无限多？))。

祝你好运!我希望有人能解决这个问题。与许多问题一样，解决方案通常不像在更快的机器上运行算法或具有更多并行性或更长的时间等那样简单，而是使用更先进的技术或更具创造性的方法来解决问题，这自己更进一步的领域。答案是一个数字，(通常)比用于推导它的方法更不重要。