Duffinian numbers: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
(Added C++ solution) |
||
Line 250: | Line 250: | ||
12481 12482 12483 |
12481 12482 12483 |
||
13447 13448 13449"</lang> |
13447 13448 13449"</lang> |
||
=={{header|C++}}== |
|||
<lang cpp>#include <iomanip> |
|||
#include <iostream> |
|||
#include <numeric> |
|||
#include <sstream> |
|||
bool duffinian(int n) { |
|||
if (n == 2) |
|||
return false; |
|||
int total = 1, power = 2, m = n; |
|||
for (; (n & 1) == 0; power <<= 1, n >>= 1) |
|||
total += power; |
|||
for (int p = 3; p * p <= n; p += 2) { |
|||
int sum = 1; |
|||
for (power = p; n % p == 0; power *= p, n /= p) |
|||
sum += power; |
|||
total *= sum; |
|||
} |
|||
if (m == n) |
|||
return false; |
|||
if (n > 1) |
|||
total *= n + 1; |
|||
return std::gcd(total, m) == 1; |
|||
} |
|||
int main() { |
|||
std::cout << "First 50 Duffinian numbers:\n"; |
|||
for (int n = 1, count = 0; count < 50; ++n) { |
|||
if (duffinian(n)) |
|||
std::cout << std::setw(3) << n << (++count % 10 == 0 ? '\n' : ' '); |
|||
} |
|||
std::cout << "\nFirst 50 Duffinian triplets:\n"; |
|||
for (int n = 1, m = 0, count = 0; count < 50; ++n) { |
|||
if (duffinian(n)) |
|||
++m; |
|||
else |
|||
m = 0; |
|||
if (m == 3) { |
|||
std::ostringstream os; |
|||
os << '(' << n - 2 << ", " << n - 1 << ", " << n << ')'; |
|||
std::cout << std::left << std::setw(24) << os.str() |
|||
<< (++count % 3 == 0 ? '\n' : ' '); |
|||
} |
|||
} |
|||
std::cout << '\n'; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
First 50 Duffinian numbers: |
|||
4 8 9 16 21 25 27 32 35 36 |
|||
39 49 50 55 57 63 64 65 75 77 |
|||
81 85 93 98 100 111 115 119 121 125 |
|||
128 129 133 143 144 155 161 169 171 175 |
|||
183 185 187 189 201 203 205 209 215 217 |
|||
First 50 Duffinian triplets: |
|||
(63, 64, 65) (323, 324, 325) (511, 512, 513) |
|||
(721, 722, 723) (899, 900, 901) (1443, 1444, 1445) |
|||
(2303, 2304, 2305) (2449, 2450, 2451) (3599, 3600, 3601) |
|||
(3871, 3872, 3873) (5183, 5184, 5185) (5617, 5618, 5619) |
|||
(6049, 6050, 6051) (6399, 6400, 6401) (8449, 8450, 8451) |
|||
(10081, 10082, 10083) (10403, 10404, 10405) (11663, 11664, 11665) |
|||
(12481, 12482, 12483) (13447, 13448, 13449) (13777, 13778, 13779) |
|||
(15841, 15842, 15843) (17423, 17424, 17425) (19043, 19044, 19045) |
|||
(26911, 26912, 26913) (30275, 30276, 30277) (36863, 36864, 36865) |
|||
(42631, 42632, 42633) (46655, 46656, 46657) (47523, 47524, 47525) |
|||
(53137, 53138, 53139) (58563, 58564, 58565) (72961, 72962, 72963) |
|||
(76175, 76176, 76177) (79523, 79524, 79525) (84099, 84100, 84101) |
|||
(86527, 86528, 86529) (94177, 94178, 94179) (108899, 108900, 108901) |
|||
(121103, 121104, 121105) (125315, 125316, 125317) (128017, 128018, 128019) |
|||
(129599, 129600, 129601) (137287, 137288, 137289) (144399, 144400, 144401) |
|||
(144721, 144722, 144723) (154567, 154568, 154569) (158403, 158404, 158405) |
|||
(166463, 166464, 166465) (167041, 167042, 167043) |
|||
</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |