Hamming numbers: Difference between revisions

'''[[wp:Hamming numbers|Hamming numbers]]''' are numbers of the form  

 

''Hamming numbers''   are also known as   ''ugly numbers''   and also   ''5-smooth numbers''   (numbers whose prime divisors are less or equal to 5).

# Show the   1691^st   Hamming number (the last one below   2³¹).

# Show the   one million^th   Hamming number (if the language – or a convenient library – supports arbitrary-precision integers).

 

 

;References:

* [http://dobbscodetalk.com/index.php?option=com_content&task=view&id=913&Itemid=85 Hamming problem] from Dr. Dobb's CodeTalk (dead link as of Sep 2011; parts of the thread [http://drdobbs.com/blogs/architecture-and-design/228700538 here] and [http://www.jsoftware.com/jwiki/Essays/Hamming%20Number here]).

<br><br>

 

=={{header|Ada}}==

{{works with|GNAT}}

 

 

 

 

procedure Hamming is

generic

 

begin

end loop;

end loop;

end loop;

 

 

begin

end loop;

 

 

=={{header|ALGOL 68}}==

{{works with|Algol 68 Genie 1.19.0}}

Hamming numbers are generated in a trivial iterative way as in the Python version below. This program keeps the series needed to generate the numbers as short as possible using flexible rows; on the downside, it spends considerable time on garbage collection.

 

MODE SERIES = FLEX [1 : 0] UNT, # Initially, no elements #

OD;

print ((newline, whole (hamming number (1 691), 0)));

{{out}}

<pre>

519312780448388736089589843750000000000000000000000000000000000000000000000000000000

</pre>

 

=={{header|ATS}}==

//

// How to compile:

//

} (* end of [main0] *)

{{out}}

<pre>

 

=={{header|AutoHotkey}}==

Msgbox % hamming(1,20)

Msgbox % hamming(1690)

 

return Output

 

=={{header|AWK}}==

BEGIN {

for (i=1; i<=20; i++) {

}

printf("\n1691: %d\n",hamming(1691))

exit(0)

}

return((x < y) ? x : y)

}

{{out}}

<pre>

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

1691: 2125764000

</pre>

 

=={{header|BBC BASIC}}==

FOR h% = 1 TO 20

PRINT "H("; h% ") = "; FNhamming(h%)

IF m = x5 k% += 1 : x5 = 5 * h%(k%)

NEXT

{{out}}

<pre>

H(20) = 36

H(1691) = 2125764000

</pre>

 

=={{header|Bracmat}}==

{{trans|D}}

= x2 x3 x5 n i j k min

. tbl$(h,!arg) { This creates an array. Arrays are always global in Bracmat. }

& out$(hamming$1691)

& out$(hamming$1000000)

{{out}}

<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|C}}==

Using a min-heap to keep track of numbers. Does not handle big integers.

#include <stdlib.h>

 

/* free(q); */

return 0;

===Alternative===

Standard algorithm. Numbers are stored as exponents of factors instead of big integers, while GMP is only used for display. It's much more efficient this way.

#include <stdlib.h>

#include <string.h>

printf("10,000,000: "); show_ham(get_ham(1e7));

return 0;

{{out}}

<pre> 1,691: 2125764000

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Numerics;

using System.Linq;

}

}

{{out}}

<pre>1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

===Generic version for any set of numbers===

The algorithm is similar to the one above.

using System.Numerics;

using System.Linq;

}

}

 

{{out}}

--Mike Lorenz

 

using System.Linq;

using System.Numerics;

}

}

 

{{out}}

I wanted to fix the enumerator (old) version, as it wasn't working. It became a bit of an obsession... after a few iterations I came up with the following, which is the fastest C# version on my computer - your mileage may vary. It combines the speed of the Log method; Log(2)+Log(3)=Log(2*3) to help determine which is the next one to use. Then I have added some logic (using the series property) to ensure that exponent sets are never duplicated - which speeds the calculations up a bit.... Adding this trick to the Fast Version will probably result in the fastest version, but I'll leave that to someone else to implement. Finally it's all enumerated through a crazy one-way-linked-list-type-structure that only exists as long as the enumerator and is left up to the garbage collector to remove the bits no longer needed... I hope it's commented enough... follow it if you dare!

 

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre>5-Smooth:

