Problem in understanding cstutoringcenter problem 43 solution bug

Question

Problem: How many of the first 100,000,000 hexagonal numbers are divisible by all the numbers from 1 through 20?

2nd solution - simple brute force (does work)

 public static void main(String[] args) {
  long hnr = 100000000L, count = 0L;

  for (long i = 1, h = getHexNr(i); i <= hnr; i++, h = getHexNr(i)) 
   if (h % 2 == 0 && h % 3 == 0 && h % 4 == 0 && h % 5 == 0
     && h % 6 == 0 && h % 7 == 0 && h % 8 == 0
     && h % 9 == 0 && h % 10 == 0 && h % 11 == 0
     && h % 12 == 0 && h % 13 == 0 && h % 14 == 0
     && h % 15 == 0 && h % 16 == 0 && h % 17 == 0
     && h % 18 == 0 && h % 19 == 0 && h % 20 == 0) count++;

  System.out.println(count);
 }

1st solution (does not work)

public static void main(String[] args) {
  long nr = 1L, hnr = 100000000L, count = 0L;
  double tmp = 0;

  for (long i = 2L; i < 21; i++)
   nr = lcm(nr, i);
  for (double qes : getQES(2, 1, -nr)) {
   if (qes < 0) continue;
   int limit = (int) (getHexNr(hnr) / Math.floor(qes));
   for (int i = 0; i < limit; i++) {
    // if ((i * qes) % 1 == 0) count++;
    if ((tmp += qes) % 1 == 0) count++;
   }
  }

  System.out.println(count);
 }

And utils:

 static long gcd(long a, long b) {
  if (b == 0) return Math.abs(a);
  return gcd(b, a % b);
 }

 static long lcm(long a, long b) {
  return (a * b) / gcd(a, b);
 }

 static long getHexNr(long n) {
  return n * (2 * n - 1);
 }

 static double[] getQES(long a, long b, long c) {
  double d = b * b - 4 * a * c;
  if (d < 0) return new double[0];
  return new double[] { (-b + Math.sqrt(d)) / (2 * a),
    (-b - Math.sqrt(d)) / (2 * a) };
 }

What is going wrong with first solution? (decimal precision?)

edit: Algorithm for solution 1:

1. find smalles number x evenly divisible by all of the numbers from 1 to 20
2. solve quadratic equation derived from hex number formula x = n * (2 * n - 1)
3. if multible of n is without residue increase count
4. repeat 3. while multiple of n is smaller then 100000000'th hexagonal number

edit 2:

1. 232792560 // right
2. [10788.460769248566, -10788.960769248566] // right
3. numbers like 6418890 are passing the test, google "6418890*10788.460769248566%1="

edit 3:

Yes, brute force version should check evenly divisibility of only primes below 21. But rather more interesting was to find out, what Goldberg talked about. I did know about it, but more of like five monkeys story.

Bit later, i thought about rounding the number, when i remembered, that Math library does not contain function to do this. But i could use BigDecimal, and when i looked up BigDecimal and double i found this. What a pleasant deja vu.

And rounding looks like:

public static double round(double d, int nr) {
 return new BigDecimal(Double.toString(d)).setScale(nr,
  BigDecimal.ROUND_HALF_UP).doubleValue();
}

Answer 1

While there may well be additional problems:

((tmp += qes) % 1 == 0)

tmp and qes are both doubles, which means == comparisons are likely to fail; see What Every Computer Scientist Should Know About Floating-Point Arithmetic

Answer 2

You should probably link to an describe the problem so that people can know what a hexagonal number is.

Also in the brute force method you don't need to recheck the common prime factors in a number because all of these must be divisible, so it can be shorter as:

public static void main(String[] args) {
  long hnr = 100000000L, count = 0L;

  for (long i = 1, h = getHexNr(i); i <= hnr; i++, h = getHexNr(i)) 
   if (h % 20 == 0 && h % 19 == 0 && h % 18 == 0 && h % 17 == 0
    && h % 16 == 0 && h % 14 == 0 && h % 13 == 0 && h % 11 == 0) count++;

  System.out.println(count);
}

I was curious, so I timed the results:

include <stdio.h>
#define H(n) (n*(2ULL*n-1ULL))
#define limit 100000000ULL
int main(int argc, char** argv){
  unsigned long long int count=0, i = 1, h = 1;
  if(argc>1&&argv[1][0]=='1'){
    for (; ++i <= limit; h = H(i)) {
     if (h % 19 == 0 && h % 17 == 0 && h % 16 == 0 && h % 13 == 0
      && h % 11 == 0 && h %  9 == 0 && h %  7 == 0 && h %  5 == 0) count++;
    }
  } else if(argc>1&&argv[1][0]=='2'){
    for (; ++i <= limit; h = H(i)) {
     if (h % 20 == 0 && h % 19 == 0 && h % 18 == 0 && h % 17 == 0
      && h % 16 == 0 && h % 14 == 0 && h % 13 == 0 && h % 11 == 0) count++;
    }
  } else if(argc>1&&argv[1][0]=='3'){
    for (; ++i <= limit; h = H(i)) {
     if (h %  5 == 0 && h %  7 == 0 && h %  9 == 0 && h % 11 == 0
      && h % 13 == 0 && h % 16 == 0 && h % 17 == 0 && h % 19 == 0) count++;
    }
  } else if(argc>1&&argv[1][0]=='4'){
    for (; ++i <= limit; h = H(i)) {
     if (h % 11 == 0 && h % 14 == 0 && h % 14 == 0 && h % 16 == 0
      && h % 17 == 0 && h % 18 == 0 && h % 19 == 0 && h % 20 == 0) count++;
    }
  } else {
    for (; ++i <= limit; h = H(i)) {
     if (h %  2 == 0 && h %  3 == 0 && h %  4 == 0 && h %  5 == 0
      && h %  6 == 0 && h %  7 == 0 && h %  8 == 0
      && h %  9 == 0 && h % 10 == 0 && h % 11 == 0
      && h % 12 == 0 && h % 13 == 0 && h % 14 == 0
      && h % 15 == 0 && h % 16 == 0 && h % 17 == 0
      && h % 18 == 0 && h % 19 == 0 && h % 20 == 0) count++;
    }
  }
  printf("%llu\n",count);
}

Method 1 is slightly faster than 2, method 4 is slightly faster than 3. Methods 3 or 4 are faster than 1 or 2, and the original is faster still. Odd?
By throwing in a h%2==0&& in front of all methods I get better results; the original (still the same speed) is now slower than all of them, but otherwise the ranking remains the same. gcc must optimize h%2==0 to be a bitwise operation.

All output 59 and run in about 2 seconds on my 2.1Ghz Core Duo portable.