Stack Overflow
Stack Overflow

Questions tagged [hamming-numbers]

Hamming Numbers are numbers whose only prime factors are 2, 3 and 5. They are named after Richard Hamming but became famous (or notorious) after Edsger Dijkstra posed the question of how to efficiently enumerate them in numeric order.

Hamming Numbers (a.k.a. regular numbers) are numbers whose only prime factors are 2, 3 and 5. They are named after Richard Hamming but became famous (or notorious) after Edsger Dijkstra posed the question, and proposed a solution, of how to efficiently enumerate them in increasing numeric order:

  • 1 is a Hamming number.
  • If n is a Hamming number, then so are 2*n, 3*n, and 5*n.

They are a particular case of more general smooth numbers.

See also .

34 questions
172
votes
21 answers

Tricky Google interview question

A friend of mine is interviewing for a job. One of the interview questions got me thinking, just wanted some feedback. There are 2 non-negative integers: i and j. Given the following equation, find an (optimal) solution to iterate over i and j in…
Chris Eberle
  • 47,994
  • 12
  • 82
  • 119
45
votes
13 answers

nᵗʰ ugly number

Numbers whose only prime factors are 2, 3, or 5 are called ugly numbers. Example: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... 1 can be considered as 2^0. I am working on finding nth ugly number. Note that these numbers are extremely sparsely…
Anil Katti
  • 1,313
  • 1
  • 14
  • 26
23
votes
9 answers

Find the Kth least number for expression (2^x)*(3^y)*(5^z)

In the expression 2x * 3y * 5z The x, y and z can take non negative integer value (>=0). So the function would generate a series of number 1,2,3,4,5,6,8,9,10,12,15,16.... I have a brute force solution. I would basically iterate in a loop…
deeKay
  • 277
  • 3
  • 9
16
votes
4 answers

how to generate numbers given their prime factors, but with unknown exponents?

Possible Duplicates: nth ugly number Find the Kth least number for expression (2^x)*(3^y)*(5^z) I'm wondering how to solve this problem in a fast and elegant way: We define "ugly" every number n which can be written in the form: 2^x * 3^y *…
Bakuriu
  • 98,325
  • 22
  • 197
  • 231
14
votes
4 answers

Generating integers in ascending order using a set of prime numbers

I have a set of prime numbers and I have to generate integers using only those prime factors in increasing order. For example, if the set is p = {2, 5} then my integers should be 1, 2, 4, 5, 8, 10, 16, 20, 25, … Is there any efficient algorithm to…
nims
  • 3,751
  • 1
  • 23
  • 27
11
votes
8 answers

Find the smallest regular number that is not less than N

Regular numbers are numbers that evenly divide powers of 60. As an example, 602 = 3600 = 48 × 75, so both 48 and 75 are divisors of a power of 60. Thus, they are also regular numbers. This is an extension of rounding up to the next power of two. I…
finnw
  • 47,861
  • 24
  • 143
  • 221
9
votes
3 answers

New state of the art in unlimited generation of Hamming sequence

(this is exciting!) I know, the subject matter is well known. The state of the art (in Haskell as well as other languages) for efficient generation of unbounded increasing sequence of Hamming numbers, without duplicates and without omissions, has…
Will Ness
  • 70,110
  • 9
  • 98
  • 181
7
votes
1 answer

Hamming numbers for O(N) speed and O(1) memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers 2^i*3^j*5^k, where i, j, k are natural numbers. Is there a possibility to generate Nth Hamming number with O(N)…
vladon
  • 8,158
  • 2
  • 47
  • 91
7
votes
3 answers

Performance of seq vs Lazy> in F#

There is a well known solution for generating an infinite stream of Hamming numbers (i.e. all positive integers n where n = 2^i * 3^j * 5^k). I have implemented this in two different ways in F#. The first method uses seq. The solution is…
Fysx
  • 805
  • 1
  • 6
  • 12
5
votes
6 answers

How do you find the list of all numbers that are multiples of only powers of 2, 3, and 5?

I am trying to generate a list of all multiples which can be represented by the form , where a, b, and c are whole numbers. I tried the following, [ a * b * c | a <- map (2^) [0..], b <- map (3^) [0..], c <- map (5^) [0..] ] but it only lists…
robbie
  • 1,219
  • 1
  • 11
  • 25
5
votes
2 answers

Finding Hamming Numbers - not code or distance

I'm currently learning C++. I am looking for Hamming numbers (numbers whose prime divisors are less or equal to 5). When I input a number n, the program should output the n-th Hamming number. Following numbers are input, and output: 1 2 3 4 5 6 7…
Jae-young Song
  • 51
  • 1
  • 2
4
votes
0 answers

Vivaldi's number

A Vivaldi's number is a number that can be factored by only 2, 3 and 5 ( V = 2^a * 3^b * 5^c, a, b, c = 0,1,...; also known as Hamming number). The task is to find the Nth Vivaldi number. The algorithm isn't too bad for small inputs, but N ranges…
monolith937
  • 429
  • 1
  • 4
  • 13
4
votes
1 answer

Hamming numbers by intervals

Here's a somewhat different approach to generating the sequence of Hamming numbers (aka regular numbers, 5-smooth numbers) based on the interval from one number in the sequence to the next. Here's an example plot of said intervals: So there is a…
Joe Knapp
  • 322
  • 2
  • 9
3
votes
2 answers

Hamming numbers and double precision

I was playing around with generating Hamming numbers in Haskell, trying to improve on the obvious (pardon the naming of the functions) mergeUniq :: Ord a => [a] -> [a] -> [a] mergeUniq (x:xs) (y:ys) = case x `compare` y of …
0xd34df00d
  • 1,496
  • 1
  • 8
  • 17
3
votes
2 answers

Trouble understanding / visualising SICP streams Hamming numbers program

I'm basically stuck at excercise 3.56 in SICP. The problem goes like this: Exercise 3.56. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than…
ashishmax31
  • 151
  • 2
  • 12
1
2 3