CODEWITHSUNDEEP
pythonnumber-theory
bbd108
bbd108

Reputation: 998

Produce Generalised Hamming Numbers Python

This is my code to generate all the Hamming Numbers (aka 5-smooth-Numbers) under a given limit. https://en.wikipedia.org/wiki/Smooth_number

In number theory, a smooth (or friable) number is an integer which factors completely into small prime numbers. For example, a 7-smooth number is a number whose prime factors are all at most 7, so 49 = 7^2 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not

I know of other ways to generate the numbers, however the function I first made makes sense to me and was wondering how to expand this to 7-smooth, 11-smooth, ..., n-smooth-numbers. Is there a simpler way to change my function to loop through the primes below the limit without adding lines of very similar code?

import math

def HammingFiveUnder(limit):
    hammings = []
    exp2 = int(math.log(limit, 2))
    exp3 = int(math.log(limit, 3))
    exp5 = int(math.log(limit, 5))
    for i in range(0, exp2+1):
        for j in range(0, exp3+1):
            for k in range(0, exp5+1):
                poss_ham = 2**i * 3**j * 5**k
                if poss_ham <= limit:
                    hammings.append(poss_ham)
    return sorted(hammings)

print(HammingFiveUnder(100))

Upvotes: 2

Views: 748

Answers (3)

xdze2
xdze2

Reputation: 4151

A slightly different solution using the Cartesian product itertool.product function:

Roughly equivalent to nested for-loops in a generator expression. For example, product(A, B) returns the same as ((x,y) for x in A for y in B).

n_primes is the number of prime factor wanted taken in order.

from itertools import product as cartesianproduct # Cartesian product of input iterables.
from functools import reduce
import math

def prod(list_of_numbers):
    ''' Compute the product of the given numbers '''
    return reduce(lambda x,y: x*y, list_of_numbers)

def smoothnumbers(n_primes=3, limit=100):
    # List of the primes numbers:
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    # Compute the possible exponent ranges given the limit:
    max_exponents = [math.floor(math.log(limit, prime))
                     for prime in primes[:n_primes]]
    exponents_ranges = [range(max_exp+1) for max_exp in max_exponents]

    # loop
    smoothnumbers = []
    for exponents in cartesianproduct(*exponents_ranges):
        n = prod( factor**exp for factor, exp in zip(primes, exponents) )
        # print(exponents, n)
        if n <= limit:
            smoothnumbers.append(n)

    return sorted(smoothnumbers)

Which gives:

print( smoothnumbers(n_primes=2, limit=100) )
# [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96]

print( smoothnumbers(n_primes=3, limit=100) )
# [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36,
#  40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100]

print( smoothnumbers(n_primes=5, limit=100) )
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25,
#  27, 28, 30, 32, 33, 35, 36, 40, 42, 44, 45, 48, 49, 50, 54, 55, 56, 60, 63,
#  64, 66, 70, 72, 75, 77, 80, 81, 84, 88, 90, 96, 98, 99, 100]

Upvotes: 2

Dan Nagle
Dan Nagle

Reputation: 5415

You can keep the same logic, you just need to make use of more suitable data types and itertools.product from the standard library.

itertools.product will give you all combinations of the list items so it's equivalent to the nested loops.

import itertools

# returns (n,p) as n**p
def tuplePower(t):
  n, p = t
  return n**p

# returns the product of the list items
def multiplyIter(myIter):
  result = 1
  for i in myIter:
    result = result * i
  return result

def HammingFiveUnder(limit):
  hammings = []
  # iterable data structures
  multipliers = (2, 3, 5)
  exps = [int(math.log(limit, x)) for x in multipliers]
  # compose the list of ranges to replace nested for loops
  ranges_lists = [[i for i in range(0, n+1)] for n in exps]
  combo_list = list(itertools.product(*ranges_lists))
  # iterate through the list
  for combo_item in combo_list:
    poss_ham = multiplyIter(list(map(tuplePower, zip(multipliers, combo_item))))
    if poss_ham <= limit:
      hammings.append(poss_ham)
  return sorted(hammings)

print(HammingFiveUnder(100))

Upvotes: 1

Femkemilene
Femkemilene

Reputation: 305

A possible solution is to make a list of all possible primes, then computer all combination using itertools.combinations and multiply the elements of each of those lists. I had to filter out all the double combinations, so there is still some potential for a speed boost.

import numpy as np
import math
import itertools

def HammingFiveUnder(limit):
    hammings = []

    def prime_list():
        '''create a list with primes repeated as many times as they can maximally occur under the said limit in a prime factorisation'''
        list_with_repeated_primes = []   
        for prime in [2,3,5,7]: #change this for smooth number you want
            rep = int(math.log(limit, prime))
            for n in range(rep):
                list_with_repeated_primes.append(prime)
        return list_with_repeated_primes
    list_with_repeated_primes = prime_list()

#now make all possible combinations of primes and check against limit:
    comb = []
    for i in range(len(list_of_repeated_primes)):
        comb += itertools.combinations(list_of_repeated_primes,i+1)
    comb = np.unique(comb)
    for i in comb:
        poss_ham = np.prod(np.array(i))  
        if poss_ham <= limit:
            hammings.append(poss_ham)
    return sorted(hammings)

print(HammingFiveUnder(100))

Upvotes: 0

Related Questions