Thoughts and examples of java implementation of 4 digit vampire numbers

This problem comes from Java programming thought book 1. The so-called "vampire number" refers to even-digit numbers, which can be obtained by multiplying a pair of numbers, and each pair of numbers contains a half-digit number of product, in which the numbers selected from even-digit numbers can be arranged arbitrarily. For example:

1260=21*60, 1827=21*87, 2187=27*81...

List the results first:

1 A total of 7:

1260=21*60, 1395=15*93, 1435=41*35, 1530=51*30, 1827=87*21, 2187=27*81, 6880=86*80

The first idea is to enumerate all the four digits, assuming that these four digits are abcd, which can be expressed as 1000a + 100b + 10c + d. Then there are 12 combinations of 2 digits extracted from this 4 digits (abcd is 0-9 respectively, which can be used as X, and the numbers on 10 digits of Y must be 1-9):

① X=10*a + b, Y=10*c + d--Impossible ② X=10*a + b, Y=10*d + c--Impossible ③ X=10*a + c, Y=10*b + d--Impossible ④ X=10*a + c, Y=10*d + b--Impossible ⑤ X=10*a + d, Y=10*b + c--Impossible ⑥ X=10*a + d, Y=10*c + b ⑦ X=10*b + a, Y=10*c + d 8 X=10*b + a, Y=10*d + c Pet-name ruby X=10*b + c, Y=10*d + a-impossible Attending X=10*b + d, Y=10*c + a 12. X=10*c + a, Y=10*d + b X=10*c + b, Y=10*d + a

Is it possible that some of these 12 combinations are impossible to satisfy 1000a+100b+10c+d=X*Y? If it can be removed directly, unnecessary calculations can be reduced.

Assuming that ① might find a matching vampire number, there is an equation: (10*a + b) * (10*c + d) = 1000a + 100b + 10c + d = 100* (10*a + b) + 10*c + d
< = > (10*a + b)*(10*c + d - 100) = 10*c + d

Because the left side (10*c + d-100) is a negative number and the right side is a positive number, it cannot be equal; Because c/d are interchangeable in the above formula, it is impossible to find the number of vampires through ① ②.

Assuming that it is possible to find a matching vampire number, there is an equation: (10*a + c) * (10*b + d) = 1000a + 100b + 10c + d
< = > 100*a*b + 10*(a*d+b*c) + cd = 100*a*b - 100*a*b + 1000*a + 100*b + 10*c +d = 100*a*b + 10*[10*a*(10-b) + 10*b] + 10*c +d
< = > 10*(a*d+b*c) + cd = 10*[10*a*(10-b) + 10*b] + 10*c +d

Because the children on both sides have a*d < 10*a* (10-b), b*c < 10*b, cd < 10*c + d, so the right side is always greater than the left side; Because of the interchangeability of b/d in the above formula, it is impossible to find the number of vampires through ③ ④.

Assuming that the combination of 10*b + c can find the vampire number, there is an equation: (10*a + d) * (10*b + c) = 1000*a + 10* (10*b + c) + d
< = > (10*b + c)*(10*a + d - 10) = 1000*a + d = 100*(10a + d/100)

Because left (10*b + c) < 100, (10*a + d-10) < (10a + d/100), so the right side is always greater than the left side; Because a/d are interchangeable in the above formula, it is impossible to find the number of vampires through ⑤ Pet-name ruby.

The other four digits containing two or more zeros can not be vampire numbers, because if they contain two zeros, they can only be split out in the form of 10*a and 10*b, and the last two digits of the product must be in the form of ZZ00; Then the equation degenerates to a*b=10*a+b and transforms to b=10*a/a-1) > 10, while b cannot be greater than 10.

The implementation code is as follows:

/**
 * VampireNumbers<br />
 *  Seek all 4 Bit vampire number 
 * @author South Park
 */
public final class VampireNumbers {
 private static final StringBuilder outputStr = new StringBuilder(14);
 private static final String equalSign = " = ";
 private static final String multiSign = " * ";
 /**
 *  If these two 2 If the product of digits is equal to the original number, it will be successful and the number will be printed 
 * @param i 4 The value of bits 
 * @param m  Among them 1 A 2 Number of digits 
 * @param n  In addition 1 A 2 Number of digits 
 */
 private static final void productTest (final int i, final int m, final int n) {
 //  If the condition is met, the output 
 if(m * n == i) {
  outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);
  System.out.println(outputStr.toString());
  outputStr.delete(0, 14);
 }
 }
 /**
 *  From 1011 Begin to 9998 Loop through every 4 Various splitting combinations of digits 
 * @param args
 */
 public static void main(String[] args) {
 int count = 0;//  Count the number of cycles 
 long startTime = System.nanoTime();
 //  Respectively represent thousands 10 Ladies and gentlemen 
 int a,b,c,d;
 // 4 Number of digits containing zeros 
 int zeroCount = 0;
 for(short i = 1011; i < 9999; i++) {
  zeroCount = 0;
  String value = ""+i;
  //  Get the value in each bit (0-9)
  a = value.charAt(0) - 48;// Thousand digits 
  b = value.charAt(1) - 48;// Hundred digits 
  c = value.charAt(2) - 48;//10 Bit 
  d = value.charAt(3) - 48;// Individual position 
  if (b == 0) 
  zeroCount++;
  if (c == 0)
  zeroCount++;
  if (d == 0)
  zeroCount++;
  //  The numbers contain 2 More than zero exclusion 
  if (zeroCount >= 2) {
  continue;
  }
  count++;
  //productTest(i, 10*a + b, 10*c + d);
  //productTest(i, 10*a + b, 10*d + c);
  //productTest(i, 10*a + c, 10*b + d);
  //productTest(i, 10*a + c, 10*d + b);
  //productTest(i, 10*a + d, 10*b + c);
  productTest(i, 10*a + d, 10*c + b);
  productTest(i, 10*b + a, 10*c + d);
  productTest(i, 10*b + a, 10*d + c);
  //productTest(i, 10*b + c, 10*d + a);
  productTest(i, 10*b + d, 10*c + a);
  productTest(i, 10*c + a, 10*d + b);
  productTest(i, 10*c + b, 10*d + a);
 }
 System.out.println(System.nanoTime() - startTime);
 //  Number of output cycles 
 System.out.println("loop count:" + count);
 }
}

