Frobenius Problem

92 Views Asked by At

Let a[1],...,a[n] be positive integer such that gcd(a[1],...,a[n])=1 and a[1]<...< a[n]
how can find number such that "Max number of representable is 1 in linear combination" for example :

a[1]=7 ; a[2]=11 ; a[3]=13 => 45

3*7+1*11+1*13=45

unique representable

I'm looking for a formula for that

Code Python for find number


def builtin_gcd(a,b):
      for p in range(1,a+1):
            if a%p==0 and b%p==0:
                  t=p
      return t

def gcd(a, *r):
      for b in r:
            a = builtin_gcd(a, b)
      return a

def H(n,L):
      'L::list'
      if n==0:
            return 0
      aa=int(n/L[0])
      bb=int(n/L[1])
      cc=int(n/L[2])
      s=0
      for a in range(aa+1):
            for b in range(bb+1):
                  for c in range(cc+1):
                        if a*L[0]+b*L[1]+c*L[2]==n:
                              s+=1
      return(s)
def find(List):
      if gcd(*List)!=1 :
            return("Error GCD: the gcd of the given list should be number 1 but is %d"%gcd(*List)) 
      a=List[0]*List[1]-List[0]-List[1]
      for i in range(a+1,0,-1):
            if H(i,List)==1:
                  return i

find([7,11,13])=45