Strange results from FrobeniusSolve

Question

As part of pruning for my code searching for optimal addition chains I want to try and find some fast ways to discover that certain numbers are not representable in the Frobenius coin problem. An important number for me is $2^{127}-1$ as the shortest addition chain for this number is unknown. I want to experiment with FrobeniusSolve in mathematica. So for example mathematica can see this has no solutions:

FrobeniusSolve[{785518299414867319177, 
  750840562311845410824}, 170141183460469231731687303715884105727]

I am currently unable to do this same calculation myself since it seems too slow to generate the extended GCD so far. I am having another go at this though but find some of the behavior puzzling. For example this fails with a memory exception:

FrobeniusSolve[{290289902302528, 
  141751767173}, 170141183460469231731687303715884105727, 3]

Ok so that's probably solving the problem in some general (I know it uses Lattice basis reduction) way while a simple problem to solve with the extended GCD. Stranger still this problem just echos back the command:

FrobeniusSolve[{1, 590464, 1180928, 
  1771392}, 170141183460469231731687303715884105727, 10]

I was hoping to experiment a little but the behavior seems strange. What does the echoing back mean?

Answer 1

FrobeniusSolve has optimized algorithms for finding all solutions and for finding one solution (or proving that no solutions exist). When the requested number of solutions is m>1, FrobeniusSolve has a heuristic for reducing the number of variables, but for two variables the currently implemented method defaults to finding all solutions and then returning m of them. When there are too many solutions to enumerate them all, FrobeniusSolve fails (of course it should, and will, handle out-of-memory exceptions better). Note that if you request one solution instance, the examples work fast.

In[1]:= FrobeniusSolve[{290289902302528, 141751767173},                                   
170141183460469231731687303715884105727, 1]                                               

Out[1]= {{586107825697347144736412, 276674741977267}}

In[2]:= FrobeniusSolve[{1, 590464, 1180928, 1771392},                                     
170141183460469231731687303715884105727, 1]                                               

Out[2]= {{170141183460469231731687303715884105727, 0, 0, 0}}

In[3]:= FrobeniusSolve[{590464, 1180928, 1771392},                                        
170141183460469231731687303715884105727, 1]                                               

Out[3]= {}