Knuth's power tree: Difference between revisions
Content added Content deleted
m (added 222222 example) |
(Added Sidef) |
||
Line 557: | Line 557: | ||
power tree for 191 is: 1 2 3 5 7 14 19 38 57 95 190 191 ═══ 3^191 is: 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
power tree for 191 is: 1 2 3 5 7 14 19 38 57 95 190 191 ═══ 3^191 is: 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
||
power tree for 81 is: 1 2 3 5 10 20 40 41 81 ═══ 1.1^81 is: 2253.240236044012487937308538033349567966729852481170503814810577345406584190098644811 |
power tree for 81 is: 1 2 3 5 10 20 40 41 81 ═══ 1.1^81 is: 2253.240236044012487937308538033349567966729852481170503814810577345406584190098644811 |
||
</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|zkl}} |
|||
<lang ruby>func path(n, p = Hash(1 => 0), lvl=[[1]]) { |
|||
n || return [] |
|||
while (n !~ p) { |
|||
var q = [] |
|||
for x in lvl[0] { |
|||
for y in path(x, p, lvl) { |
|||
break if (x+y ~~ p) |
|||
y = x+y |
|||
p{y} = x |
|||
q << y |
|||
} |
|||
} |
|||
lvl[0] = q |
|||
} |
|||
path(p{n}) + [n] |
|||
} |
|||
func tree_pow(x, n) { |
|||
var r = Hash(0 => 1, 1 => x) |
|||
var p = 0 |
|||
for i in path(n) { |
|||
r{i} = (r{i-p} * r{p}) |
|||
p = i |
|||
} |
|||
r{n} |
|||
} |
|||
func show_pow(x, n) { |
|||
var fmt = ("%d: %s\n" + ["%g^%s = %f", "%s^%s = %s"][x.is_int] + "\n") |
|||
print(fmt % (n, path(n), x, n, tree_pow(x, n))) |
|||
} |
|||
for x in ^18 { show_pow(2, x) } |
|||
show_pow(1.1, 81) |
|||
show_pow(3, 191)</lang> |
|||
{{out}} |
|||
<pre style="height:32ex;overflow:scroll"> |
|||
0: [] |
|||
2^0 = 1 |
|||
1: [1] |
|||
2^1 = 2 |
|||
2: [1, 2] |
|||
2^2 = 4 |
|||
3: [1, 2, 3] |
|||
2^3 = 8 |
|||
4: [1, 2, 4] |
|||
2^4 = 16 |
|||
5: [1, 2, 4, 5] |
|||
2^5 = 32 |
|||
6: [1, 2, 4, 6] |
|||
2^6 = 64 |
|||
7: [1, 2, 4, 6, 7] |
|||
2^7 = 128 |
|||
8: [1, 2, 4, 8] |
|||
2^8 = 256 |
|||
9: [1, 2, 4, 8, 9] |
|||
2^9 = 512 |
|||
10: [1, 2, 4, 8, 10] |
|||
2^10 = 1024 |
|||
11: [1, 2, 4, 8, 10, 11] |
|||
2^11 = 2048 |
|||
12: [1, 2, 4, 8, 12] |
|||
2^12 = 4096 |
|||
13: [1, 2, 4, 8, 12, 13] |
|||
2^13 = 8192 |
|||
14: [1, 2, 4, 8, 12, 14] |
|||
2^14 = 16384 |
|||
15: [1, 2, 4, 8, 12, 14, 15] |
|||
2^15 = 32768 |
|||
16: [1, 2, 4, 8, 16] |
|||
2^16 = 65536 |
|||
17: [1, 2, 4, 8, 16, 17] |
|||
2^17 = 131072 |
|||
81: [1, 2, 4, 8, 16, 32, 64, 80, 81] |
|||
1.1^81 = 2253.240236 |
|||
191: [1, 2, 4, 8, 16, 32, 64, 128, 160, 176, 184, 188, 190, 191] |
|||
3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347 |
|||
</pre> |
</pre> |
||