challenge for programmable calculators

[Thomas Klemm]

(12-25-2013 01:27 AM)Han Wrote:  Once you've solved a problem completely using mathematics, is there really any need for a program? I always held the opinion that programs were useful when we reached a mathematical stumbling block.

You'd still have to verify that the determinant \((1+a^2-9a)^2-4a(11a+1)\) is only positive for a = 1. So we're down at a loop of 7. Thus a program is still helpful.
Either that or you solve \((1+a^2-9a)^2-4a(11a+1)=0\) and figure that out by the roots.

Cheers
Thomas

[Thomas Klemm]

(12-25-2013 04:31 AM)Gerson W. Barbosa Wrote:  Also, no more fun writing a program anymore :-(

How do you know that a = 1 is the only solution?
Just because I said so?

[Thomas Klemm]

(12-24-2013 05:57 PM)radwilliams Wrote:  (a+b+c)*(a*b*c) = a^2+b^2+c^2 + 2*(a*b + a*c + b*c)

Is there some implied multiplication involved?

[Alberto Candel]

I would like to propose two extensions to this problem:

(1) Instead of 3 digit numbers abc, consider n-digit numbers (a_1)(a_2)...(a_n)
(2) Instead of base 10, consider numbers in other bases b, like hexadecimal b=16

Happy holidays!

[Gerson W. Barbosa]

(12-26-2013 02:06 AM)Alberto Candel Wrote:  I would like to propose two extensions to this problem:

(1) Instead of 3 digit numbers abc, consider n-digit numbers (a_1)(a_2)...(a_n)

For base 10, the list is already complete:

http://oeis.org/A038369

[kakima]

I tried exactly that earlier today. Unfortunately there aren't too many other solutions, at least for bases 10 and 16, until you go beyond eight digits. (I'm not saying there are solutions beyond eight digits, just that I stopped there.)

My original thought was to propose a challenge to write a program that given a number N, searches for N-digit solutions. When I wrote just such a program and put it in a loop from two to eight, it found only the two known 3-digit solutions. For base 16, it only found one solution.

There may be solutions in other bases. I suppose I'll have to try them...

[Alberto Candel]

(12-26-2013 02:18 AM)Gerson W. Barbosa Wrote:  

(12-26-2013 02:06 AM)Alberto Candel Wrote:  I would like to propose two extensions to this problem:

(1) Instead of 3 digit numbers abc, consider n-digit numbers (a_1)(a_2)...(a_n)

For base 10, the list is already complete:

http://oeis.org/A038369

Did not know this! Thank you.

[Han]

(12-25-2013 06:15 AM)Thomas Klemm Wrote:  

(12-25-2013 01:27 AM)Han Wrote:  Once you've solved a problem completely using mathematics, is there really any need for a program? I always held the opinion that programs were useful when we reached a mathematical stumbling block.

You'd still have to verify that the determinant \((1+a^2-9a)^2-4a(11a+1)\) is only positive for a = 1. So we're down at a loop of 7. Thus a program is still helpful.
Either that or you solve \((1+a^2-9a)^2-4a(11a+1)=0\) and figure that out by the roots.

Cheers
Thomas