It also shows that one can use somewhat functional programming techniques in C#.

 

 

{{trans|Haskell}}

using System.Collections;

using System.Collections.Generic;

}

}

 

===Fast enumerating logarithmic version===

The following code eliminates or reduces all of those problems by being non-generic, eliminating duplicate calculations, saving memory by "draining" the growable List's used in blocks as back pointer indexes are used (thus using memory at the same rate as the functional version), thus avoiding excessive allocations/garbage collections; it also is enumerates through the Hamming numbers although that comes at a slight cost in overhead function calls:

{{trans|Nim}}

using System.Collections;

using System.Collections.Generic;

private const double lb5 = 2.3219280948873623478703194294894; // Math.Log(5) / Math.Log(2);

private struct logrep {

public uint x2, x3, x5;

}

public logrep mul2() {

}

public logrep mul3() {

}

public logrep mul5() {

}

}

public IEnumerator<Tuple<uint, uint, uint>> GetEnumerator() {

var one = new logrep();

while (true) {

else {

}

}

}

.Select(t => HammingsLogArr.trival(t))

.ToArray()));

 

var n = 1000000UL;

Console.WriteLine();

}

{{output}}

<pre>1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

The above code is about as fast as one can go generating sequences; however, if one is willing to forego sequences and just calculate the nth Hamming number (again), then some reading on the relationship between the size of numbers to the sequence numbers is helpful (Wikipedia: regular number). One finds that there is a very distinct relationship and that it quite quickly reduces to quite a small error band proportional to the log of the output value for larger ranges. Thus, the following code just scans for logarithmic representations to insert into a sequence for this top error band and extracts the correct nth representation from that band. It reduces time complexity to O(n^(2/3)) from O(n) for the sequence versions, but even more amazingly, reduces memory requirements to O(n^(1/3)) from O(n^(2/3)) and thus makes it possible to calculate very large values in the sequence on common personal computers. The code is as follows:

{{trans|Nim}}

using System.Collections;

using System.Collections.Generic;

Console.WriteLine();

}

 

The output is the same as above except that the time is too small to be measured. The billionth number in the sequence can be calculated in just about 10 milliseconds, the trillionth in about one second, the thousand trillionth in about a hundred seconds, and it should be possible to calculate the 10^19th value in less than a day (untested) on common personal computers. The (2^64 - 1)th value (18446744073709551615) cannot be calculated due to a slight overflow problem as it approaches that limit.

=={{header|C++}}==

===C++11 For Each Generator===

#include <iostream>

#include <vector>

}

};

 

===5-Smooth===

int main() {

int count = 1;

return 0;

}

Produces:

<pre>

 

===7-Smooth===

int main() {

int count = 1;

return 0;

}

Produces:

<pre>

1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100 105 108 112 120 125 126 128 135 140 144 147 150 160 162 168 175 180 189

</pre>

 

=={{header|Clojure}}==

This version implements Dijkstra's merge solution, so is closely related to the Haskell version.

