Zumkeller numbers: Difference between revisions

Content added Content deleted
m (→‎{{header|Pascal}}: too much copy and paste...)
(→‎{{header|C++}}: improvements)
Line 1,536: Line 1,536:


=={{header|C++}}==
=={{header|C++}}==
<lang cpp>
<lang cpp>#include <iostream>
#include <iostream>
#include <cmath>
#include <cmath>
#include <vector>
#include <vector>
Line 1,546: Line 1,545:
using namespace std;
using namespace std;


//returns n in binary right justified with
// Returns n in binary right justified with length passed and padded with zeroes
const uint* binary(uint n, uint length);
//length passed and padded with zeroes
int* Bin(int n, int length);


//returns the the binary ordered subset of rank r.
// Returns the the binary ordered subset of rank r.
//Adapted from Sympy impementation.
// Adapted from Sympy implementation.
vector<int> subset_unrank_bin(vector<int>& d, int r);
vector<uint> subset_unrank_bin(vector<uint>& d, uint r);


vector <int> factors(int x);
vector<uint> factors(uint x);


bool isPrime(int number);
bool isPrime(uint number);


bool isZum(int n);
bool isZum(uint n);


ostream& operator<<(ostream& os, const vector<uint>& zumz) {
for (uint i = 0; i < zumz.size(); i++) {
if (i % 10 == 0)
os << endl;
os << setw(10) << zumz[i] << ' ';
}
return os;
}

int main() {
cout << "First 220 Zumkeller numbers:" << endl;
vector<uint> zumz;
for (uint n = 2; zumz.size() < 220; n++)
if (isZum(n))
zumz.push_back(n);
cout << zumz << endl << endl;


cout << "First 40 odd Zumkeller numbers:" << endl;
int main()
vector<uint> zumz2;
{
for (uint n = 2; zumz2.size() < 40; n++)
vector<int> zumz;
if (n % 2 && isZum(n))
int n = 2;
zumz2.push_back(n);
cout << "The first 220 Zumkeller numbers:\n\n";
cout << zumz2 << endl << endl;
while (zumz.size() < 220)
{
if (isZum(n))
zumz.push_back(n);
n++;
}
for (int i = 0; i < zumz.size(); i++)
{
if (i % 10 == 0)
cout << endl;
cout << setw(10) << zumz[i] << ' ';
}


cout << "\n\nFirst 40 odd Zumkeller numbers:\n\n";
cout << "First 40 odd Zumkeller numbers not ending in 5:" << endl;
vector<int> zumz2;
vector<uint> zumz3;
for (uint n = 2; zumz3.size() < 40; n++)
n = 2;
if (n % 2 && (n % 10) != 5 && isZum(n))
while (zumz2.size() < 40)
zumz3.push_back(n);
{
cout << zumz3 << endl << endl;
if (n % 2 && isZum(n))
zumz2.push_back(n);
n++;
}
for (int i = 0; i < zumz2.size(); i++)
{
if (i % 10 == 0)
cout << endl;
cout << setw(10) << zumz2[i] << ' ';
}
cout << "\n\nFirst 40 odd Zumkeller numbers not ending in 5:\n\n";
vector<int> zumz3;
n = 2;
while (zumz3.size() < 40)
{
if (n % 2 && (n % 10) != 5 && isZum(n))
{
zumz3.push_back(n);
}
n++;
}
for (int i = 0; i < zumz3.size(); i++)
{
if (i % 10 == 0)
cout << endl;
cout << setw(10) << zumz3[i] << ' ';
}


return 0;
return 0;
}
}


//returns n in binary right justified with
// Returns n in binary right justified with length passed and padded with zeroes
const uint* binary(uint n, uint length) {
//length passed and padded with zeroes
uint* bin = new uint[length]; // array to hold result
int* Bin(int n, int length)
fill(bin, bin + length, 0); // fill with zeroes
{
// convert n to binary and store right justified in bin
int* bin, rem, i = 0;
for (uint i = 0; n > 0; i++) {
uint rem = n % 2;
n /= 2;
if (rem)
bin[length - 1 - i] = 1;
}


return bin;
bin = new int[length]; //array to hold result
for (int i = 0; i < length; i++) //fill with zeroes
bin[i] = 0;
//convert n to binary and store right justified in bin
while (n > 0)
{
rem = n % 2;
n = n / 2;
if (rem)
bin[length - 1 - i] = 1;
i++;
}

return bin;
}
}


//returns the the binary ordered subset of rank r.
// Returns the sum of the binary ordered subset of rank r.
//Adapted from Sympy impementation.
// Adapted from Sympy implementation.
vector<int> subset_unrank_bin(vector<int>& d, int r)
uint sum_subset_unrank_bin(const vector<uint>& d, uint r) {
vector<uint> subset;
{
// convert r to binary array of same size as d
vector<int> subset;
const uint* bits = binary(r, d.size() - 1);
int* bits;
//convert r to binary array of same size as d
bits = Bin(r, d.size() - 1);
//get binary ordered subset
for (int i = 0; i < d.size() - 1; i++)
{
if (bits[i])
{
subset.push_back(d[i]);
}
}


return subset;
// get binary ordered subset
for (uint i = 0; i < d.size() - 1; i++)
if (bits[i])
subset.push_back(d[i]);

delete[] bits;

return accumulate(subset.begin(), subset.end(), 0u);
}
}