This requires nothing more than calculus. Let \( f(x) = (x^2-9x+1)^2-4x(11x+1) \). Note that \( f(1) = 1 \) and \( f(2) = -15 \). Verify that \( f'(x) = 4x^3-54x^2+78x-22 \) and \( f ' ' (x) = 12x^2-108x+78 \). Using the quadratic formula, we see that \( f ' ' (x) = 0 \) when \( x = \frac{9}{2} \pm \frac{\sqrt{55}}{2} \). Since \( 7 < \sqrt{55} < 8 \),
\[ 0 < \frac{9}{2} - \frac{\sqrt{55}}{2} < 1 \]
\[ 8 < \frac{9}{2} + \frac{\sqrt{55}}{2} < 9 \]
We can easily check that \( f ' ' (x) < 0 \) on \( [ 1, 8 ] \) -- it's a parabola that opens upward and has two real zeros. Since \( f ' ' (x) < 0 \) on \( [ 1, 8 ] \), the function \( f'(x) \) is decreasing on the interval \( [1,8] \). Since \( f'(2) = -50 \), and \( f'(x) \) is decreasing, then \( f'(x) < 0 \) on the interval \( [2,8] \). This implies \( f(x) \) is decreasing on \( [ 2, 8 ] \). Since \( f(2) = -15 \), it follows that \( f(x) < 0 \) on \( [2,8] \). Given that the parameter \( a \in [ 1, 7 ] \cap \mathbb{Z} \), it follows that \( a=1 \) is the only value for which \( f(a) > 0 \).

[Thomas Klemm]

Or just have a look at the roots: {0.04974, 0.857089, 1.50476, 15.5884}
Since \(f(1)=1\) it's obvious that \(f(n)<0\) for n in {2,...,15}.
To show this for n = 15 with your method isn't possible.
In this case we're lucky that we don't have to do that.

[Han]

(12-26-2013 06:19 AM)Thomas Klemm Wrote:  Or just have a look at the roots: {0.04974, 0.857089, 1.50476, 15.5884}
Since \(f(1)=1\) it's obvious that \(f(n)<0\) for n in {2,...,15}.
To show this for n = 15 with your method isn't possible.
In this case we're lucky that we don't have to do that.

The obviousness of \( f(n) < 0 \) for \( n \in \{ 2, 3, \dotsm, 15 \} \) only comes after having used a solver, a decent graphing program, or the closed formulas for solutions to quartic polynomials. However, the mathematics involved in coming up with those formulas is not trivial. So if you did not use any software (solver or grapher), I fail to see how you can conclude "obviousness."

I'm a bit confused here. I thought the point was (in trying to go for the fastest program) to try to reduce the complexity as much as possible prior to doing any programming. My point was that in the process of reducing the complexity by using mathematics (i.e. no programming or technology), we essentially solved the problem and made the programming challenge unnecessary.

The original problem has been reduced to proving \( a = 1 \), which can be done without any solver and just basic calculus. Cruff's equation 3 is entirely unecessary. All we need (which Cruff showed) are:
\[ abc = 11a+b+1 \quad \text{and} \quad a+b+c = 9 \]
From these two formulas, we can deduce \( 1 \le a,b,c \le 7\) and that
\[ab^2+(1+a^2−9a)b+11a+1=0, \]
a point that you brought up in a previous post. In solving for \( b \) in \(ab^2+(1+a^2−9a)b+11a+1=0 \), \( b \) being a positive integer forces the condition that the descriminant must at least be non-negative. This leads to the conclusion that \( a=1 \) is the only possibility (through basic calculus), and the solution to the original programming challenge follows easily.

We never need to consider values of \( a > 7 \) since it can be proved that \( 1 \le a \le 7 \). I am also not seeing how luck factors in, either, given that everything was deduced mathematically.

Edit: Given that \( a \) can only be 7 possible integer values, brute-force-by-hand would also lead to the conclusion that the descriminant is positive only for \( a = 1 \). However Don Shepherd had interest in a non-brute force solution.

[Thomas Klemm]

(12-26-2013 07:17 AM)Han Wrote:  So if you did not use any software (solver or grapher), I fail to see how you can conclude "obviousness."

Obvious in the sense that \(f\) is continuous: it will switch the sign only at roots. Maybe too obvious to note?

Quote:I'm a bit confused here. I thought the point was (in trying to go for the fastest program) to try to reduce the complexity as much as possible prior to doing any programming.

I thought the point was having some fun with your calculators on a rainy day.

Quote:I am also not seeing how luck factors in, either, given that everything was deduced mathematically.

There's nothing wrong with your deduction. It's just that it works only up to the inflection point at ~ 8.2081. But we're lucky that we only have to show it up to 7. So we're fine! This kind of luck.
I mean there's no way you could tell beforehand it will work.
In essence it's a further reduction of the search space: instead of 7 we're down at 1. Well done!

Quote:Given that \( a \) can only be 7 possible integer values, brute-force-by-hand would also lead to the conclusion that the descriminant is positive only for \( a = 1 \).

Not sure when brute-force turns into intelligent search. Really only when we're able to enumerate the solutions without further checks?

Cheers
Thomas

[Albert Chan]

(12-24-2013 05:43 PM)cruff Wrote:  \[abc-1 = \frac{9(11a+b)}{a+b+c}\]

I don't follow how above (from post#32) can conclude *only* a + b + c = 9

(abc - 1)(a + b + c) ≡ 0 (mod 9)

→ (a + b + c) ≡ 0 (mod 9)

If a+b+c=18, min(abc*(a+b+c)) = (9*8*1)(9+8+1) = 1296 > 999, thus a+b+c = 9

7 combinations, 2 solutions: 117, 126, 135, 144, 225, 234, 333

But, more checks are needed:

→ abc ≡ 1 (mod 9)
9 combinations, 0 solution: 125, 147, 188, 227, 248, 444, 455, 578, 777

→ abc ≡ 1 (mod 3, but not mod 9) and (a + b + c) = (6 or 12 or 15)
3 combinations, 0 solution: 114, 177, 447