0
\$\begingroup\$

I am trying to filter steps such that it only contains numbers from 1 to step_size that aren't divisible by factors of step_size. However, the only way I can get it to work is using a flag like this, which seems to be suboptimal.

(This is part of a larger prime factorizer, which works quite well with this prime_count, even if it is somewhat arbitrary.)

number = 651687138465 # Some integer > 1
preset_primes = [2, 3, 5, 7, 11, 13, 17]
# Actual code of the question starts here
prime_count = min(max(3, 1 + len(str(number)) // 3), 7)  # Arbitrary, but it works well
step_size = math.prod(preset_primes[:prime_count])
steps = [1]  # 1 is always a step, 2-4 never are
for i in range(5, step_size):
    flag_append = True
    for prime in preset_primes[:prime_count]:
        if not i % prime:
            flag_append = False
    if flag_append:
        steps.append(i)
\$\endgroup\$
3
  • \$\begingroup\$ Python has built-in functions any and all which evaluate iterables of logical values. You can use generator expressions with them, like any(i % prime == 0 for prime in preset_primes) or all(i % prime != 0 for prime in preset_primes). \$\endgroup\$
    – aghast
    Nov 12, 2023 at 12:29
  • \$\begingroup\$ (@aghast: discussed in J_H's older answer.) \$\endgroup\$
    – greybeard
    Nov 12, 2023 at 16:14
  • \$\begingroup\$ This has been done many times before, including here. \$\endgroup\$
    – Mast
    Nov 12, 2023 at 18:11

2 Answers 2

2
\$\begingroup\$

natural log

I'm unhappy with this expression:

prime_count = ... len(str(number)) // 3

Since the length computes log10(), and 3 is roughly 2.718, it seems it would be more honest to write ln(), or math.log(number).

As written it is a little too magical. If we have benchmark results showing how FP is "too slow" in this context, we should at least have a # comment describing those timings or linking to an url.

It's also unclear why we compute min( ... , 7). The magic number should be expressed as len(preset_primes). But there's no need for it anyway, since a "long" slice, e.g. [:9], will simply consume the seven available factors with no complaint.


early exit

When we clear flag_append = False, we should take the opportunity to break out of the loop.

Or you might choose to rephrase that loop in terms of the any() function. (Close relative of all().)


numba

In the interest of speed you might want to put this code in a type annotated helper function. Then you could use numba's @njit decorator to run it compiled instead of running it as interpreted bytecode.

\$\endgroup\$
4
  • \$\begingroup\$ Regarding the first point - math.log(number)/math.log(1000) is identical to log10(x)/3. But it's not quite the same as what is currently done (only for number=10**n), I will check what the performance impact is. \$\endgroup\$ Nov 12, 2023 at 1:51
  • \$\begingroup\$ Oh, I read that and my first thought was it might relate to density of primes, the familiar N / ln(N) expression. So I didn't want the "natural log" aspect obscured. If there's something else going on there, it would be worthwhile to describe it in a # comment, perhaps with URL citation of some relevant math paper. \$\endgroup\$
    – J_H
    Nov 12, 2023 at 2:01
  • \$\begingroup\$ It somewhat relates, yes. In this case the following code will check these steps, shifted by a loop using step_size and as such for smaller numbers, creating lots of steps simply isn't worth it, while larger numbers greatly benefit. The len(str(number)) // 3 has been a better choice than other functions I've tested and as such it's there. Actually, int((1 + math.log(number))/(3*math.log(10))) (the 1+ here is required to be equal to len), which I would have assumed to be identical, returns slightly too small values for numbers close to 10**n, is that just math.log() being inaccurate? \$\endgroup\$ Nov 12, 2023 at 2:32
  • \$\begingroup\$ Along with break, mention/demonstrate for …: ‹body› else: ‹after regular termination›. \$\endgroup\$
    – greybeard
    Nov 12, 2023 at 7:48
1
\$\begingroup\$

i is not divisible by a factor of step_size iff gcd(i, step_size) == 1. Otherwise, that gcd is the corresponding factor or a product of multiple factors such that they divide i.

So you can write:

steps = [1]
for i in range(5, step_size):
    if math.gcd(i, step_size) == 1:
        steps.append(i)

You could, if you wanted, write that as a list comprehension:

steps = [i for i in range(1, step_size) if math.gcd(i, step_size) == 1]

With that caveat that I had to make the range start at 1, so 2..4 are only excluded because the product of small primes that we used includes 2 and 3.

\$\endgroup\$
1
  • \$\begingroup\$ (Would have upvoted if the question was tagged algorithm - any insights on performance?) \$\endgroup\$
    – greybeard
    Nov 12, 2023 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.