Prev: Pi approximation function optimization
Next: error with intial conditions for ode45
From: Jared F on 12 Mar 2010 20:55
I came across the "brain teaser" of finding the best approximation of pi by dividing one 9-digit number by another 9-digit number. Both numbers contain 1 through 9 once.

I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.

I've tried a couple different methods of writing a program to find a better approximation, but all I can come up with is a massive number of loops that would take way too long for my computer to process.

I'll paste my current program below. If you can think of a better way to write this, let me know. I don't have an extensive background in matlab, so I'm at a loss for how to optimize this. Thanks!

Program Below
____________________________________

for a = 3:9;
for b = 1:9;
for c = 1:9;
for d = 1:9;
for e = 1:9;
for f = 1:9;
for g = 1:9;
for h = 1:9;
for i = 1:9;
for j = 1:9;
for k = 1:9;
for l = 1:9;
for m = 1:9;
for n = 1:9;
for o = 1:9;
for p = 1:9;
for q = 1:9;
for r = 1:9;

x = 100000000.*a+10000000.*b+1000000.*c+100000.*d+10000.*e+1000.*f+100.*g+10.*h+i;
y = 100000000.*j+10000000.*k+1000000.*l+100000.*m+10000.*n+1000.*o+100.*p+10.*q+r;

z = x/y;


if (z - pi < .001)

format short;

printf('x = %i\n', x);
printf('y = %i\n', y);
format long;
printf('z = %i\n', z);
disp('----------');

endif

endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
endfor
From: John D'Errico on 12 Mar 2010 21:33
"Jared F" <jfritz408(a)yahoo.com> wrote in message <hnerad$sf3$1(a)fred.mathworks.com>...
> I came across the "brain teaser" of finding the best approximation of pi by dividing one 9-digit number by another 9-digit number. Both numbers contain 1 through 9 once.
>
> I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.
>
> I've tried a couple different methods of writing a program to find a better approximation, but all I can come up with is a massive number of loops that would take way too long for my computer to process.
>

I won't do homework assignments, which this sounds
surprisingly like. And even if this is something you wish
to try yourself, you won't gain anything by me doing
it for you. However, you did make a start at it, so I''ll
give you a hint.

You want to find a ratio of TWO pan-digital numbers
that yields pi to as high an approximation as possible.

Rather than looping massively as you tried, why not
search over all denominators? How many 9 digit
pan-digital numbers are there? (Hint: factorial(9).)
Of them, how many might possibly form the
denominator? (By my count, the number is only
about 84360 of them.)

So this is quite solvable.

John
From: Jared F on 12 Mar 2010 22:38
Thanks for the hint. Since 987654321 is the largest pan-digital number, the max denominator is 314298765. And vice-versa, since 123456789 is the smallest combination, the minimum numerator is 387695421. (These are found by using: numerator = pi * denominator).

This leaves about 80220 possible denominators like you said, but still leaves 252000 possible numerators. That's a lot of possibilities. Also, I don't know how else to come up with a string of pan-digital numbers other than using the loops I created. Is there a more efficient way?

I'm just doing problem this for fun, but yes it would be a good homework assignment. Especially with pi day just around the corner.

:)



>
> I won't do homework assignments, which this sounds
> surprisingly like. And even if this is something you wish
> to try yourself, you won't gain anything by me doing
> it for you. However, you did make a start at it, so I''ll
> give you a hint.
>
> You want to find a ratio of TWO pan-digital numbers
> that yields pi to as high an approximation as possible.
>
> Rather than looping massively as you tried, why not
> search over all denominators? How many 9 digit
> pan-digital numbers are there? (Hint: factorial(9).)
> Of them, how many might possibly form the
> denominator? (By my count, the number is only
> about 84360 of them.)
>
> So this is quite solvable.
>
> John
From: Sadik on 13 Mar 2010 08:18
Hi Jared,

Here is my version of it. The operation is limited by the available memory, as well as the maximum number of elements allowed by matlab. Therefore, the following may not be the best solution, but it could hopefully show you another direction of doing it. [It seems that the search for the optimal combination is going to take about 10 hours!]

