Dec-23-2021, 01:49 PM
Hi all,
I am trying to solve problem 78 from Project Euler (https://projecteuler.net/problem=78). The problem is related to integer partition. The question here is to find the first number, n, for which p(n) is divisible by 1e6. I have tested my algorithm for a small number of coins (<100) and it seems to work fine (it produces the correct results). My idea was to use the modulo operator to determine the number of coins for which the partition function = 0. However, I get the wrong results over and over again... I compared my results with other algorithms that produce the correct number, and it seems that it is related to the accuracy of the numbers that are determined by my algorithm. The answer should be 55374, but my algorithm finds the first n to be 4096. Any idea what is wrong here? Note that I have no experience with Python, so I haven't used any functions or whatever yet.
I am trying to solve problem 78 from Project Euler (https://projecteuler.net/problem=78). The problem is related to integer partition. The question here is to find the first number, n, for which p(n) is divisible by 1e6. I have tested my algorithm for a small number of coins (<100) and it seems to work fine (it produces the correct results). My idea was to use the modulo operator to determine the number of coins for which the partition function = 0. However, I get the wrong results over and over again... I compared my results with other algorithms that produce the correct number, and it seems that it is related to the accuracy of the numbers that are determined by my algorithm. The answer should be 55374, but my algorithm finds the first n to be 4096. Any idea what is wrong here? Note that I have no experience with Python, so I haven't used any functions or whatever yet.
import numpy as np # number of coins N = 100000 # pre-allocate some arrays # Pstore contains the partition values # gstore contains the generalized pentagonal numbers # signs contains alternating signs Pstore = np.zeros((N,1)) gstore = np.zeros((N,1)) signs = np.zeros((5*N,1)) # create array with alternating signs for n in range(0,N): signs[4*n+1] = 1 signs[4*n+2] = 1 signs[4*n] = -1 signs[4*n+3] = -1 signs = np.delete(signs, 0) # start loop for n in range (0,N): # partition function = 1 for n = 0 and n = 1 if n == 0: Pstore[n] = 1 elif n == 1: Pstore[n] = 1 gstore[n] = 1 # calculate generalized pentagonal number elif n > 1: if n % 2 == 0: gstore[n] = (3*(-int(n/2))**2-(-int(n/2)))/2 else: gstore[n] = (3*(int(n/2)+1)**2-(int(n/2)+1))/2 a = -1 counter = 0 # calculate partition number and store while a < 0: if n > gstore[counter+1]: Pstore[n] += signs[counter] * Pstore[int(n-gstore[counter+1])] counter += 1 elif n == gstore[counter+1]: Pstore[n] += signs[counter] * Pstore[int(n-gstore[counter+1])] a = 0 elif n < gstore[counter+1]: a = 0 # print value if number is found if Pstore[n] % 1000000 == 0: print(Pstore[n])