find or generate all octal numbers from 0 to 8^10 that digit sum is equal to x-CodePudding

So given an input of 0o11110000000 base 8 ('0o' is ignored) i have to generate and count how many possible numbers that when the individual numbers are added they are the same. for example

0o1111000000 : 1 1 1 1 0 0 0 0 0 0 0 0 0 0 = 4
0o0000001111 : 0 0 0 0 0 0 0 0 0 0 1 1 1 1 = 4
0o0000000201 : 0 0 0 0 0 0 0 0 0 0 0 2 0 1 = 3

so for an input of 0o0000000001 i should get an answer of 10

My method is a very very brute force method in which i have to check every possible number from 0 to 7777 7777 77 base8. It uses the decimal represtation of the octal numbers and i use a recursive function to retrieve the octal sum of a number

How can i improve this to be a lot more faster. If possible no python modules as i doubt the machine running the program is unable to import a lot of stuff

def sum_of_octal_digits( n ):
    if n == 0 :
        return 0
    else:
        return int(n) % 8   sum_of_octal_digits( int(n / 8) )


octInput = input("Enter hex: ")
int_octInput  = int(octInput , 16)
total = sum_of_octal_digits(int_octInput )


allcombinations  = list()
for i in range(pow(8,len(e[2:]))):
    if sum_of_octal_digits(i) == total :
        allcombinations.append(i)
    
    
print(len(allcombinations))

CodePudding user response：

You're counting the number of sequences of {0, 1, 2, 3, 4, 5, 6, 7} of length n that sum to t. Call that value S[n, t].

There's a recurrence relation that S[n, t] satisfies:

S[0, 0] = 1
S[0, t] = 0 (t != 0)
S[n 1, t] = sum(S[n, t-d] for d=0...min(t, 7))

Once you have the recurrence relation, solving the problem using dynamic programming is straightforward (either by using memoization, or using a bottom-up table approach).

The program should run in O(nt) time and use O(nt) space.