Find an integer n > 0 which holds the following three conditions

Some definition for starters: flip(n) is the 180 degree rotation of a seven segment display font number, so a 2 in seven segment font will be flipped to a 2. 0,1,2,5,8 will be mapped to themselfs. 6 -> 9, 9 -> 6 and 3,4,7 are not defined. Therefore any number containing 3,4,7 will not be flippable. More examples: flip(112) = 211, flip(168) = 891, flip(3112) = not defined.

(By the way, I am quite sure that flip(1) should be undefined, but the homework says that flip(168) = 891 so regarding this assignment flip(1) is defined)

The original challenge: Find an integer n > 0 which holds the following three conditions:

1. flip(n) is defined and flip(n) = n
2. flip(n*n) is def开发者_开发百科ined
3. n is divisible by 2011 -> n % 2011 == 0

Our solution which you can find below seems to work, but it does not find an answer at least not for 2011. If I am using 1991 instead (I searched for some "base" number for which the problem could be solved) I am getting a pretty fast answer saying 1515151 is the one. So the basic concept seems to work but not for the given "base" in the homework. Am I missing something here?

Solution written in pseudo code (We have an implementation in Small Basic and I made a multithreading one 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,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;
}

Heuristically (with admittedly minimal experimentation and going mainly on intuition), it is not so likely you will find a solution without optimising your search technique mathematically (e.g. employing a method of construction to build a perfect square that doesn't contain 3,4,7 and is flippably symmetrical. as opposed to optimising the computations, which will not change the complexity by a noticeable amount):

I'll start with a list of all numbers who satisfy 2 criteria (that the number and it's flip be the same, i.e. flippably symmetrical, and that it be a multiple of 2011), less than 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

There are 46 numbers there, all flippably symmetrical according to the definition and multiples of 2011, under 10^11. Seemingly multiples of 2011 that satisfy this condition will become scarcer because as the number of digits increases, less of the multiples will be palindromes, statistically.

I.e. for any given range, say [1, 10^11] (as above), there were 46. For the adjacent range of equal width: [10^11+1, 2*10^11], we might guess to find another 46 or thereabouts. But as we continue up with intervals of the same width in higher powers of 10, the number of numbers is the same (because we analyse equal width intervals) although the palindrome condition now falls on more digits because the number of digits increases. So approaching infinity we expect the number of palindromes on any fixed with interval to approach 0. Or, more formally (but without proof) for every positive value N, with probability 0 a given interval (of predetermined width) will have more than N multiples of 2011 that are palindromes.

So the number of palindromes we can find will decrease as an exhaustive search continues. As per the probability that for any found palindrome the square will be flippable, we assume uniform distribution of the squares of palindromes (since we have no analysis to tell us otherwise, and no reason to believe otherwise) and then the probability that any given square of d digits length will be flippable is (7/10)^d.

Let's start with the smallest such square we found

192555261 ^ 2 = 37077528538778121

which is already 17 digits long, giving it a probability of around 0.002 (approx. 1/430) that it's flippably defined. But already by the time we've reached the last on the list:

98986298686 ^ 2 = 9798287327554005326596

which is 24 digits long, and has a probability of less than 1/5000 of being flippably defined.

So as the search continues in higher numbers, the number of palindromes decreases, and the probability that any found palindrome's square is flippable also decreases - a double edged blade.

What's left is to find some sort of ratio of densities and accordingly see how improbable finding a solution is... Although it's clear intuitively that finding a solution gets much less likely probabilistically speaking (which by no means rules out that one or even a large number of solutions exist (possibly an infinite number?)).

Good luck! I hope someone solves this. As with many problems, the solutions are often not as simple as running the algorithm on a faster machine or with more parallelism or for a longer period of time or whatnot, but with a more advanced technique or more inventive methods of attacking the problem, which themselves further the field. The answer, a number, is of much less interest (usually) than the method used to derive it.

You are searching through all of the numbers divisible by 2011, then checking whether they are the flip of themselves. But after you've reached 7 digit numbers the condition that it be a flip of itself is more restrictive than the condition that it be divisible by 2011. So I'd suggest that you instead iterate through all of the numbers that can be constructed without the digits 3, 4, 7, then construct the number that is flip of itself prepended to itself, possibly squishing a middle digit if the middle digits are 11, 22, 55, or 88. Then test for divisibility by 2011, then test whether n*n is flippable.

Be very, very aware of the possibility that n*n will hit integer overflow. By the time you've reached a 5-digit number for the base, your n will be 9 or 10 digits long, and n*n will be 18-21 digits long.

Not necessarily a complete solution, more like thought process which may help you on the way.

1. n = flip(n) => n is a palindrome (180° rotation in flip()), n consists only of numbers which map to themselves in flip() i.e.: 0, 1, 2, 5, 8
2. flip(n*n) is defined. Thus n*n may not contain 3, 4, 7
3. n % 2011 = 0.
4. n > 0.