"Kinda" addition chain calculator

Question

I build an addition chain (more information about addition chains: Wikipedia) calculator that produces shorter chains than chains with the length equal to the number that's being tried to achieve.

It doesn't always produces the shortest chains (if were talking about a big number). However still gives a pretty short chain compared to the max sized chain the number would get.

It is faster than, brute-force calculating (but obv. less accurate in finding the shortest chain (like I said above)), since it relies on an algorithm (I'm not sure if an algorithm is the right word, but basically I just used logical steps to find a short chain). Basically it starts from the given number and goes backwards to 1.

---

It works as followed:

1. Check if the number is even or odd, if it's odd check if it's a prime number.
2. If it's an even number, just divide by 2. If it's odd find the biggest factor and divide the number by it, till the factor itself is reached. If it's a prime number, subtract it by 1 and follow the steps for an even number
3. Step 1 and 2 are always repeated, and before (before and after would duplicate the values, so only 'before') every action, the current state of the number is added to a list

(It is also checking if every number had (n+1)/2 length of chains, so there's a tiny step for that, but that's not very important. This was an extra thing I did, for my math class.)

So let's say we have 5, it's an odd number so we subtract by 1 to get an even number: 4. Now we divide it by 2 and get 2, since 2 is also an even number we divide again and we got to 1 and the program stops and prints the list which is: [5, 4, 2, 1] (which is the shortest possible addition chain (I know that this only works for tiny numbers btw, for big numbers it still shortens the chain (of max size) a lot which is cool for me))

---

I am learning programming by myself and haven't touched sort/search algorithms, what could I have done better in terms of the quality of my code or even the logical steps I use to calculate?

---

n = int(input())  # kan tot 8 cijfers snel(<1min), na 8 traag

BewijsN = (n + 1) / 2

List1 = []


def IsEven(n):
    if n % 2 == 0:
        return True

    else:
        return False


def IsPrime(n):
    for x in range(n - 2):
        x += 2

        if n % x == 0:
            return False

    return True


def BigFactorCheck(n):
    for x in range(n):
        x += 1

        if n % (n - x) == 0:
            return n - x


while n > 1:
    if IsEven(n) == False:

        if IsPrime(n):
            List1.append(n)
            n += -1  # Prim naar even

        else:  # Oneven
            List1.append(n)
            BigFactor = BigFactorCheck(n)

            for x in range((n // BigFactor) - 2):
                x += 1
                List1.append(n - BigFactor * x)

            n = n - BigFactor * (x + 1)  # lelijk, maar werkt

    while IsEven(n):
        List1.append(n)
        n = n // 2

        if n == 1:
            List1.append(n)

List1.sort()
print(len(List1), List1)
if len(List1) - 1 <= BewijsN:
    print(True, len(List1) - 1, "<=", BewijsN)

Answer 1

Code Organization

Code should be organized in such a way that someone reading the code doesn't have to scroll up and down in order to understand the code. For instance, you should not have:

mainline code
function definitions
mainline code

Instead, the mainline code should all be together at the bottom:

function definitions
mainline code

Naming

The PEP 8 -- Style Guide for Python Code lists a number of rules guidelines that should be followed throughout Python code. One such guideline is:

• function and variable names should be in snake_case; MixedCase is reserved for class names.

So BewijsN and List1 should become bewijs_n and list_1. Similarly, IsEven, IsPrime and BigFactorCheck should be is_even, is_prime, and big_factor_check.

List1 is especially ugly. There is no List2, List3 and so on, so why is there a 1 in that name? number_chain might make a better name.

Boolean Test

def IsEven(n):
    if n % 2 == 0:
        return True

    else:
        return False

The function body reads approximately:

    if something is True:
        return True
    else:
        return False

Since something will be True in the "then" clause, instead of returning the literal True, we could return something. Similarly, when something is False, in the "else" clause, instead of returning the literal False, we could also return something:

    if something is True:
        return something 
    else:
        return something

At this point, we can see the if ... else is irrelevant; in both cases, we return something. So we can optimize this to:

    return something 

specifically:

def is_even(n):
    return n % 2 == 0

Range

The IsPrime function has this code:

    for x in range(n - 2):
        x += 2

This is confusing and inefficient. Confusing because the loop variable x starts at 0, and is modified inside the loop, increasing it to 2; what is it on the next iteration? Of course, the modification inside the loop body is lost when the next iteration begins, but that will often confuse a newcomer to Python.

It is inefficient, since because adding 2 each time through the loop is an unnecessary operation, which takes time. Numbers are objects, and every time a computation changes a number, the old number object is dereferenced (and possibly destroyed), and a new number object may be created. It is far faster to simply loop over the correct range: range(2, n).

def is_prime(n):
    for x in range(2, n):
        if n % x == 0:
            return False
    return True

This loop can actually be simplified and sped up, using the all(...) function and a generator expression:

def is_prime(n):
    return all(n % x != 0 for x in range(2, n))

There are many things you can do to further speed up this is_prime function. If the number would be divisible by an even number larger than 2, it would have already been divisible by 2, so you can call that out as a special case, and then only consider odd numbers 3 and up, using range(3, n, 2):

def is_prime(n):
    if n > 2 and n % 2 == 0:
        return False

    return all(n % x != 0 for x in range(3, n, 2))

Also, looking for factors larger than \$sqrt(n)\$ is inefficient, since if \$x > sqrt(n)\$ was a factor, then \$n / sqrt(n) < sqrt(n)\$ would also be a factor, and you would have already encountered it:

from math import isqrt

def is_prime(n):
    if n > 2 and n % 2 == 0:
        return False

    return all(n % x != 0 for x in range(3, isqrt(n) + 1, 2))

Due to isqrt(n), this will crash if called with a negative value. Crashing is bad. What did your function do? IsPrime(-10) returned True, which is incorrect, which is arguably worse than crashing. At least if you crash, you know something went wrong, and get a stack trace you can debug. A wrong result is harder to debug, since you don't know where it went wrong. While we're at it, neither 0 nor 1 should return True:

from math import isqrt

def is_prime(n):
    if n < 2 or (n > 2 and n % 2 == 0):
        return False

    return all(n % x != 0 for x in range(3, isqrt(n) + 1, 2))

This is faster and more correct. You could improve it even further, with more advanced prime checking, such as the sieve-of-eratosthenes.

Big Factor Check

def BigFactorCheck(n):
    for x in range(n):
        x += 1

        if n % (n - x) == 0:
            return n - x

On the last iteration, x initially is n-1, but you add 1 to it, so x actually would be n. Then n % (n - x) would be n % (n - n), or n % 0, which is a division by zero! Eek. Fortunately, you never reach the last iteration; the previous iteration would test n % 1 == 0, which should always be true. Still, dangerous code.

Again, for x in range(n) and x += 1 could simply become for x in range(1, n+1). But you don't simply want x; you want n - x. Why not just loop starting a n-1, and go down until you reach n - (n-1)? You don't even need to try the n % 1 == 0 iteration; you could stop before reaching 1, and simply return 1 if you get to the end of the for loop:

def big_factor_check(n):
    for x in range(n - 1, 1, -1):
        if n % x == 0:
            return x
    return 1

Main function

Your mainline code is complex enough to warrant its own function. You could even add a main-guard, so you can import this function into other programs if you want to use it, without executing the mainline code.

def addition_chain(n):
    number_chain = []
    while n > 1:
        # your computations here

    number_chain.sort()
    return number_chain

if __name__ == '__main__':
    n = int(input())
    bewijs_n = (n + 1) / 2
    chain = addition_chain(n)
    print(len(chain), chain)
    if len(chain) - 1 <= bewijs_n:
        print(True, len(chain) - 1, "<=", bewijs_n)

Answer 2

Improved implementation

Here's an improved implementation of the same algorithm, incorporating stuff from the other answers:

from math import isqrt

def smallest_factor(n):
    for i in range(2, isqrt(n) + 1):
        if n % i == 0:
            return i

def addition_chain(n):
    chain = []
    while n:
        if small := smallest_factor(n):
            big = n // small
            for _ in range(small - 1):
                chain.append(n)
                n -= big
        else:
            chain.append(n)
            n -= 1
    chain.reverse()
    return chain

Demo

Demo output for several n, with how long it took, how long the chain is, and the (possibly abbreviated) chain:

n=1  5.15 μs  len=1 [1]
n=2  5.01 μs  len=2 [1, 2]
n=3  9.16 μs  len=3 [1, 2, 3]
n=4  481.24 μs  len=3 [1, 2, 4]
n=5  356.58 μs  len=4 [1, 2, 4, 5]
n=6  10.75 μs  len=4 [1, 2, 3, 6]
n=7  17.10 μs  len=5 [1, 2, 3, 6, 7]
n=8  451.55 μs  len=4 [1, 2, 4, 8]
n=9  381.45 μs  len=5 [1, 2, 3, 6, 9]
n=10  372.24 μs  len=5 [1, 2, 4, 5, 10]
n=123  426.09 μs  len=10 [1, 2, 4, 5, 10, 20, 40, 41, 82, 123]
n=123456789  2178.51 μs  len=3630 [1, 2, 3, 6, 9, '...', 13717421, 27434842, 41152263, 82304526, 123456789]

Code producing the above output:

from time import perf_counter as timer

def abbreviated(chain):
    if len(chain) <= 10:
        return chain
    return chain[:5] + ['...'] + chain[-5:]
    
for n in [*range(1, 11), 123, 123456789]:
    t0 = timer()
    chain = addition_chain(n)
    t1 = timer()
    print(f'{n=}  {(t1 - t0) * 1e6:.2f} μs ', f'len={len(chain)}', abbreviated(chain))

An observation

Note that there's no need to special-case when n is even, and I left it out in the code. Your treatment was to divide it by 2. By treating 2 the same as any other factor, we instead subtract n/2 once. That's equivalent. Sure, that might make even cases slightly slower, but they're very fast anyway, so it doesn't really matter.

A simpler and better alternative

Consider this much simpler alternative:

def addition_chain(n):
    chain = []
    while n:
        chain.append(n)
        if n % 2:
            n -= 1
        else:
            n //= 2
    chain.reverse()
    return chain

Same demo as before:

n=1  2.32 μs  len=1 [1]
n=2  2.17 μs  len=2 [1, 2]
n=3  2.85 μs  len=3 [1, 2, 3]
n=4  2.55 μs  len=3 [1, 2, 4]
n=5  2.58 μs  len=4 [1, 2, 4, 5]
n=6  2.64 μs  len=4 [1, 2, 3, 6]
n=7  3.26 μs  len=5 [1, 2, 3, 6, 7]
n=8  2.01 μs  len=4 [1, 2, 4, 8]
n=9  2.58 μs  len=5 [1, 2, 4, 8, 9]
n=10  5.20 μs  len=5 [1, 2, 4, 5, 10]
n=123  4.21 μs  len=12 [1, 2, 3, 6, 7, '...', 30, 60, 61, 122, 123]
n=123456789  14.99 μs  len=42 [1, 2, 3, 6, 7, '...', 30864196, 30864197, 61728394, 123456788, 123456789]

Note that this is much faster and produces a much shorter chain for n=123456789: length 42 instead of length 3630 from your original algorithm. While your original algorithm produces long chains when a smallest factor is large, this simpler algorithm always produces chains of length O(log n).

Answer 3

Internationalization

I'd like to expand on the difference between code-language and i18n (internationalisation) / localisation (l10n).

This is a good idea (please excuse my Google translate):

# Will be fast up to 8 digits; will be slow after 8
n = int(input(
    'Voer het nummer in'
))

User-facing content should be in the language of the user. This can be very simple (as in the above example with a hard-coded locale), or very complicated, based on your requirements. There are some Python packages such as https://docs.python.org/3.8/library/locale.html that will support this effort.

This can be problematic:

# Ik begrijp dit, maar mijn collega's misschien niet
# kan tot 8 cijfers snel(<1min), na 8 traag

For better or worse, English is the de-facto language of programming and engineering. Nearly all of the workplaces I've been in have been multi-lingual, and English is a standard - just like Python itself - that we all agree on to facilitate communication. This is particularly important for open-source collaboration on the internet.

Answer 4

Some suggestions:

• Write English, not something like "BewijsN", "lelijk, maar werkt" and "kan tot 8 cijfers snel(<1min), na 8 traag" which barely anyone here can understand.
• It fails for n = 1, producing [] instead of [1].
• Use a prompt, like input("Enter the target for the addition chain: ")
• .sort() => .reverse(), since you build descending numbers. It won't make the overall solution much faster, but sorting gives the reader the wrong and confusing impression that it's not just descending.
• Improving is_prime alone like AJNeufeld showed doesn't improve your complexity from O(n) to something better, as your BigFactorCheck is also only O(n). For example, BigFactorCheck(95) checks 94, 93, 92, ..., 21, 20 before it finds 19 and stops. Much faster to search the smallest factor, i.e., 2, 3, 4, 5 and then compute the biggest as 95/5. Also, your prime check already finds the smallest factor, so if you don't throw that away, you can use that instead of searching for it again.
• Your else: # Oneven branch subtracts BigFactor from n multiple times. Or rather it subtracts multiples of BigFactor from n and doesn't update n yet. I think the former, subtracting BigFactor from n multiple times (actually updating n), would save code and make it simpler. I'm not gonna try it, though, since I'd want to compare the modification with the original by running both and comparing the results, and since your main code is not in a nice function that takes n and returns the chain, this is not as easy as it should be. So: make the main code such a function.
• if IsEven(n) == False: => if not IsEven(n):
• n += -1 => n -= 1
• n = n - ... => n -= ...
• n = n // 2 => n //= 2