Числа Цумкеллера

О них нет даже в англоязычной вики, хотя ссылки попадаются часто.

Числами Цумкеллера (Zumkeller) называются натуральные числа, делители которых (включая единицу и само число) можно разбить на два подмножества так, что суммы чисел этих подмножеств будут одинаковы, например, 12 - это число Цумкеллера, потому что множество делителей {1, 2, 3, 4, 6, 12} может быть разбито на подмножества {1, 3, 4, 6} и {2, 12} так, что суммы элементов обоих подмножеств равны 14.

В прилагаемой программке нет нормального управления оперативной памятью (функция IsZumkeller каждый раз создаёт новый динамический вектор и IsPartSum тоже, к тому же, она рекурсивна), так как цель была просто получить несколько чисел. В этом отношении код, конечно, можно доработать. Тем не менее, в конфигурации Release границу поиска до 4-5 тысяч элементов такой код должен осилить.

Впрочем, если хотим проверить конкретное число, то можно сделать функцию main вот такой

int main() {
 cout << IsZumkeller(43464);
 cin.get();
 return 0;
}

и тогда это не должно переполнять память :)

Ниже приводится листинг (запускался в консоли Visual Studio 2019), а сами числа выводить не буду, так как нашёл ссылку на таблицу с первыми 10000 чисел.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

vector <int> * GetDivisors (int n) {
 vector <int> *divs = new vector<int>;
 divs->push_back(1);
 divs->push_back(n);
 for (int i = 2; i * i <= n; i++) {
  if (n % i == 0) {
   int j = n / i;
   divs->push_back(i);
   if (i != j) divs->push_back(j);
  }
 }
 return divs;
}

bool IsPartSum (vector<int> *divs, int sum) {
 if (sum == 0) { if (divs) delete divs; return true; }
 int le = divs->size();
 if (le == 0) { return false; }
 int last = divs->at(le - 1);
 vector <int> * newDivs = new vector <int> ();
 for (int i = 0; i < le - 1; i++) {
  newDivs->push_back (divs->at(i));
 }
 if (last > sum) return IsPartSum(newDivs, sum);
 return (IsPartSum(newDivs, sum) || IsPartSum(newDivs, sum - last));
 delete newDivs;
}

bool IsZumkeller(int n) {
 vector <int> *divs = GetDivisors(n);
 int sum = accumulate(divs->begin(), divs->end(), 0);
 if (sum % 2 == 1) return false;
 if (n % 2 == 1) {
  int abundance = sum - 2 * n;
  return (abundance > 0 && abundance % 2 == 0);
 }
 bool b = IsPartSum(divs, sum / 2);
 delete divs;
 return b;
}


int main() {
 int n = 5000; //Верхняя граница поиска чисел Цумкеллера
 for (int i = 1; i <= n; i++) {
  if (IsZumkeller(i)) cout << i << " ";
 }
 cin.get();
 return 0;
}

 Первые 10000 чисел Цумкеллера, текстовый файл

12.01.2020, 14:06 [1287 просмотров]