生成广义汉明数 Python

Question

这是我的代码，用于生成给定限制下的所有汉明数（又名 5 平滑数）。 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

我知道生成数字的其他方法，但是我首先使用的函数对我来说很有意义，并且想知道如何将其扩展为 7-smooth、11-smooth、...、n-smooth-numbers .有没有更简单的方法来更改我的函数以循环遍历低于限制的素数而不添加非常相似的代码行？

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))

Answer 1

一个可能的解决方案是列出所有可能的素数，然后使用 itertools.combinations 计算所有组合并将每个列表的元素相乘。我不得不过滤掉所有的双重组合，所以仍然有一些速度提升的潜力。

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))

Answer 2

你可以保持相同的逻辑，你只需要使用更合适的数据类型和标准库中的itertools.product。

itertools.product 将为您提供列表项的所有组合，因此它等同于嵌套循环。

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))

Answer 3

使用笛卡尔积 itertool.product 函数的稍微不同的解决方案：

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是要按顺序取的素数个数。

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)

给出：

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]

生成广义汉明数 Python

Produce Generalised Hamming Numbers Python

python

number-theory