Perfect totient numbers: Difference between revisions
Content added Content deleted
Deadmarshal (talk | contribs) (Added Lua) |
(Added implementation in bc) |
||
Line 545: | Line 545: | ||
return phi |
return phi |
||
end function</lang> |
end function</lang> |
||
=={{header|bc}}== |
|||
<lang bc>define gcd (i, j) { |
|||
while(j != 0) { |
|||
k = j |
|||
j = i % j |
|||
i = k |
|||
} |
|||
return i |
|||
} |
|||
define is_perfect_totient (num) { |
|||
tot = 0 |
|||
for (i = 1; i < num; i++) { |
|||
if (gcd(num, i) == 1) { |
|||
tot += 1 |
|||
} |
|||
} |
|||
sum = tot + cache[tot] |
|||
cache[num] = sum |
|||
return num == sum |
|||
} |
|||
j = 1 |
|||
count = 0 |
|||
# we only go to 15 (not 20) because bc is very slow |
|||
while (count <= 15) { |
|||
if (is_perfect_totient(j)) { |
|||
print j, " " |
|||
count += 1 |
|||
} |
|||
j += 1 |
|||
} |
|||
print "\n" |
|||
quit |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
$ time bc -q perfect-totient.bc |
|||
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 |
|||
real 0m35,553s |
|||
user 0m35,437s |
|||
sys 0m0,030s |
|||
</pre> |
|||