时间戳

首页 > 解决方案 > 生成广义汉明数 Python

python - 生成广义汉明数 Python

问题描述

这是我在给定限制下生成所有汉明数（又名 5-smooth-Numbers）的代码。https://en.wikipedia.org/wiki/Smooth_number

在数论中，光滑（或易碎）数是一个整数，它完全分解为小素数。例如，7 平滑数是质因数最多为 7 的数，因此 49 = 7^2 和 15750 = 2 × 32 × 53 × 7 都是 7 平滑数，而 11 和 702 = 2 × 33 × 13 不是

我知道生成数字的其他方法，但是我首先提出的功能对我来说很有意义，并且想知道如何将其扩展到 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))

标签： pythonnumber-theory

解决方案

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

大致相当于生成器表达式中的嵌套 for 循环。例如，product(A, B) 返回与 ((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]

推荐阅读