Best.

% brainTeaser.m

allCombinations = perms(1:9);

allNumbers = zeros(size(allCombinations,1),1);

for k = 1:length(allNumbers)

for digit = 1:9

allNumbers(k) = allNumbers(k) + allCombinations(k,digit)*power(10,9-digit);

end

end

numberOfPartitions = 560; % Form blocks of numbers, each of length 9!/560
partitionLength = length(allNumbers)/numberOfPartitions;

globalMin = 1e6;

for m = 1:numberOfPartitions
firstPartition = allNumbers((m-1)*numberOfPartitions+(1:partitionLength));
disp(['Beginning partition ' num2str(m) ' of ' num2str(numberOfPartitions) '...'])
for n = 1:numberOfPartitions
secondPartition = allNumbers((n-1)*numberOfPartitions+(1:partitionLength));
matrixOfDivisions = firstPartition*(1./secondPartition');
[minValue,minLocation] = min(abs(matrixOfDivisions(:)-pi));
if minValue < globalMin
[row,col] = ind2sub(size(matrixOfDivisions),minLocation);
numerator = firstPartition(row);
denominator = secondPartition(col);
globalMin = minValue;
end

end

end


disp(['The best approximation is given by ' num2str(numerator) '/' num2str(denominator)])
disp(['The result is equal to ' num2str(numerator/denominator) ', and pi = ' num2str(pi)])











"Jared F" <jfritz408(a)yahoo.com> wrote in message <hner7u$r8m$1(a)fred.mathworks.com>...
> I came across the "brain teaser" of finding the best approximation of pi by dividing one 9-digit number by another 9-digit number. Both numbers contain 1 through 9 once.
>
> I found a very close approximation by hand (728691345 / 231948765 = 3.141604763) but I want to know if there are any better ones.
>
> I've tried a couple different methods of writing a program to find a better approximation, but all I can come up with is a massive number of loops that would take way too long for my computer to process.
>
> I'll paste my current program below. If you can think of a better way to write this, let me know. I don't have an extensive background in matlab, so I'm at a loss for how to optimize this. Thanks!
>
> Program Below
> ____________________________________
>
> for a = 3:9;
> for b = 1:9;
> for c = 1:9;
> for d = 1:9;
> for e = 1:9;
> for f = 1:9;
> for g = 1:9;
> for h = 1:9;
> for i = 1:9;
> for j = 1:9;
> for k = 1:9;
> for l = 1:9;
> for m = 1:9;
> for n = 1:9;
> for o = 1:9;
> for p = 1:9;
> for q = 1:9;
> for r = 1:9;
>
> x = 100000000.*a+10000000.*b+1000000.*c+100000.*d+10000.*e+1000.*f+100.*g+10.*h+i;
> y = 100000000.*j+10000000.*k+1000000.*l+100000.*m+10000.*n+1000.*o+100.*p+10.*q+r;
>
> z = x/y;
>
>
> if (z - pi < .001)
>
> format short;
>
> printf('x = %i\n', x);
> printf('y = %i\n', y);
> format long;
> printf('z = %i\n', z);
> disp('----------');
>
> endif
>
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
> endfor
From: John D'Errico on 13 Mar 2010 08:54
"Sadik " <sadik.hava(a)gmail.com> wrote in message <hng3aa$fr9$1(a)fred.mathworks.com>...
> Hi Jared,
>
> Here is my version of it. The operation is limited by the available memory, as well as the maximum number of elements allowed by matlab. Therefore, the following may not be the best solution, but it could hopefully show you another direction of doing it. [It seems that the search for the optimal combination is going to take about 10 hours!]
>

But then your solution will take a half day to solve.
Since I don't believe that giving a solution to someone
who is trying to learn actually helps them at all, all I
will do is to suggest that there are far better ways to
approach it.

Be creative. There is at least one solution with error
as low as:

error =
-8.49968984084626e-11

This took 11 lines of code to generate, and 0.23
seconds of cpu time.

John
 |  Next  |  Last
Pages: 1 2
Prev: Pi approximation function optimization
Next: error with intial conditions for ode45