vector <int> factors(int x) {
vector<uint> factors(uint x) {
vector<uint> result;
// this will loop from 1 to int(sqrt(x))
for (uint i = 1; i * i <= x; i++) {
// Check if i divides x without leaving a remainder
if (x % i == 0) {
result.push_back(i);


if (x / i != i)
vector <int> result;
result.push_back(x / i);
int i = 1;
}
// This will loop from 1 to int(sqrt(x))
}
while (i * i <= x) {
// Check if i divides x without leaving a remainder
if (x % i == 0) {
result.push_back(i);


// return the sorted factors of x
if (x / i != i)
result.push_back(x / i);
sort(result.begin(), result.end());
return result;
}
i++;
}
// Return the list of factors of x
return result;
}
}


bool isPrime(int number)
bool isPrime(uint number) {
if (number < 2) return false;
{
if (number < 2) return false;
if (number == 2) return true;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (uint i = 3; i * i <= number; i += 2)
if (number % 2 == 0) return false;
for (int i = 3; (i * i) <= number; i += 2)
if (number % i == 0) return false;
if (number % i == 0) return false;


return true;
return true;
}
}


bool isZum(int n)
bool isZum(uint n) {
// if prime it ain't no zum
{
if (isPrime(n))
//if prime it ain't no zum
return false;
if (isPrime(n))
return false;


// get sum of divisors
const auto d = factors(n);
uint s = accumulate(d.begin(), d.end(), 0u);


// if sum is odd or sum < 2*n it ain't no zum
//get sum of divisors
if (s % 2 || s < 2 * n)
vector<int> d = factors(n);
return false;
sort(d.begin(), d.end());
int s = accumulate(d.begin(), d.end(), 0);


//if sum is odd or sum < 2*n it ain't no zum
// if we get here and n is odd or n has at least 24 divisors it's a zum!
if (s % 2 || s < 2 * n)
if (n % 2 || d.size() >= 24)
return false;
return true;


if (!(s % 2) && d[d.size() - 1] <= s / 2)
//if we get here and n is odd or n has at least 24 divisors it's a zum!
for (uint x = 2; (uint) log2(x) < (d.size() - 1); x++) // using log2 prevents overflow
if (n % 2 || d.size() >= 24)
if (sum_subset_unrank_bin(d, x) == s / 2)
return true;
return true; // congratulations it's a zum num!!


// if we get here it ain't no zum
if (!(s % 2) && d[d.size() - 1] <= s / 2)
return false;
{
}</lang>
//using log2 prevents overflow
for (int x = 2; (int)log2(x) < (d.size() - 1); x++)
{
vector<int> I = subset_unrank_bin(d, x);
int sum = accumulate(I.begin(), I.end(), 0);
if (sum == s / 2) //congratulations it's a zum num!!
return true;
}
}

//if we get here it ain't no zum
return false;
}

</lang>
{{out}}
{{out}}
<pre>
<pre>
The first 220 Zumkeller numbers:
First 220 Zumkeller numbers:


6 12 20 24 28 30 40 42 48 54

6 12 20 24 28 30 40 42 48 54
56 60 66 70 78 80 84 88 90 96
56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140
102 104 108 112 114 120 126 132 138 140
150 156 160 168 174 176 180 186 192 198
150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240
204 208 210 216 220 222 224 228 234 240
246 252 258 260 264 270 272 276 280 282
246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336
294 300 304 306 308 312 318 320 330 336
340 342 348 350 352 354 360 364 366 368
340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416
372 378 380 384 390 396 402 408 414 416
420 426 432 438 440 444 448 456 460 462
420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498
464 468 474 476 480 486 490 492 496 498
500 504 510 516 520 522 528 532 534 540
500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580
544 546 550 552 558 560 564 570 572 580
582 588 594 600 606 608 612 616 618 620
582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666
624 630 636 640 642 644 650 654 660 666
672 678 680 684 690 696 700 702 704 708
672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756
714 720 726 728 732 736 740 744 750 756
760 762 768 770 780 786 792 798 804 810
760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852
812 816 820 822 828 832 834 836 840 852
858 860 864 868 870 876 880 888 894 896
858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940
906 910 912 918 920 924 928 930 936 940
942 945 948 952 960 966 972 978 980 984
942 945 948 952 960 966 972 978 980 984


First 40 odd Zumkeller numbers:
First 40 odd Zumkeller numbers:


945 1575 2205 2835 3465 4095 4725 5355 5775 5985

945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305


First 40 odd Zumkeller numbers not ending in 5:
First 40 odd Zumkeller numbers not ending in 5:


81081 153153 171171 189189 207207 223839 243243 261261 279279 297297

81081 153153 171171 189189 207207 223839 243243 261261 279279 297297
351351 459459 513513 567567 621621 671517 729729 742203 783783 793611
351351 459459 513513 567567 621621 671517 729729 742203 783783 793611
812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709
812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
*/
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Zumkeller_numbers"