Perfect totient numbers: Difference between revisions
Content added Content deleted
(Added implementation in bc) |
(Added implementation in Tcl) |
||
| Line 2,588: | Line 2,588: | ||
<pre>The first 20 perfect totient numbers are: |
<pre>The first 20 perfect totient numbers are: |
||
[3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571]</pre> |
[3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571]</pre> |
||
=={{header|Tcl}}== |
|||
<lang tcl>array set cache {} |
|||
set cache(0) 0 |
|||
proc gcd {i j} { |
|||
while {$j != 0} { |
|||
set t [expr {$i % $j}] |
|||
set i $j |
|||
set j $t |
|||
} |
|||
return $i |
|||
} |
|||
proc is_perfect_totient {n} { |
|||
global cache |
|||
set tot 0 |
|||
for {set i 1} {$i < $n} {incr i} { |
|||
if [ expr [gcd $i $n] == 1 ] { |
|||
incr tot |
|||
} |
|||
} |
|||
set sum [expr $tot + $cache($tot)] |
|||
set cache($n) $sum |
|||
return [ expr $n == $sum ? 1 : 0] |
|||
} |
|||
set i 1 |
|||
set count 0 |
|||
while { $count < 20 } { |
|||
if [ is_perfect_totient $i ] { |
|||
puts -nonewline "${i} " |
|||
incr count |
|||
} |
|||
incr i |
|||
} |
|||
puts "" |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
$ time tclsh perfect-totient.tcl |
|||
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571 |
|||
real 1m18,058s |
|||
user 1m17,593s |
|||
sys 0m0,046s |
|||
</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||