91 lines
3.6 KiB
C#
91 lines
3.6 KiB
C#
using System;
|
|
using System.Collections;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
using System.Numerics;
|
|
|
|
static class NthHamming {
|
|
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 struct logrep {
|
|
public uint x2, x3, x5;
|
|
public double lg;
|
|
public logrep(uint x, uint y, uint z, double lg) {
|
|
this.x2 = x; this.x3 = y; this.x5 = z; this.lg = lg;
|
|
}
|
|
}
|
|
|
|
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 const double fctr = 6.0 * lb3 * lb5;
|
|
private const double crctn = 2.4534452978042592646620291867186; // Math.Log(Math.sqrt(30.0)) / Math.Log(2.0)
|
|
|
|
public static Tuple<uint, uint, uint> findNth(UInt64 n) {
|
|
if (n < 1) throw new Exception("NthHamming.findNth: argument must be > 0!");
|
|
if (n < 2) return Tuple.Create(0u, 0u, 0u); // trivial case for argument of one
|
|
var lgest = Math.Pow(fctr * (double)n, 1.0/3.0) - crctn; // from WP formula
|
|
var frctn = (n < 1000000000) ? 0.509 : 0.105;
|
|
var lghi = Math.Pow(fctr * ((double)n + frctn * lgest), 1.0/3.0) - crctn;
|
|
var lglo = 2.0 * lgest - lghi; // upper and lower bound of upper "band"
|
|
var count = 0UL; // need 64 bit precision in case...
|
|
var bnd = new List<logrep>();
|
|
for (uint k = 0, klmt = (uint)(lghi / lb5) + 1; k < klmt; ++k) {
|
|
var p = (double)k * lb5;
|
|
for (uint j = 0, jlmt = (uint)((lghi - p) / lb3) + 1; j < jlmt; ++j) {
|
|
var q = p + (double)j * lb3;
|
|
var ir = lghi - q;
|
|
var lg = q + Math.Floor(ir); // current log2 value (estimated)
|
|
count += (ulong)ir + 1;
|
|
if (lg >= lglo) bnd.Add(new logrep((UInt32)ir, j, k, lg));
|
|
}
|
|
}
|
|
if (n > count) throw new Exception("NthHamming.findNth: band high estimate is too low!");
|
|
var ndx = (int)(count - n);
|
|
if (ndx >= bnd.Count) throw new Exception("NthHamming.findNth: band low estimate is too high!");
|
|
bnd.Sort((a, b) => (b.lg < a.lg) ? -1 : 1); // sort in decending order
|
|
|
|
var rslt = bnd[ndx];
|
|
return Tuple.Create(rslt.x2, rslt.x3, rslt.x5);
|
|
}
|
|
}
|
|
|
|
class Program {
|
|
static void Main(string[] args) {
|
|
Console.WriteLine(String.Join(" ", Enumerable.Range(1,20).Select(i =>
|
|
NthHamming.trival(NthHamming.findNth((ulong)i))).ToArray()));
|
|
Console.WriteLine(NthHamming.trival((new HammingsLogArr()).ElementAt(1691 - 1)));
|
|
|
|
var n = 1000000000000UL;
|
|
var elpsd = -DateTime.Now.Ticks;
|
|
|
|
var rslt = NthHamming.findNth(n);
|
|
|
|
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();
|
|
}
|
|
}
|