Ggthjy

I found some months ago that I could generate Hamming multiples of 3 and 5 multiples (3^x & 5^x) in one list comprehension. There are many fewer 3 and 5 Hamming multiples in a Hamming sequence. I did not have to be concerned with duplicate multiples as it is 2 disparate lists.

All I needed to do was add the Hamming 2 multiples.

When I did, it was chaos. Multiples of the 3 and 5 multiples with the 2^x produced clean Hamming numbers but left even more at the end of the list that had missing Hamming numbers between them.

The problem was the Cartesian product of the 2 multiples and the 3&5 multiples.

I had used the 3^x times 5^x’s in another algorithm successfully. I had limited the list with some involved calculation.

Then, I encountered the same problem working with primes. I wanted a list to subtract from a wheel but the list contained much excess. It was another huge Cartesian product of values.

I didn’t know which elements to eliminate from either list and I thought them intermixed.

Then it dawned on me. I tried it with the primes and it worked. Then with the Hamming 2s and it worked.

First I rewrote the 3 & 5 multiples list comprehension with the much simpler logic and way less calculation.

What was the solution? All it is, is using the end value of the generated first list to limit values of subsequent lists. List comprehensions take the first value of the first list and apply it to all values in the second list thus making a list. It is the first list end value that is the limit of each subsequent list. These limited lists do not generate any excess at the end of any list

The prime’s composite list to subtract is top and bottom diagonal to form a rouge triangle. In it x and y are identical. The Hammings lists are bottom, irregular diagonal only. The x and y are different.

My problem, now, is how to specify how many Hammings I want instead of thex in 2^x as the parameter. Is it just practical to use take with some derived value of x (in 2^x) to get the number of Hammings wanted? How can x be derived from specified n number of Hamming wanted? The second thing is how fast is this compared to the fastest Hamming list generators?

Thanks for any help you can offer.

The Hamming functions follow

gnf n f = scanl (*) 1 $ replicate f n



mk35   n = (c->      [m| t<- gnf 3 n, f<- gnf 5  n,    m<- [t*f], m<= c]) (2^(n+1))

mkHams n = (c-> sort [m| t<- mk35  n, f<- gnf 2 (n+1), m<- [t*f], m<= c]) (2^(n+1))

last $ mkHams 50

2251799813685248

(0.03 secs, 12,869,000 bytes)

2^51

2251799813685248

4/5/2019

@Will Ness on SO suggested limiting early.

gnf n f| f==2= scanl (*) 1 $ replicate n 2

       | f==3= takeWhile (<=2^(n+1))$ scanl (*) 1$ replicate n 3

       | f==5= takeWhile (<=2^ n)   $ scanl (*) 1$ replicate n 5 

Thank @E-Coms for suggesting short circuit limiting very large lists generated.

hams2' n c d = [ takeWhile (<=d) [ m*f| m<- gnf c 2 ]| f<- [a*b| a <-gnf n 3, b<-gnf n 5] ]

hams2 n = sort.concat $ hams2' n (n+1) (2^(n+1))

last $ hams2 100

2535301200456458802993406410752

(0.09 secs, 69,227,792 bytes)

2 ^ 101

2535301200456458802993406410752