Hi shiwaji, a question for you, can you prove this is the only solution?

Last edited by bobbym (2009-08-09 08:45:25)

Hi shiwaji;

To me it is a programming problem. There maybe a partial math solution using generating functions but I am not sure. Learn a programming language it will get you out of a lot of math jams.

Hi phrontister;

You have picked a difficult one to learn on. Here is why:

This is the dumbest algorithm I could think of and also the slowest. An idiot just suggested this to me. It will loop 387 420 489 times, theoretically it should get the answer (There is a land mine here, we could talk about that later). You will need to format the program below and adjust the syntax for your compiler. C++ might be able to plow through this but Basic?

FOR A=1 TO 9
FOR B=1 TO 9
FOR C=1 TO 9
FOR D=1 TO 9
FOR E=1 TO 9
FOR F=1 TO 9
FOR G=1 TO 9
FOR H=1 TO 9
FOR I=1 TO 9
IF A/(10*B+C) + D/(10*E+F) + G/(10*H+I) =1 
  THEN Print[A,B,C,D,E,F,G,H,I]
NEXT I
NEXT H
NEXT G
NEXT F
NEXT E
NEXT D
NEXT C
NEXT B
NEXT A

As an exercise for you, what can you do to speed it up.

Last edited by bobbym (2009-08-14 20:33:23)

Hi integer;

Thats where I am going with this but I didn't want too expose phrontister to anything too complex to start.

Basically, first I generated the permutations and put them in an array,vector, list whatever your particular language supports. Using the permutations cuts down the choices from 9^9 to 9!.

Also
IF A/(10*B+C) + D/(10*E+F) + G/(10*H+I) =1
  THEN Print[A,B,C,D,E,F,G,H,I]

is the worst way to test for success.

Last edited by bobbym (2009-08-15 11:18:03)

Easier now with hindsight to prune out permutations, since there is only one answer. Doing it beforehand could prune out the solution. Thats why I went with the permutations of 9.

Last edited by bobbym (2009-08-11 15:10:31)

Just wondering, are there number theory problems for which there is a proof that a solution cannot be reached without brute force?

Hi identity;

I don't think so, but many problems are not feasible even though they are theoretically possible. Combinatorial explosion as it is called makes some problems too large for brute force.

Hi phrontister;

Even though you see code like this all the time, in every language, her test is numerically unsound and there are 2 fixes for it. It worked here but you could almost say she got lucky with it.
Go here to see a little bit what I mean. The first part with excel is meaningful.
http://www.wolfram.com/broadcast/screen … ghtanswer/

Last edited by bobbym (2009-08-12 01:04:02)

Hi phrontister;

Forgive the ugliness and spaghetti code look of my prog. It is just to illustrate a point. Also I have not used any Basic for more than 20 years.

Try this in LBasic: Don't use the input command to enter f. Just change it manually. We expect to count down from 10 by 1/3 until we get to 0. Watch what happens and then try 1/2,1/6,1/8,1/10,1/5 for f. Important: this is not a bug in LBasic it is inherent in the way computers do arithmetic.

a=10
f=1/3
[loop]
a=a-f
if a=0 then print "done" : end
print a
goto [loop]

Or try this

x = 0
f=1/7
  while x <> 500
    x = x + f
    print x
  wend
end

For some fractions they terminate as expected and for some others they don't. Floating point arithmetic is not the same as how humans work with numbers. Where we see the number line as continuous, to the computer there are gaps like morse code. Some numbers cannot be represented in binary in a finite amount of digits.

For humans (a-b)^2 = (a^2 - 2 a b +b^2) is an identity. For computers it is not.

If I use a for next loop we get the correct response. Why? Because the for next loop is smart enough not to test floating point numbers for equality as she has done. It tests greater than or less than which is much more accurate.

Last edited by bobbym (2009-08-18 17:09:05)

So could this problem be solved theoretically?

Hi Bobby,

bobbym wrote:

Try this in LBasic: Don't use the input command to enter f. Just change it manually. We expect to count down from 10 by 1/3 until we get to 0. Watch what happens and then try 1/2,1/6,1/8,1/10,1/5 for f.

I tried those exercises and I see what you mean. 1/10 surprised me.

I changed your code to run to 200 to avoid the endless looping. Btw, I don't know how to stop the program mid-stream - do you?

For terminated results LBASIC prints just the integer "200", but for non-terminations it prints "200.0". I suppose LB is saying that the number is not an integer, and that the number of zeros preceding other decimal digits exceeds its precision limit.

If I use a for next loop we get the correct response.

I tried that, but I got the same incorrect responses as before. Maybe I didn't code it correctly. I'll try again...

Re your first workaround:

I don't have "break". My OS is Windows XP. I tried CTRL + all the buttons on my keyboard, but nothing except F10 did anything (F10 paused it, but I couldn't gain any further control over the program from there).

I'll have to ask LB, because the only way I can manually quit a program is via the Task Manager (CTRL + ALT + DELETE). And that's annoying.