Output:

1260 = 21 * 60
1395 = 15 * 93
1435 = 41 * 35
1530 = 51 * 30
1827 = 87 * 21
2187 = 27 * 81
6880 = 86 * 80
6880 = 80 * 86
12360961
loop count:8747

The second way is to start with a pair of XY after decomposition, and carry out double cycle exhaustion from 10 to 99. Because the product result must be 4 digits, that is, the range is 1000 to 9999, the range of the second layer cycle can be limited to reduce the number of cycles. From the results, the second way has fewer cycles and less time.

For 4-bit vampire numbers, X*Y-X-Y must be a multiple of 9, because X*Y-X-Y has only six results:

9*(110*a + 11*b) 9*(110*a + 10*b + c) 9*(110*a + 11*b + c - d) 9*(111*a + 10*b) 9*(111*a + 11*b - d) 9*(111*a + 10*b + c - d)

Code implementation:

import java.util.Arrays;
/**
 * VampireNumbers2<br />
 *  Seek all 4 Bit vampire number 
 * @author South Park
 */
public final class VampireNumbers2 {
 private static final StringBuilder outputStr = new StringBuilder(14);
 private static final String equalSign = " = ";
 private static final String multiSign = " * ";
 /**
 *  If these two 2 If the product of digits is equal to the original number, it will be successful and the number will be printed 
 * @param i 4 The value of bits 
 * @param m  Among them 1 A 2 Number of digits 
 * @param n  In addition 1 A 2 Number of digits 
 */
 private static final void printVN (final int i, final int m, final int n) {
 outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);
 System.out.println(outputStr.toString());
 outputStr.delete(0, 14);
 }
 /**
 *  From 11 Begin to 99 A double loop attempts each combination of 4 Does the number product result exactly contain the original two 2 A number of digits 
 * @param args
 */
 public static void main(String[] arg) {
 int count = 0;//  Count the number of cycles 
 long startTime = System.nanoTime();
 String vnValueStr = "";
 String multiValueStr = "";
 char[] vnValueArr = new char[4];
 char[] multiValueArr = new char[4];
 int from;
 int to;
 int vampireNumbers;
 //  Double cycle exhaustion 
 for (int i = 11; i < 100; i++) {
  //  Through the from And to The calculation of, reduce the number 2 The number of re-cycles; j=i+1 Avoid repetition 
  from = Math.max(1000 / i + 1, i + 1);
  to = Math.min(10000 / i, 100);
  for (int j = from; j < to; j++) {
  count++;
  vampireNumbers = i * j;
  //  Filter out the number of non-vampires 
  if ((vampireNumbers - i - j) % 9 != 0) {
   continue;
  }
  vnValueStr = "" + vampireNumbers;
  vnValueArr[0] = vnValueStr.charAt(0);
  vnValueArr[1] = vnValueStr.charAt(1);
  vnValueArr[2] = vnValueStr.charAt(2);
  vnValueArr[3] = vnValueStr.charAt(3);
  multiValueStr = "" + i + j;
  multiValueArr[0] = multiValueStr.charAt(0);
  multiValueArr[1] = multiValueStr.charAt(1);
  multiValueArr[2] = multiValueStr.charAt(2);
  multiValueArr[3] = multiValueStr.charAt(3);
  Arrays.sort(vnValueArr);
  Arrays.sort(multiValueArr);
  if (Arrays.equals(vnValueArr, multiValueArr)) {//  Compare after sorting , If it is true, find it 1 Number of vampires 
   printVN(vampireNumbers, i, j);
  }
  }
 }
 System.out.println(System.nanoTime() - startTime);
 //  Number of output cycles 
 System.out.println(count);
 }
}

Output:

1395 = 15 * 93
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
1530 = 30 * 51
1435 = 35 * 41
6880 = 80 * 86
3024115
3269

Because the mechanism of vampire number has not been found, we have to use exhaustive method. The main way to improve performance here is to reduce the number of cycles and unnecessary calculations.

Summarize