(lazy-seq

(let [x (first xs),

(smerge (map #(*' 3 %) hamming))

(smerge (map #(*' 2 %) hamming))

Note that the above version uses a lot of space and time after calculating a few hundred thousand elements of the sequence. This is no doubt due to not avoiding the generation of duplicates in the sequences as well as its "holding on to the head": it maintains the entire generated sequences in memory.

 

In order to fix the problems with the above program as to memory use and extra time expended, the following code implements the Haskell idea as a function so that it does not retain the pointers to the streams used so that they can be garbage collected from the beginning as they are consumed. it avoids duplicate number generation by using intermediate streams for each of the multiples and building each on the results of the last; also, it orders the streams from least dense to most so that the intermediate streams retained are as short as possible, with the "s5" stream only from one fifth to a third of the current value, the "s35" stream only between a third and a half of the current output value, and the s235 stream only between a half and the current output - as the sequence is not very dense with increasing range, mot many values need be retained:

{{trans|Haskell}}

"Computes the unbounded sequence of Hamming 235 numbers."

[]

(u [s n] (let [r (atom nil)]

(reset! r (merge s (smult n (cons 1 (lazy-seq @r)))))))]

 

 

After compiling code in REPL:

519312780448388736089589843750000000000000000000000000000000000000000000000000000000N

</pre>

 

=={{header|CoffeeScript}}==

# property that they don't evenly divide any prime numbers outside

# a given set, such as [2, 3, 5].

numbers = generate_hamming_sequence(primes, 10000)

console.log numbers[1690]

 

=={{header|Common Lisp}}==

Maintaining three queues, popping the smallest value every time.

(let ((x (apply #'min (map 'list #'first seqs))))

(loop for s in seqs

(if (or (< n 21)

(= n 1691)

A much faster method:

(let ((fac '(2 3 5))

(idx (make-array 3 :initial-element 0))

 

(loop for i in '(1691 1000000) do

{{out}}

<pre> 1: 1

1691: 2125764000

1000000: 519312780448388736089589843750000000000000000000000000000000000000000000000000000000</pre>

 

=={{header|D}}==

===Basic Version===

This version keeps all numbers in memory, computing all the Hamming numbers up to the needed one. Performs constant number of operations per Hamming number produced.

 

auto hamming(in uint n) pure nothrow /*@safe*/ {

1_691.hamming.writeln;

1_000_000.hamming.writeln;

{{out}}

<pre>[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]

This keeps <math>O(n^{2/3})</math> numbers in memory, but over-computes a sequence by a factor of about <math>\Theta(n^{2/3})</math>, calculating extra multiples past that as well. Incurs an extra <math>O(\log n)</math> factor of operations per each number produced (reinserting its multiples into a tree). Doesn't stop when the target number is reached, instead continuing until it is no longer needed:

{{trans|Java}}

core.memory;

 

writeln("hamming(1691) = ", 1691.hamming);

writeln("hamming(1_000_000) = ", 1_000_000.hamming);

{{out}}

<pre>First 20 Hamming numbers: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]

Does exactly what the first version does, creating an array and filling it with Hamming numbers, keeping the three back pointers into the sequence for next multiples calculations, except that it represents the numbers as their coefficients triples and their logarithm values (for comparisons), thus saving on BigInt calculations.

{{trans|C}}

import std.bigint: BigInt;

import std.conv: text;

foreach (immutable n; [1691, 10 ^^ 6, MAX_HAM])

writefln("%8d: %s", n, n.getHam);

The output is similar to the second C version.

Runtime is about 0.11 seconds if MAX_HAM = 1_000_000 (as the task requires),

It's a little slower than the precedent version, but it uses much less RAM,

so it allows to compute the result for larger n.

import std.bigint: BigInt;

import std.conv: text;

foreach (immutable n; [1691, 10 ^^ 6, 10_000_000])

writefln("%8d: %s", n, n.getHam);

The output is the same as the second alternative version.

 

=={{header|DCL}}==

$

$ n = 0

$

$ n = limit - 1

{{out}}

<pre>

32

36

2125764000

</pre>

 

=={{header|Eiffel}}==

note

description : "Initial part, in order, of the sequence of Hamming numbers"

]"

warning : "[

`note' and other newer keywords not supported, red color for manifest strings.

This should be fixed soon.

end

end

 

{{out}}

 

=={{header|Elixir}}==

def generater do

queues = [{2, queue}, {3, queue}, {5, queue}]

IO.puts Hamming.generater |> Enum.take(1691) |> List.last

IO.puts "one millionth Hamming number:"

 

{{out}}

519312780448388736089589843750000000000000000000000000000000000000000000000000000000

</pre>

 

=={{header|ERRE}}==

For bigger numbers, you have to use an external program, like MULPREC.R

 

!$DOUBLE

HAMMING(1691->RES)

PRINT("H(1691)=";RES)

{{out}}<pre>H( 1 )= 1

H( 2 )= 2

</pre>

 

This version implements Dijkstra's merge solution, so is closely related to the Haskell classic version.

 

let rec (-|-) (Cons(x, nxf) as xs) (Cons(y, nyf) as ys) =

let rec inf_map f (Cons(x, nxf)) =

Cons(1I, lazy(let x = inf_map ((*) 2I) hamming

let y = inf_map ((*) 3I) hamming

let main args =

let rec iterLazyListFor f n (Cons(v, rf)) =

let rec nthLazyList n ((Cons(v, rf)) as ll) =

 

The above code memory residency is quite high as it holds the entire lazy sequence in memory due to the reference preventing garbage collection as the sequence is consumed,

The following code reduces that high memory residency by making the routine a function and using internal local stream references for the intermediate streams so that they can be collected as the stream is consumed as long as no reference is held to the main results stream (which is not in the sample test functions); it also avoids duplication of factors by successively building up streams and further reduces memory use by ordering of the streams so that the least dense are determined first:

{{trans|Haskell}}

 

let rec merge (Cons(x, f) as xs) (Cons(y, g) as ys) =

if x < y then Cons(x, lazy(merge (f.Force()) ys))

let rec smult m (Cons(x, rxs)) =

Cons(m * x, lazy(smult m (rxs.Force())))

let u s n =

 

 

Both codes output the same results as follows but the second is over three times faster:

2125764000

519312780448388736089589843750000000000000000000000000000000000000000000000000000000

 

 

===Fast somewhat imperative sequence version using logarithms===

 

 

 

let hammingsLog() = // imperative arrays, eliminates the BigInteger operations...

 

if n <= 0u then rslt

 

[<EntryPoint>]

let main argv =

let strt = System.DateTime.Now.Ticks

 

let stop = System.DateTime.Now.Ticks

 

printfn ""

 

 

===Extremely fast non-enumerating version sorting values in error band===

If one is willing to forego sequences and just calculate the nth Hamming number, then some reading on the relationship between the size of numbers to the sequence numbers is helpful (Wikipedia: regular number). One finds that there is a very distinct relationship and that it quite quickly reduces to quite a small error band proportional to the log of the output value for larger ranges. Thus, the following code just scans for logarithmic representations to insert into a sequence for this top error band and extracts the correct nth representation from that band. It reduces time complexity to O(n^(2/3)) from O(n) for the sequence versions, but even more amazingly, reduces memory requirements to O(n^(1/3)) from O(n^(2/3)) and thus makes it possible to calculate very large values in the sequence on common personal computers. The code is as follows:

{{trans|Haskell}}

if n < 1UL then failwith "nthHamming; argument must be > 0!"

if n < 2UL then 0u, 0u, 0u else // trivial case for first value of one

let fctr = 6.0 * lb3 * lb5

let crctn = 2.4534452978042592646620291867186 // Math.Log(Math.sqrt(30.0)) / Math.Log(2.0)

let rec loopk k kcnt kbnd =

let rec loopj j jcnt jbnd =

let count, bnd = loopk 0u 0UL [] // 64-bit value so doesn't overflow

if n > count then failwith "nthHamming: band high estimate is too low!"

System.Console.ReadKey(true) |> ignore

printfn ""

{{output}}

<pre>( 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 )

 

It takes too short a time to be measured to calculate the millionth Hamming number, the billionth number in the sequence can be calculated in just about 15 milliseconds, the trillionth in about one second, the thousand trillionth in about a hundred seconds, and it should be possible to calculate the 10^19th value in less than a day (untested) on common personal computers. The (2^64 - 1)th value (18446744073709551615) cannot be calculated due to a slight overflow problem as it approaches that limit.

 

=={{header|Factor}}==

{{trans|Scala}}

;

IN: rosetta.hamming

 

: nth-from-now ( hamming-iterator n -- m )

 

<hamming-iterator> 20 next-n .

 

{{trans|Haskell}}

IN: rosetta.hamming-lazy

 

h 2 3 5 [ '[ _ * ] lazy-map ] tri-curry@ tri

sort-merge sort-merge

 

20 hamming ltake list>array .

64-bit cell represents a number 2^l*3^m*5^n, where l, n, and m are

bitfields in the cell (20 bits for now). It also uses a fixed-point logarithm to compare the Hamming numbers and prints them in factored form. This code has been tested up to the 10^9th Hamming number.

 

: extract2 ( h -- l )

20 .nseq

cr 1691 nthseq h.

{{out}}

<pre>

</pre>

A smaller, less capable solution is presented here. It solves two out of three requirements and is ANS-Forth compliant.

create hamming /hamming allot

( n1 n2 n3 n4 n5 n6 n7 -- n3 n4 n5 n6 n1 n2 n8)

cr 21 1 ?do i . i hamming# . cr loop

1691 hamming# . cr

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

Using big_integer_module from here [http://fortran.com/big_integer_module.f95]

use big_integer_module

implicit none

end if

end function mini

{{out}}

<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|FunL}}==

{{trans|Scala}}

 

val hamming =

for q <- [q2, q3, q5] do q.enqueue( 1 )

 

{{trans|Haskell}}

 

def

println( hamming.take(20) )

println( hamming(1690) )

 

{{out}}

8100000000

</pre>

 

=={{header|Go}}==

===Concise version using dynamic-programming===

 

import (

fmt.Println(h[1691-1])

fmt.Println(h[len(h)-1])

{{out}}

<pre>

===Longer version using dynamic-programming and logarithms===

More than 10 times faster.

 

import (

}

show(table[ordinal-1])

{{out}}

<pre>

The program implements the memoized streams/lazylists with a "roll-your-own" implementation and only the necessary methods as required by this algorithm as Go does not have a library to supply such, and uses a function closure to implement a simple form of enumeration of the Hamming values. It used "llmult to perform the function of the "map" function used in the Haskell code, which is to produce a new stream which has each value of the input stream multiplied by a constant. Instead of the Haskell "foldl" function, this program uses a simple Go "for" comprehension of the input primes array.

{{trans|Haskell}}

package main

 

fmt.Printf("Found the %vth Hamming number as %v in %v.\r\n", n, rslt.String(), end.Sub(strt))

}

 

The outputs are about the same as the above versions. In order to perform this algorithm, one can see how much more verbose Go is than more functional languages such as Haskell or F# for this primarily functional algorithm.

While the above version can calculate to larger ranges due to somewhat reduced memory use, it is still somewhat limited as to range by memory limits due to the increasing size of the big integers used, limited in speed due to those big integer calculations, and also limited in speed due to Go's slow memory allocations and de-allocations. The following code uses combined techniques to overcome all three limitations: 1) as for other solutions on this page, it uses a representation using integer exponents of 2, 3, and 5 and a scaled integer logarithm only for value comparisons (scaled such that round-off errors aren't a factor over the applicable range); thus memory use per element is constant rather than growing with range for big integers, and operations are simple integer comparisons and additions and are thus very fast. 2) memory reductions are by draining the used arrays by batches (rather than one by one as above) in place to reduce the time required for constant allocations and de-allocations. The code is as follows:

{{trans|Rust}}

 

import (

 

type logelm struct { // log representation of an element with only allowable powers

}

 

func (self *logelm) lte(othr *logelm) bool {

}

func (self *logelm) mul2() logelm {

}

func (self *logelm) mul3() logelm {

}

func (self *logelm) mul5() logelm {

}

 

func log_nodups_hamming(n uint) *big.Int {

 

 

 

 

}

 

func main() {

 

 

 

 

 

 

 

{{output}}

<pre>[1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36]

The above code is not as fast as one can go as it is limited by the need to calculate all Hamming numbers in the sequence up to the required one: some reading on the relationship between the size of numbers to the sequence numbers is helpful (Wikipedia: regular number). One finds that there is a very distinct relationship and that it quite quickly reduces to quite a small error band proportional to the log of the output value for larger ranges. Thus, the following code just scans for logarithmic representations to insert into a sequence for this top error band and extracts the correct nth representation from that band. It reduces time complexity to O(n^(2/3)) from O(n) for the sequence versions, but even more amazingly, reduces memory requirements to O(n^(1/3)) from O(n^(2/3)) and thus makes it possible to calculate very large values in the sequence on common personal computers. The code is as follows:

{{trans|Nim}}

 

import (

)

 

type logrep struct {

}

type logreps []logrep

func (s logreps) Len() int { // necessary methods for sorting

}

func (s logreps) Swap(i, j int) {

}

func (s logreps) Less(i, j int) bool {

}

 

func nthHamming(n uint64) (uint32, uint32, uint32) {

 

}

 

func convertTpl2BigInt(x2, x3, x5 uint32) *big.Int {

}

 

func main() {

 

 

 

{{output}}

<pre>1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

 

As can be seen above, the time to calculate the millionth Hamming number is now too small to be measured. The billionth number in the sequence can be calculated in just about 15 milliseconds, the trillionth in about 1.5 seconds, the thousand trillionth in about 150 seconds, and it should be possible to calculate the 10^19th value in less than a day (untested) on common personal computers. The (2^64 - 1)th value (18446744073709551615th value) cannot be calculated due to a slight overflow problem as it approaches that limit.

 

=={{header|Haskell}}==

===The classic version===

 

union a@(x:xs) b@(y:ys) = case compare x y of

-- [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

-- (2125764000,2147483648)

Runs in about a second on [http://ideone.com/q3fma Ideone.com].

The nested <code>union</code>s' effect is to produce the minimal value at each step,

The amount of operations is constant for each number produced, so the time complexity should be <math>O(n)</math>. [http://ideone.com/k8PU3 Empirically], it is slightly above that and worsening, suggestive of extra cost of bignum arithmetics. [http://ideone.com/k8PU3 Using triples representation] with logarithm values for comparisons amends this problem, but runs ~ 1.2x slower for the 1,000,000.

 

 

===Avoiding generation of duplicates===

 

main = do

 

===Explicit multiples reinserting===

This is a common approach which explicitly maintains an internal buffer of <math>O(n^{2/3})</math> elements, removing the numbers from its front and reinserting their 2- 3- and 5-multiples in order. It overproduces the sequence, stopping when the ''n''-th number is no longer needed instead of when it's first found. Also overworks by maintaining this buffer in total order where just heap would be sufficient. Worse, this particular version uses a sequential list for its buffer. That means <math>O(n^{2/3})</math> operations for each number, instead of <math>O(1)</math> of the above version (and thus <math>O(n^{5/3})</math> overall). Translation of [[#Java|Java]] (which does use priority queue though, so should have ''O''&zwj;&thinsp;&zwj;(''n''&zwj;&thinsp;&zwj;log''n'') operations overall). Uses <code>union</code> from the "classic" version above:

{{out}}

[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

 

[2125764000,2147483648]

 

(1,[2,3,5])

(2,[3,4,5,6,10])

(12,[15,16,18,20,24,25,27,30,36,40,45,50,60])

 

 

 

 

 

 

 

 

| w >= 1 = error $ "Breach of contract: (w < 1): " ++ show w

| m >= nb = error $ "Generated band is too narrow: " ++ show (m,nb)

{{out}}

(55,47,64)

519312780448388736089589843750000000000000000000000000000000000000000000000000000000</pre>

 

 

 

 

 

import Data.Word

import Data.List (sortBy)

import Data.Function (on)

 

| n < 2 = case n of

0 -> error "nthHam: Argument is zero!"

| m < 0 = error $ "Not enough triples generated: " ++ show (c,n)

| m >= nb = error $ "Generated band is too narrow: " ++ show (m,nb)

| otherwise = case res of (_, tv) -> tv -- 2^i * 3^j * 5^k

where