Hamming numbers: Difference between revisions
Content added Content deleted
Line 151: | Line 151: | ||
(cons 1 (smerge3 (map*n 2 hamming) (map*n 3 hamming) (map*n 5 hamming)))))</lang> |
(cons 1 (smerge3 (map*n 2 hamming) (map*n 3 hamming) (map*n 5 hamming)))))</lang> |
||
Note that this version uses a lot of space and time after calculating a few hundred thousand elements of the sequence. This is no doubt due to its "holding on to the head": it maintains the entire generated sequence in memory. |
Note that this version uses a lot of space and time after calculating a few hundred thousand elements of the sequence. This is no doubt due to its "holding on to the head": it maintains the entire generated sequence in memory. |
||
=={{header|D}}== |
|||
D V2 version, from the Java version. This version keeps the whole sequence in memory. |
|||
<lang d>import std.stdio: writeln; |
|||
import std.bigint: BigInt; |
|||
import std.algorithm: min, map; |
|||
import std.range: iota; |
|||
import std.array: array; |
|||
BigInt hamming(int limit) { |
|||
BigInt two = 2; |
|||
BigInt three = 3; |
|||
BigInt five = 5; |
|||
auto h = new BigInt[limit]; |
|||
h[0] = 1; |
|||
BigInt x2 = 2; |
|||
BigInt x3 = 3; |
|||
BigInt x5 = 5; |
|||
int i, j, k; |
|||
foreach (ref el; h[1 .. $]) { |
|||
el = min(x2, x3, x5); |
|||
if (x2 == el) |
|||
x2 = two * h[++i]; |
|||
if (x3 == el) |
|||
x3 = three * h[++j]; |
|||
if (x5 == el) |
|||
x5 = five * h[++k]; |
|||
} |
|||
return h[$ - 1]; |
|||
} |
|||
const(char)[] bigIntRepr(BigInt i) { |
|||
const(char)[] result; |
|||
i.toString((const(char)[] s){ result = s; }, "d"); |
|||
return result; |
|||
} |
|||
void main() { |
|||
writeln(array(map!bigIntRepr(map!hamming(iota(1, 21))))); |
|||
writeln(bigIntRepr(hamming(1691))); |
|||
writeln(bigIntRepr(hamming(1_000_000))); |
|||
}</lang> |
|||
Output: |
|||
<pre>1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 |
|||
2125764000 |
|||
519312780448388736089589843750000000000000000000000000000000000000000000000000000000</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |