-6

The closed form for $n = 3$ where $3! <= p < q < (r > 2p$ and $r > 2q)$ is $g(p,q,r)= (p -2)(q -2)(r -2) -2[(p -1)(q -1) -1 +(p -1)(r -1) -1 +(q -1)(r -1) -1] +3[p +q +r +1] -1.$ It took me about 45 minutes to find it.

For example, the McDonald's nugget problem is $p= 6, q= 9, r= 20, g(6,9,20)= 4*7*18 -2[(5*8 -1 +(5*19 -1) +(8*19 -1)] +3[6 +9 +20 +1] -1 = 504 -2(284) +3(36) -1 = 43.$

Try it for this made up problem... for 6, 8, 27; you should get 37, and it's right! Nobody has seen it since about the year 1880. Nice,... huh?? I made a YouTube video that reiterates it. William Bouris

Somebody is actually down-voting it. LOL

user124808
  • 19
  • What GCD assumptions are you making in your closed form? – Steven Stadnicki Nov 20 '15 at 19:04
  • I'm assuming that gcd(p,q,r) = 1, overall. It doesn't matter for pairwise comparisons. Good question! – user124808 Nov 20 '15 at 19:05
  • Also, I believe that $q \mod p \neq +/-1, r \mod p \neq +/-1$ and $r \mod q \neq +/-1$ is a necessary fact as well. I don't know LaTeX. – user124808 Nov 20 '15 at 19:13
  • David Zhang found, for coin denominations up to $200,$ the only triples that obey the "closed form" suggested for the Frobenius number are , ${(6,9,20),(6,8,27),(6,7,60)}.$ – Will Jagy Nov 20 '15 at 20:51

2 Answers2

4

well, no. For the triple $(6,7,10001),$ your formula gives something large, while the correct value comes from the two smaller coins, $42-6-7 = 29.$

You are using the letters $p < q < r.$ Note that the examples you give that do work have $\gcd(p,q) \neq 1.$ that is, the answer is not the same as the answer for the two smaller coins, because using just those two coins always gives multiples of $g = \gcd(p,q).$

There is nothing to prevent you having a correct formula for $\gcd(p,q) \neq 1$ and specific bounds on $r.$

How to investigate more, from wikipedia on Numerical Semigroups:

enter image description here

Will Jagy
  • 139,541
  • There must be an upper bound for r. – user124808 Nov 20 '15 at 19:24
  • @user124808, it is up to you to find such an upper bound. Note that I would usually vote to close an announcement such as yours, but it seemed just as quick to both rule out your result as stated, plus give you a restrictive problem which you might be able to finish correctly. Recommend a computer search. – Will Jagy Nov 20 '15 at 19:28
  • To be fair, the OP does require $q \not\equiv \pm 1 \mod p$, so $(6,7,10001)$ does not quite qualify as a counterexample. – David Zhang Nov 20 '15 at 19:44
  • @DavidZhang, I did not notice that. Do you know of a list of coin numbers for three coins with all denominations small (up to 30,say)? I am a bit curious now about when $\gcd(p,q) \neq 1$ and $r$ neither too small nor too large compared with $p,q.$ I think I will write a program, from a question a few weeks ago I found out how one proves that a supposed coin number really is correct. – Will Jagy Nov 20 '15 at 19:52
  • @DavidZhang, here http://math.stackexchange.com/questions/1523421/word-problem-what-is-the-largest-amount-you-cannot-buy/1524457#1524457 – Will Jagy Nov 20 '15 at 19:54
  • @WillJagy Here is an exhaustive list of Frobenius numbers for triplets $\le 30$. To be honest, I have no idea how to compute these efficiently, but there must be a way, as Wolfram Mathematica can do it remarkably quickly. – David Zhang Nov 20 '15 at 20:09
  • @DavidZhang, thank you. Wikipedia gives an easy to describe algorithm with the name Rodseth, probably the inventor, and mentions a faster but complicated one by Greenberg. I'm not sure how much patience I have, i was going to print out triples where the OP's cubic gives the correct answer, in hopes of conjecturing a bunch of conditions that make it work. I think I will implement Rodseth in the next few days, I like continued fractions. – Will Jagy Nov 20 '15 at 20:13
  • 1
    @WillJagy You're going to have quite a difficult time. There are exactly three triples $\le 100$ for which OP's formula works -- namely, ${(6, 7, 60), (6, 8, 27), (6, 9, 20)}$. He was very lucky in his choice of "made-up" problem. – David Zhang Nov 20 '15 at 20:17
  • @David, thanks again. It would have taken me some time to check up to 30..I did successfully download your list as a text file, meaning I could use C++ to check things. The thing did seem too large for $p,q,r$ of similar size, roughly cubic. – Will Jagy Nov 20 '15 at 20:24
  • @WillJagy No problem. Actually, I can confirm that extending the range to triples $\le 200$ does not add any new solutions. It may actually be the case that these are the only cases in which OP's formula gives the correct answer. – David Zhang Nov 20 '15 at 20:35
  • @DavidZhang, just goes to show. I believed a (very reasonable) conjecture of my (late) friend Kaplansky for some 20 years. I finally did an exhaustive computer search in late 2013, I found a dozen counterexamples, absolutely nowhere a human being would expect to look. – Will Jagy Nov 20 '15 at 20:45
  • Let us continue this discussion in chat. – David Zhang Nov 20 '15 at 20:52
1

Your conjectured formula doesn't appear to be correct. Take $(p,q,r) = (6,7,16)$. Their Frobenius number is $17$, but your formula gives $g(6, 7, 16) = -15$. The fact that this is a negative number should give you some serious doubt about its validity.

For a larger counterexample, take $(p,q,r) = (15131, 18910, 106986)$. Their Frobenius number is $41340527$, but your formula gives $$ g(15131, 18910, 106986) = 30595895089807. $$

David Zhang
  • 8,835
  • https://en.wikipedia.org/wiki/Numerical_semigroup#R.C3.B6dseth.27s_algorithm and previous paragraph "There is no known general formula to compute the Frobenius number of numerical semigroups having embedding dimension three or more. It is also known that no polynomial formula can be found to compute the Frobenius number or genus of a numerical semigroup with embedding dimension three. Interestingly, it is known that every positive integer is the Frobenius number of some numerical semigroup with embedding dimension three." – Will Jagy Nov 20 '15 at 20:04