Числа Цумкеллера
О них нет даже в англоязычной вики, хотя ссылки попадаются часто.
Числами Цумкеллера (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 [1288 просмотров]