Python Forum
this weekend's python class assignment
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
this weekend's python class assignment
#1
this weekend's python class assignment:

a command that takes a number (or more than one of them) and determines an expression consisting of a sum of one or more powers of 2 that equals that number.

Output:
> powersoftwosum 4672 4672 = 2**12 + 2**9 + 2**6 >

test your code with this number:

173688133855974293135356477513031861779904976998460846059186376011869694459904
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply
#2
This problem interested me, and I solved its more general version: when one asked to find decomposition by powers not only of 2, but
arbitrary number.

from itertools import accumulate
def decompose(a, base=2):
    """Decompose the number by powers of specified base. 
    
    4672 = 2**12 + 2**9 + 2**6 (base = 2)
    """
    res = list()
    def _recursion(a, res=res):
        if a % base != 0:
            raise Exception("Couldn't decompose the number.")
        ind = 0
        while a % base == 0:
            a = a / base 
            ind += 1
        if ind:
            res.append(ind)
        if a == 1:
            return list(accumulate(res))
        if a > 1:
            a -= 1
            _recursion(a, res=res)
    _recursion(a)
    return list(accumulate(res))
decompose(4672)
Output:
[6, 9, 12]
decompose(4672, base=4)
Output:
[3, 4, 4, 6] # 4672 = 4**3 + 4**4 + 4**4 + 6**4


decompose(4672, base=8)
Output:
[2, 3, 4] # 4372 = 8**2 + 8**3 + 8**4
Finally,

decompose(173688133855974293135356477513031861779904976998460846059186376011869694459904, base=2)
Output:
[255, 256]
decompose(173688133855974293135356477513031861779904976998460846059186376011869694459904, base=8)
Output:
[85, 85, 85] # big number = 8**85 + 8**85 + 8**85
Reply
#3
i was interested in seeing how people would address or solve or deal with extremely large numbers and what algorithmic optimization they might use, if any, like finding how big the number is. one method for base 2 is to just call bin() and let it do all the hard work, no matter how big the number is. this is basically the same problem of converting a number to a sequence of digits as your solution shows.

if someone asks for code to find the next power of 2 after a number n you can simply do:
print('2**'+str(len(bin(n))-2))
is this cheating? of course not. it's finding the quickest solution, quickly, and moving on to the next task.

if Python had a function to do that in any base (surely there is one somewhere) that would be the one to use for the any-base case. i have implemented one, but it's a mess right now. maybe i'll clean it up this weekend if i have time.
Tradition is peer pressure from dead people

What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020