Stack Overflow
Stack Overflow

Questions tagged [smooth-numbers]

In number theory, a smooth number is an integer which factors completely into small prime numbers. Multiples of {2,3,5} are known as 5-smooth, regular, or Hamming numbers. A positive integer is called k-smooth if none of its prime factors is greater than k.

In number theory, a smooth number is an integer which factors completely into small prime numbers. Multiples of {2,3,5} are known as 5-smooth, regular, or Hamming numbers. A positive integer is called k-smooth if none of its prime factors is greater than k. Smooth numbers are especially important in cryptography relying on factorization.

See also .

14 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
16
votes
10 answers

Printing numbers of the form 2^i * 5^j in increasing order

How do you print numbers of form 2^i * 5^j in increasing order. For eg: 1, 2, 4, 5, 8, 10, 16, 20
shreyasva
  • 13,126
  • 25
  • 78
  • 101
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
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
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
4 answers

Super Ugly Number

So the problem is: Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the…
yehyaawad
  • 126
  • 1
  • 11
3
votes
3 answers

Can someone explain to me this part of Dixon's factorization algorithm?

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound B and some number N and search for numbers between sqrtN and N whose squares are B-smooth, meaning all their…
polarbits
  • 187
  • 1
  • 3
  • 10
2
votes
1 answer

How to display first N natural numbers, knowing the divisors in Lisp

Display first N natural numbers, the divisors of which are only 2, 3 and 7. I wrote something like that. I am a beginner in Lisp. Thank you! defvar x 1 (defun numbers(n) if(mod x 2 ) (loop for x from 1 to n do(print x) …
Doc Humanity
  • 21
  • 5
1
vote
1 answer

Hamming with lists in Haskell

I want to write a hamming function in Haskell that gets a list as Input. I already have this: merge :: [Integer] -> [Integer] -> [Integer] merge (x:xs)(y:ys) | x == y = x : merge xs ys | x < y = x : merge xs (y:ys) |…
beginner334
1
vote
7 answers

algorithm to find products of a set of primes, in order, greater than x

Consider the finite set {2,3,5,...,n}. I am interested in primes but the question could apply to any set of numbers. I want to find all possible products of these numbers in ascending order, and in particular greater than or equal to some number x.…
Tavin
  • 390
  • 2
  • 13
1
vote
2 answers

Haskell Hamming numbers, works but shows duplicates

I am trying to generate hamming numbers in haskell, the problem is I get duplicate #'s in my output list and I cannot figure out why exactly. Should I just create a remove duplicates function or am I just missing something simple? Also in the…
user1311286
0
votes
2 answers

Haskell List comprehensions infinite list problem

I'm trying to learn Haskell and comprehension lists but cannot find solution on this: mylist = [x*y | x <- [1..], y <- [1..]] After my trials the result is something like this mylist = [1,2,3,4,5,...] because in list comprehensions, x takes the…
JAM AICA
  • 91
  • 1
  • 10