92 lines
3.4 KiB
C#
92 lines
3.4 KiB
C#
using System;
|
|
using System.Collections;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
using System.Numerics;
|
|
|
|
class HammingsLogArr : IEnumerable<Tuple<uint, uint, uint>> {
|
|
public static BigInteger trival(Tuple<uint, uint, uint> tpl) {
|
|
BigInteger rslt = 1;
|
|
for (var i = 0; i < tpl.Item1; ++i) rslt *= 2;
|
|
for (var i = 0; i < tpl.Item2; ++i) rslt *= 3;
|
|
for (var i = 0; i < tpl.Item3; ++i) rslt *= 5;
|
|
return rslt;
|
|
}
|
|
private const double lb3 = 1.5849625007211561814537389439478; // Math.Log(3) / Math.Log(2);
|
|
private const double lb5 = 2.3219280948873623478703194294894; // Math.Log(5) / Math.Log(2);
|
|
private struct logrep {
|
|
public double lg;
|
|
public uint x2, x3, x5;
|
|
public logrep(double lg, uint x, uint y, uint z) {
|
|
this.lg = lg; this.x2 = x; this.x3 = y; this.x5 = z;
|
|
}
|
|
public logrep mul2() {
|
|
return new logrep (this.lg + 1.0, this.x2 + 1, this.x3, this.x5);
|
|
}
|
|
public logrep mul3() {
|
|
return new logrep(this.lg + lb3, this.x2, this.x3 + 1, this.x5);
|
|
}
|
|
public logrep mul5() {
|
|
return new logrep(this.lg + lb5, this.x2, this.x3, this.x5 + 1);
|
|
}
|
|
}
|
|
public IEnumerator<Tuple<uint, uint, uint>> GetEnumerator() {
|
|
var one = new logrep();
|
|
var s2 = new List<logrep>(); var s3 = new List<logrep>();
|
|
s2.Add(one); s3.Add(one.mul3());
|
|
var s5 = one.mul5(); var mrg = one.mul3();
|
|
var s2hdi = 0; var s3hdi = 0;
|
|
while (true) {
|
|
if (s2hdi >= s2.Count) { s2.RemoveRange(0, s2hdi); s2hdi = 0; } // assume capacity stays the same...
|
|
var v = s2[s2hdi];
|
|
if ( v.lg < mrg.lg) { s2.Add(v.mul2()); s2hdi++; }
|
|
else {
|
|
if (s3hdi >= s3.Count) { s3.RemoveRange(0, s3hdi); s3hdi = 0; }
|
|
v = mrg; s2.Add(v.mul2()); s3.Add(v.mul3());
|
|
s3hdi++; var chkv = s3[s3hdi];
|
|
if (chkv.lg < s5.lg) { mrg = chkv; }
|
|
else { mrg = s5; s5 = s5.mul5(); s3hdi--; }
|
|
}
|
|
yield return Tuple.Create(v.x2, v.x3, v.x5);
|
|
}
|
|
}
|
|
IEnumerator IEnumerable.GetEnumerator() {
|
|
return this.GetEnumerator();
|
|
}
|
|
}
|
|
|
|
class Program {
|
|
static void Main(string[] args) {
|
|
Console.WriteLine(String.Join(" ", (new HammingsLogArr()).Take(20)
|
|
.Select(t => HammingsLogArr.trival(t))
|
|
.ToArray()));
|
|
Console.WriteLine(HammingsLogArr.trival((new HammingsLogArr()).ElementAt((int)1691 - 1)));
|
|
|
|
var n = 1000000UL;
|
|
var elpsd = -DateTime.Now.Ticks;
|
|
|
|
var rslt = (new HammingsLogArr()).ElementAt((int)n - 1);
|
|
|
|
elpsd += DateTime.Now.Ticks;
|
|
|
|
Console.WriteLine("2^{0} times 3^{1} times 5^{2}", rslt.Item1, rslt.Item2, rslt.Item3);
|
|
var lgrthm = Math.Log10(2.0) * ((double)rslt.Item1 +
|
|
((double)rslt.Item2 * Math.Log(3.0) + (double)rslt.Item3 * Math.Log(5.0)) / Math.Log(2.0));
|
|
var pwr = Math.Floor(lgrthm); var mntsa = Math.Pow(10.0, lgrthm - pwr);
|
|
Console.WriteLine("Approximately: {0}E+{1}", mntsa, pwr);
|
|
var s = HammingsLogArr.trival(rslt).ToString();
|
|
var lngth = s.Length;
|
|
Console.WriteLine("Decimal digits: {0}", lngth);
|
|
if (lngth <= 10000) {
|
|
var i = 0;
|
|
for (; i < lngth - 100; i += 100) Console.WriteLine(s.Substring(i, 100));
|
|
Console.WriteLine(s.Substring(i));
|
|
}
|
|
Console.WriteLine("The {0}th hamming number took {1} milliseconds", n, elpsd / 10000);
|
|
|
|
Console.Write("\r\nPress any key to exit:");
|
|
Console.ReadKey(true);
|
|
Console.WriteLine();
|
|
}
|
|
}
|