Sum of fractions which equals 1

shiwaji · 2009-08-07 23:11:34

Hi all folks,

I am stuck on this math fraction puzzle...Could any of you guys help me out...here it goes...

Using 1,2,3,4,5,6,7,8,9 you need to make the correct sum:

x/xx + x/xx + x/xx =1

here x has to be a digit out of 1,2,3,4,5,6,7,8,9 and the denominator has to be filled in by 2 numbers.

all digits have to be utilised.

bobbym · 2009-08-08 01:29:06

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

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

shiwaji · 2009-08-09 17:40:55

hello bobbym,

Thnks for the reply...

Can you tell me the logic behind the solution...i have been trying to solve this equation for over two days...

bobbym · 2009-08-09 17:57:19

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.

phrontister · 2009-08-10 03:50:34

Hi Bobby,

If you have time, could you post the code for solving this in BASIC? That's the only language I 'know' atm - I'm hoping to venture into something else some day when I get some spare(!) time...maybe Python.

I've had a fair sort of a crack at it but am not getting anywhere with it because I haven't done much programming, and I'd like to learn. If I wrote the code myself I'm sure that running it would melt my cpu.

Thanks!

bobbym · 2009-08-10 08:01:22

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-13 22:33:23)

integer · 2009-08-10 09:51:56

bobbym wrote:

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

bobbym,
How did you arrive at the answer?
Really curious.

QUOTE from bobbym

This is the dumbest algorithm I could think of and also the slowest. An idiot just suggested this to me. FOR A=1 TO 9 ... NEXT A

It seems that BC would take 2 numbers from a set of 9 digits.
EF would take 2 numbers from the remaining 7 digits.
and HI would take 2 numbers at a time from the remaining 5 digits.

Then use the remaining three digits for A, D & G.
It would not require that A,D,G be permuted since BC, EF, & HI will be.

bobbym · 2009-08-10 09:59:56

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-14 13:18:03)

mathsyperson · 2009-08-10 10:22:27

Integer also notes that since the left hand side's terms are all the same structure, the number of permutations can lose another factor of 6.

If you were allowed to analyse the problem mathematically before writing the code, you could probably eliminate more. (eg. permutations that have the 1 in a numerator)

bobbym · 2009-08-10 11:10:42

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-10 17:10:31)

phrontister · 2009-08-10 21:52:47

I was curious to find out how an experienced BASIC programmer would tackle this in BASIC, and as I use LibertyBASIC I posted a question on their forum this afternoon. Janet responded (verrrrry quickly!) with this code, which in 86 seconds finds that there is only one solution (the one quoted by Bobby...plus its 5 positional permutations):-

I haven't tried to understand the code yet, but I'll post it now anyway.

Last edited by phrontister (2009-08-11 00:48:32)

Identity · 2009-08-10 23:34:23

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

bobbym · 2009-08-11 01:52:40

Hi phrontister;

I am just learning liberty basic also. That is what I did to solve this problem but in another language. As I said above you generate the permutations of 9 and try each one.

If (n(1) / (n(2) * 10 + n(3))) + (n(4) / (n(5) * 10 + n(6))) + (n(7) / (n(8) * 10 + n(9))) = 1 Then
nValids = nValids + 1

My beef with her code is this line!

Last edited by bobbym (2009-08-11 02:02:20)

bobbym · 2009-08-11 01:57:19

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.

phrontister · 2009-08-11 02:29:40

Hi Bobby,

bobbym wrote:

If (n(1) / (n(2) * 10 + n(3))) + (n(4) / (n(5) * 10 + n(6))) + (n(7) / (n(8) * 10 + n(9))) = 1 Then
nValids = nValids + 1
My beef with her code is this line!

What beef is that? Do you have a fix for it, or a better approach altogether?

bobbym · 2009-08-11 02:34:13

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-11 03:04:02)

phrontister · 2009-08-11 07:44:34

bobbym wrote:

Go here to see a little bit what I mean. The first part with excel is meaningful.
http://www.wolfram.com/broadcast/screen … ghtanswer/

Yes - I think I can see that relying on results from fractions can, in some circumstances, produce errors.

Here's a fix I thought up that restricts the number of fractions in that line to one, and it occurs after all the other calculations are done:-

