We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #88: Product-sum numbers
  4. Discussions

Project Euler #88: Product-sum numbers

Sort by

recency

|

15 Discussions

|

  • antonbyv
     + 0 comments
    Python 
    def valid(n: int, k: int) -> bool:
    if k > limit:
        return False
    if minK[k] > n:
        minK[k] = n
        return True
    return False
    
def getMinK(n: int, product: int, summ: int, depth: int = 1, factor: int = 2) -> int:
    if product == 1:
        return 1 if valid(n, depth + summ - 1) else 0
    
    res = 0
    if depth > 1:
        if product == summ:
            return 1 if valid(n, depth) else 0
        
        if valid(n, depth + summ - product):
            res += 1
    
    for i in range(factor, int(product ** .5) + 1):
        if product % i == 0:
            res += getMinK(n, product // i, summ - i, depth + 1, i)
            
    return res

limit = int(input())
minK = [9999999] * (limit + 1)

n, summ, i = 4, 0, 1
while i < limit:
    cnt = getMinK(n, n, n)
    if cnt > 0:
        i += cnt
        summ += n
    n += 1

print(summ)

  • nc1969
     + 0 comments

    Easy, are you sure? It took me five weeks. Not full time of course.

  • micahleamer
     + 1 comment

    The bounds for N are way higher here than on project Euler. Never the less it is possible even in Python to compute the whole thing in the time alotted. In my loop to consider all products I only needed to keep track of three numbers for each element in the queue: the product the sum and the largest factor in the current product. All products can then be generated recursively by condidering previous products and multiplying by a new number of value greater than or equal to what was previously the largest factor. Since 2k is always a product for k of length k i.e. 1*1*....*1*2*k=1+...+1+2+k when we have k-2 ones, the univeral bound for products is 2N.

  • kitchent
     + 1 comment

    Is there any non-recursive approach out there? The recursive version loops through candidates in such a way that answers are updated occasionally (an answer you find midway might be replaced by another at the end of the day).

    I tried to use a dequeue and set to generate multiplicative partitions (based on a list of primitive factors) of ascending n, and whenever any answer is found it is guaranteed to be one of the final answers. It seems to be correct but was too slow for half of the test cases. I don't know if it is because of the algorithm itself which is poor in nature, or the extensive use and manipulation of list and set in this case.

    This is the difference between constructing products from ascending factors and constructing factors from ascending products. Well, after all the former approach sounds a lot more straightforward.

  • Anyone_
     + 0 comments

    This source may HELP https://mail.google.com/mail/u/0/?ui=2&ik=3e125a257a&view=att&th=16173693abe9a47c&attid=0.1&disp=safe&realattid=1591800991683969024-local0&zw

    Keep coding:)