Carmichael lambda function: Difference between revisions
Content deleted Content added
m →{{header|Julia}}: typo |
m lamda => lambda |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 13:
;Task
* Write a function to obtain the Carmichael
* Write a function to count the number of iterations '''k''' of the '''k'''-iterated lambda function needed to get to a value of 1. Show the value of {{math | ''λ''(''n'')}} and the number of '''k'''-iterations for integers from 1 to 25.
Line 26:
:* [[wp:Carmichael_function|Wikipedia entry for Carmichael function]]
:* [[oeis:A181776|OEIS lambda(
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq''' (*)
'''Works with gojq, the Go implementation of jq''' (**)
'''Works with jaq, the Rust implementation of jq''' (***)
(*) The program seemingly made no progress after i == 12 in the second
table and was terminated.
(**) gojq's space requirements for this task beyond i == 10 in the
second table are prohibitive.
(***) The program shown below is compatible with jaq except that jaq does not
allow arrays to be grown implicitly by assignment; a simple workaround
would be to change .cache to be a JSON object. However the space
requirements effectively prevent computation of the rows in the second
table beyond the row with i == 11.
<syntaxhighlight lang="jq">
### Generic functions
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
# Emit an array of the prime factors of 'n' in order using a wheel with basis [2, 3, 5]
# e.g. 44 | primeFactors => [2,2,11]
# From https://rosettacode.org/wiki/Product_of_min_and_max_prime_factors#jq
def primeFactors:
def out($i): until (.n % $i != 0; .factors += [$i] | .n = ((.n/$i)|floor) );
if . < 2 then []
else [4, 2, 4, 2, 4, 6, 2, 6] as $inc
| { n: .,
factors: [] }
| out(2)
| out(3)
| out(5)
| .k = 7
| .i = 0
| until(.k * .k > .n;
if .n % .k == 0
then .factors += [.k]
| .n = ((.n/.k)|floor)
else .k += $inc[.i]
| .i = ((.i + 1) % 8)
end)
| if .n > 1 then .factors += [ .n ] else . end
| .factors
end;
# Define the helper function to take advantage of jq's tail-recursion optimization
def lcm($m; $n):
def _lcm:
# state is [m, n, i]
if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + $m]) | _lcm end;
[$m, $n, $m] | _lcm;
def lcm(stream):
reduce stream as $s (1; lcm(.; $s));
### Carmichael Lambda Function
def primePows:
. as $n
| { factPows: [] }
| ($n | primeFactors) as $pf
| .currFact = $pf[0]
| .count = 1
| reduce $pf[1:][] as $fact (.;
if $fact != .currFact
then .factPows += [[.currFact, .count]]
| .currFact = $fact
| .count = 1
else .count += 1
end)
| .factPows + [[.currFact, .count]] ;
def phi($p; $r):
($p | power($r-1)) * ($p - 1);
# Initial cache values
def cache: [0, 1, 1, null, 2]; # [_, 1, phi(2; 1), _, phi(2; 2)]
# input: {cache}
# output: {cache, result}
def CarmichaelHelper($p; $r):
($p|power($r)) as $n
| .cache[$n] as $cached
| if $cached then .result=$cached
else
if $p > 2
then .cache[$n] = phi($p; $r)
else .cache[$n] = phi($p; $r - 1)
end
| .result = .cache[$n]
end;
# input: {cache}
# output: {cache, result, a}
def CarmichaelLambda($n):
.cache |= (. // cache)
| .result = null
| if $n < 1 then "CarmichaelLambda: argument must be a positive integer (vs\($n))" | error
else
if .cache[$n] then .result = .cache[$n]
else ($n|primePows) as $pps
| if ($pps|length) == 1
then $pps[0][0] as $p
| $pps[0][1] as $r
| if $p > 2 then .cache[$n] = phi($p; $r)
else .cache[$n] = phi($p; $r - 1)
end
| .result = .cache[$n]
else .a = []
| reduce $pps[] as $pp (.;
CarmichaelHelper($pp[0]; $pp[1])
| .a += [ .result ] )
| .cache[$n] = lcm(.a[])
| .result = .cache[$n]
end
end
end ;
# input: {cache}
# output: {cache, result}
# Warning:.j and .k are overwritten
def iteratedToOne($j):
.k = 0
| .j = $j
| until( .j <= 1;
CarmichaelLambda(.j)
| .j = .result
| .k += 1 )
| .result = .k ;
def task1($m):
" n λ k",
"----------",
(foreach range(1; 1+$m) as $n ({};
CarmichaelLambda($n)
| .result as $lambda
| iteratedToOne($n)
| .result as $k
| .emit = "\($n|lpad(2)) \($lambda|lpad(2)) \($k|lpad(2))" )
| .emit ) ;
def task2($maxI; $maxN):
"\nIterations to 1 i lambda(i)",
"=====================================",
" 0 1 1",
( . // {}
| .cache |= (. // cache)
| .found = [true, (range(0; $maxN)|false)]
| .i=1
| .n=null
| while (.i <= $maxI and .n != $maxN;
.emit = null
| iteratedToOne(.i)
| .n = .result
| if (.found[.n]|not)
then .found[.n] = true
| CarmichaelLambda(.i)
| .result as $lambda
| .emit = "\(.n|lpad(4)) \(.i|lpad(18)) \($lambda|lpad(12))"
end
| .i += 1 )
| select(.emit).emit );
task1(25),
"",
task2(5*1e6; 15)
</syntaxhighlight>
{{output}}
<pre>
n λ k
----------
1 1 0
2 1 1
3 2 2
4 2 2
5 4 3
6 2 2
7 6 3
8 2 2
9 6 3
10 4 3
11 10 4
12 2 2
13 12 3
14 6 3
15 4 3
16 4 3
17 16 4
18 6 3
19 18 4
20 4 3
21 6 3
22 10 4
23 22 5
24 2 2
25 20 4
Iterations to 1 i lambda(i)
=====================================
0 1 1
1 2 1
2 3 2
3 5 4
4 11 10
5 23 22
6 47 46
7 283 282
8 719 718
9 1439 1438
10 2879 2878
11 34549 34548
12 138197 138196
[...terminated...]
</pre>
=={{header|Julia}}==
Line 444 ⟶ 666:
}</syntaxhighlight>
{{out}} Same as Wren example .. and it is probably 30X times slower 😅
=={{header|Sidef}}==
Built-in as '''Number#carmichael_lambda''':
<syntaxhighlight lang="ruby">func iteratedToOne(n) {
var k = 0
while (n > 1) {
n.carmichael_lambda!
++k
}
return k
}
say " n λ k"
say "----------"
for n in (1..25) {
printf("%2d %2d %2d\n", n, n.carmichael_lambda, iteratedToOne(n))
}
say "\nIterations to 1 i lambda(i)"
say "====================================="
var table = []
1..Inf -> each {|k|
var n = iteratedToOne(k)
if (!table[n]) {
table[n] = true
printf("%4s %18s %12s\n", n, k, k.carmichael_lambda)
break if (n == 15)
}
}</syntaxhighlight>
{{out}}
<pre>
n λ k
----------
1 1 0
2 1 1
3 2 2
4 2 2
5 4 3
6 2 2
7 6 3
8 2 2
9 6 3
10 4 3
11 10 4
12 2 2
13 12 3
14 6 3
15 4 3
16 4 3
17 16 4
18 6 3
19 18 4
20 4 3
21 6 3
22 10 4
23 22 5
24 2 2
25 20 4
Iterations to 1 i lambda(i)
=====================================
0 1 1
1 2 1
2 3 2
3 5 4
4 11 10
5 23 22
6 47 46
7 283 282
8 719 718
9 1439 1438
10 2879 2878
11 34549 34548
12 138197 138196
13 531441 354294
14 1594323 1062882
15 4782969 3188646
</pre>
=={{header|Wren}}==
| |||