# Strange results from FrobeniusSolve

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?

• Echoing back mean Mathematica was unable to evaluate the command (and produce a solution). Possibly you ran into a system limit, but usually there is an error message when a limit is exceeded. I'm not sure why it does not succeed. Mar 4 at 4:59

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:= FrobeniusSolve[{290289902302528, 141751767173},
170141183460469231731687303715884105727, 1]

Out= {{586107825697347144736412, 276674741977267}}

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

Out= {{170141183460469231731687303715884105727, 0, 0, 0}}

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

Out= {}