Проблема в понимании проблемы cstutoringcenter 43 Ошибка решения

Question

Проблема: Сколько первых 100 000 000 шестиугольных чисел делится на все числа от 1 до 20?

2-е решение - простая грубая сила (работает)

 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);
 }

1-й раствор (не работает)

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);
 }

И утилит:

 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) };
 }

Что не так с первым решением? (десятичная точность?)

редактировать: Алгоритм решения 1:

1. найти наименьшее число x, равномерно делимое на все числа от 1 до 20
2. решить квадратное уравнение, полученное из формулы шестнадцатеричного числа x = n * (2 * n - 1)
3. если множитель n без остатка, увеличить счетчик
4. повторить 3. в то время как кратное n меньше 100000000-го гексагонального числа

изменить 2:

1. 232792560 // справа
2. [10788.460769248566, -10788.960769248566] // справа
3. числа, такие как 6418890, проходят тест, Google "6418890 * 10788.460769248566% 1 ="

редактировать 3:

Да, версия с использованием грубой силы должна проверять равномерное деление только простых чисел ниже 21. Но гораздо интереснее было выяснить, о чем говорил Голдберг. Я знал об этом, но больше похоже на историю пяти обезьян .

Чуть позже я подумал о округлении числа, когда вспомнил, что библиотека Math не содержит функции для этого. Но я мог бы использовать BigDecimal, и когда я посмотрел на BigDecimal и удвоил, я нашел это . Какая приятная дежавю.

А округление выглядит так:

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

Answer 1

Хотя вполне могут быть и дополнительные проблемы:

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

tmp и qes являются двойными числами, что означает, что == сравнения могут быть неудачными; см. Что должен знать каждый компьютерщик об арифметике с плавающей точкой

Answer 2

Вам, вероятно, следует сослаться на описание проблемы, чтобы люди могли знать, что такое шестиугольное число.

Также в методе грубой силы вам не нужно перепроверять общие простые множители в числе, потому что все они должны быть делимыми, поэтому они могут быть короче:

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);
}

Мне было любопытно, поэтому я рассчитал результаты:

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);
}

Метод 1 немного быстрее, чем 2, метод 4 немного быстрее, чем 3. Методы 3 или 4 быстрее, чем 1 или 2, а оригинал еще быстрее. Странно?
Добавляя h% 2 == 0 && перед всеми методами, я получаю лучшие результаты; оригинал (все та же скорость) теперь медленнее, чем все они, но в остальном ранжирование остается прежним. gcc должен оптимизировать h%2==0 для побитовой операции.

Все выводятся 59 и запускаются примерно через 2 секунды на моем портативном Core Duo 2,1 ГГц.