Anonymous user
Perfect totient numbers: Difference between revisions
Added implementation in Tcl
(Added implementation in bc) |
(Added implementation in Tcl) |
||
Line 2,588:
<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>
=={{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}}==
| |||