If (n(1) * (n(5) * 10 + n(6)) * (n(8) * 10 + n(9)) + n(4) * (n(2) * 10 + n(3)) * (n(8) * 10 + n(9)) + n(7) * (n(2) * 10 + n(3)) * (n(5) * 10 + n(6))) / ((n(2) * 10 + n(3)) * (n(5) * 10 + n(6)) * (n(8) * 10 + n(9))) = 1 Then
nValids = nValids + 1

Is this the sort of thing you mean, Bobby? It seems a bit wordy...you've probably got a better way of expressing that.

The code runs fine, but a bit longer.

What's the other fix you've got in mind? (or the other two, if mine isn't one).

Last edited by phrontister (2009-08-11 07:45:41)

bobbym · 2009-08-11 09:26:34

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.

These were prepared quickly and may contain bugs but the principles are standard from numerical analysis.

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

phrontister · 2009-08-11 12:35:12

Hi Bobby,

Thanks for all of that! I could only look at it quickly this a.m. and I've got to run now, so I'll have a closer look at it tonight.

bobbym wrote:

Workaround #2:

The principle of this workaround came to me in bed last night just before I went to sleep (my mind's most productive moments!), and I was going to post about it morning...but you've saved me the trouble.:)

Identity · 2009-08-11 18:41:45

So could this problem be solved theoretically?

bobbym · 2009-08-11 19:12:11

Hi Identity;

I don't have a mathematical solution to this problem or to mine at:
http://www.mathisfunforum.com/viewtopic … 51#p116951

phrontister wrote:

If you have time, could you post the code for solving this in BASIC? That's the only language I 'know' atm - I'm hoping to venture into something else some day when I get some spare(!) time...maybe Python.

Since you got me looking at Basic, I dug up an old, old copy of QBasic 7.1. It only has an old dos gui. but it's like 25 times faster than LBasic 4.02 on my machines.

Last edited by bobbym (2009-08-13 01:08:57)

phrontister · 2009-08-13 01:41:08

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:

As you suggested, I changed the offending line. I came up with:

Same results as before, in the same time.

bobbym · 2009-08-13 01:52:55

Hi phrontister;

ctrl + break is supposed to stop a program.

phrontister · 2009-08-13 04:31:12

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.

bobbym · 2009-08-13 19:20:49

Its ctrl + pause/break : this key is above the arrow keys (at the top). It stops program execution in LBasic.

Last edited by bobbym (2009-08-13 19:21:41)

Math Is Fun Forum

#1 2009-08-07 23:11:34

Sum of fractions which equals 1

#2 2009-08-08 01:29:06

Re: Sum of fractions which equals 1

#3 2009-08-09 17:40:55

Re: Sum of fractions which equals 1

#4 2009-08-09 17:57:19

Re: Sum of fractions which equals 1

#5 2009-08-10 03:50:34

Re: Sum of fractions which equals 1

#6 2009-08-10 08:01:22

Re: Sum of fractions which equals 1

#7 2009-08-10 09:51:56

Re: Sum of fractions which equals 1

#8 2009-08-10 09:59:56

Re: Sum of fractions which equals 1

#9 2009-08-10 10:22:27

Re: Sum of fractions which equals 1

#10 2009-08-10 11:10:42

Re: Sum of fractions which equals 1

#11 2009-08-10 21:52:47

Re: Sum of fractions which equals 1

#12 2009-08-10 23:34:23

Re: Sum of fractions which equals 1

#13 2009-08-11 01:52:40

Re: Sum of fractions which equals 1

#14 2009-08-11 01:57:19

Re: Sum of fractions which equals 1

#15 2009-08-11 02:29:40

Re: Sum of fractions which equals 1

#16 2009-08-11 02:34:13

Re: Sum of fractions which equals 1

#17 2009-08-11 07:44:34

Re: Sum of fractions which equals 1

#18 2009-08-11 09:26:34

Re: Sum of fractions which equals 1

#19 2009-08-11 12:35:12

Re: Sum of fractions which equals 1

#20 2009-08-11 18:41:45

Re: Sum of fractions which equals 1

#21 2009-08-11 19:12:11

Re: Sum of fractions which equals 1

#22 2009-08-13 01:41:08

Re: Sum of fractions which equals 1

#23 2009-08-13 01:52:55

Re: Sum of fractions which equals 1

#24 2009-08-13 04:31:12

Re: Sum of fractions which equals 1

#25 2009-08-13 19:20:49

Re: Sum of fractions which equals 1

Board footer