Java – find an integer n > 0 that contains the following three conditions

Some definitions of starter: flip (n) is the 180 degree rotation of seven segment display font numbers, so a 7 / 2 font will be flipped to 2 0,1,2,5,8 will be mapped to itself 6 – > 9,9 → 6 and 3,4,7 are not defined Therefore, any number containing 3 and 7 will not be ignored More examples: flip (112) = 211, flip (168) = 891, flip (3112) = undefined

(by the way, I'm sure that flip (1) should be undefined, but the job says flip (168) = 891, so flip (1) is defined for this assignment)

The initial challenge: find the integer n > 0, which has the following three conditions:

>Flip (n) is defined, flip (n) = n > flip (n * n) is defined > n is divisible in 2011 – > n% 2011 = = 0

The solution we can find below seems to be effective, but at least there is no answer If I'm using 1991 (I searched for some "cardinality" that can solve the problem), I get a quick answer that 1515151 is one So this basic concept seems to be valid, but it is not the "foundation" given in the assignment Did I miss anything here?

Solution written in pseudo code (we have an implementation in small basic, and I have created a multithreading in 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,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;
}

Solution

In fact (there is no doubt that the minimized experiment is mainly intuitive), it is unlikely to mathematically optimize the search technology (for example, using the architectural method to build a perfect square without 3,4) 7 and is easy to be symmetrical, rather than optimize the calculation, which will not change the complexity in a significant amount):

I will start with a list of all numbers that meet the two criteria (the number and flip are the same, that is, they can be symmetrical, it is a multiple of 2011), less than 10 ^ 11:

There are 46 numbers. According to the definition and multiple in 2011, all numbers below 10 ^ 11 can be symmetrical In 2011, it seems that the multiples will become less and less, because as the numbers increase, the fewer statistical numbers will become palindromes

That is, for any given range, say [1,10 ^ 11] (above), there is 46 For the adjacent range of equal width: [10 ^ 11 1,2 * 10 ^ 11], we may guess to find another 46 or around, but when we continue to use the interval of the same width of the higher power of 10, the number of numbers is the same (because we analyze the equal width interval), although the palindrome condition now has more numbers due to the increase of the number of numbers So close to infinity, we expect any fixed number of palindromes to be close to 0 Or, for each positive value n, more accurately (but without evidence), the probability is 0, and a given interval (predetermined width) will have more than n multiples. 2011 is palindrome

So the number of palindromes we can find will be reduced because the exhaustive search continues According to the possibility of finding any palindrome, the square will be easy. We assume that the uniform distribution of the regression square (because we have no analysis to tell us, otherwise there is no reason to believe), and then the digital length of the probability of any given square will be ridiculous (7 / 10) ^ D

We start with the smallest square we find

192555261 ^ 2 = 37077528538778121

It is already a 17 digit number, giving it a probability of about 0.002 (about 1 / 430) to be defined But when we get to the last minute of the list,

98986298686 ^ 2 = 9798287327554005326596

It is 24 digits long and has a probability of less than 1 / 5000

Therefore, as the number of searches increases, the number of palindromes decreases, and the probability of any found palindrome squared may also decrease - a double-edged sword

The rest is to find some density ratios, so look at the possibility of finding a solution... Although intuitively, the probability of finding a solution is unlikely (this definitely does not rule out the number of even a large solution (which may be an infinite number))

Good luck! I hope someone can solve this problem Like many problems, solutions usually do not run algorithms on faster machines, or have more parallelism or longer periods of time, or use more advanced technologies or more creative methods to attack the problem and further their own fields The answer, a number, is much less than the method used to derive it (usually)