2
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Michael E2
    Mar 4 at 4:59
3
$\begingroup$

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]= {}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.