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:
- Check if the number is even or odd, if it's odd check if it's a prime number.
- 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
- 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)