S&SMC #13: My Solutions & Comments [LONG] Message #41 Posted by Valentin Albillo on 5 Feb 2006, 3:07 p.m., in response to message #1 by Valentin Albillo
Hi, all:
First of all, I'm absolutely impressed with the quality & quantity of your
posted solutions to this humble challenge of mine, it's been most enjoyable
and unexpected.
Frankly, I thought for a while whether I should submit this particular challenge
or some other easier one instead, because I feared people would consider it too difficult
and too 'busy', what with eight different cases to solve. But then, on the other
hand, the subject matter seemed to me irresistibly interesting, because these sums
are truly weird, and the results are wellnigh surreal, so to say.
Why ? Well, most people knowledgeable in things mathematical have seen infinite
sums (Taylor expansions, say) where each term is defined as
some combination of elementary functions, such as trigonometrics, exponentials, or
logarithms, mixed up with powers and arithmetic operations. Even other
nonelementary functions are sometimes included as well, such as Gamma or Bessel
functions, or some integrals, things like that.
But what is one to do with functions such as the one featured in Sum #1, where
f(n) counts the number of odd digits in its argument ? How can we deal with
such a function by analytical means ? Does it have a derivative ? Can it be
integrated ? Can it be extended to arbitrary, noninteger arguments, much like the
factorial function can ?
Such weird functions, which deal more with their argument's form than with
their argument's value, so to say, seem absolutely intractable, and there's no telling what
an infinite sum of them could amount to. Math intuition would seem to suggest that
it would be some weird noname irrational value, not related to any wellknown
mathematical constants. Yet the first sum comes to 1/9 ! A simple rational !! Exactly !!!
And our amazement can only increase when the second sum, which features the twin
function who counts the number of even digits in its argument, also seems to
evaluate to a rational argument, though this time a notsosimple fraction, namely
3166/3069.
At the very least, 10digit and 12digit results exactly agree with this fraction.
JeanFrançois Garnier took my hint and came up with a 20digit sum still in
perfect agreement with the fraction. Yet, the sum does not exactly evaluate to
this fraction but comes incredibly close. Matter of fact, the sum isn't neither rational nor even irrational, but transcendental. An easilydefined, easilycomputable
transcendental number which is extremely close to the rational 3166/3069. Why this
asymmetry between the odd case (sum = 1/9, rational, exactly) and the even case
(sum = 3166/3069, extremely close approximation but actually transcendental) ?
Fear not: there's a deep mathematical reason for these unexpected evaluations, these weird
counting functions can be treated analitically, and sums #6, #7, and #8 also
have a suitable and easily understandable explanation, only this is not the place to
explain it in detail, of course. Let's go instead for the solutions proper, plus assorted comments.
My Solutions
As usual, I'll give my solutions for the HP71B, as they're easier to understand
and to translate to the programming language of any other HP models, say RPN or RPL.
First of all, we do need some way of converting decimals to fractions. JeanFrançois
Garnier used the FRAC$ function available in the HP71B's JPC ROM, but that's hardly
portable to most other HP machines so here's a 5line DEC2FRC (Decimaltofraction) subprogram I wrote for the
occasion which will do the conversion:
100 SUB DEC2FRC(X,N,D,W) @ IF X=0 THEN N=0 @ D=1 @ END
110 U=0 @ V=1 @ N=1 @ D=0 @ Y=INF @ Z=ABS(X) @ F=SGN(X) @ X=Z @ W=ABS(W)
120 C=INT(X) @ IF FP(X)=0 THEN N=N*F @ END ELSE X=1/FP(X) @ S=N @ T=D
130 N=N*C+U @ U=S @ D=D*C+V @ V=T @ R=N/D @ IF ABS(R/Z1)<W THEN N=N*F @ END
140 IF R=Y OR MAX(N,D)>1.E+12 THEN N=U*F @ D=V @ END ELSE Y=R @ GOTO 120
This subprogram is based on the continued fraction expansion of the given decimal
number, and it simply computes the subsequent approximants till the tolerance
is met, returning the last one. It works for most any argument within range, regardless of its sign or value.
To use it, you simply call DEC2FRC, passing it the following parameters:
X: passed by value, is the decimal number to convert to fractional form
N: passed by reference, is the variable where the numerator will be returned
D: passed by reference, is the variable where the denominator will be returned
W: passed by value, is a tolerance value which lets you control the
relative error of the fraction so you can get smaller
fractions which still result in acceptable errors;
specifying this tolerance as 0 will return the most
precise fraction (smallest error) found
For example, let's convert PI to fractional form calling DEC2FRC from
the command line:
>CALL DEC2FRC(PI,N,D,0) @ N,D,N/D,PI
1146408 364913 3.14159265359 3.14159265359
so our fraction is 1146408/364913, which agrees with PI to 12 digits.
Let's suppose that we don't want so close an approximation, but prefer
instead a simpler fraction. We'll call DEC2FRC again, but this time
we'll specify a tolerance of 0.00001 for the maximum relative error:
>CALL DEC2FRC(PI,N,D,1E5) @ N,D,N/D,PI
355 113 3.14159292035 3.14159265359
and so this time our fraction is 355/113, which agrees with PI to nearly
8 digits, far better than our tolerance would have us believe. So our subprogram
does work, and you can freely use it in your own programs which require fraction
output. As for the sums themselves:
Sum #1:
S = SUM( N = 1, N > Inf, f(2^n)/2^n )
where f(N) counts the number of odd digits (i.e.: 1,3,5,7,9) in N
Our main program will be:
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 12/LGT(2) @ X=2^N
20 S=S+FNF(X,"13579")/X @ NEXT N @ CALL DEC2FRC((S),N,D,.000000001)
30 DISP USING "K,Z.10D,K,K,A,K";"Sum = ";S," = ",N,"/";D @ END
where FNF is a userdefined function that accept two parameters, the
number whose digits will be counted, and a string argument specifying
the digits to count. As we want to count the number of odd digits in N,
we supply "13579" as the second parameter. Thus, FNF is defined so:
50 DEF FNF(X,D$) @ S$=STR$(X) @ C=0 @ FOR I=1 TO LEN(S$)
60 C=C+(POS(D$,S$[I,I])#0) @ NEXT I @ FNF=C @ END DEF
which you can test from the keyboard, if desired. This very same function
will be reused for Sum #2. Notice that the main program sums from N=1
to N=12/LGT(2). This is so because we don't want 2^N to be more than 12
digits in length, which is the maximum size for an exact integer argument in
the 12digit HP71B's BASIC. Else, the count function would return wrong
results.
Upon running the program we get:
>RUN
Sum = 0.1111111111 = 1/9
This is indeed the *exact* result, a nice rational sum.
Sum #2:
S = SUM( N = 1, N > Inf, f(2^n)/2^n )
where f(N) counts the number of even digits (i.e.: 0,2,4,6,8) in N
Our program and userdefined function are exactly the same, except in
line 20 the string "13579" should be replaced by "02468".
Upon running it we get:
>RUN
Sum = 1.0316063865 = 3166/3069
This result is only approximate, but correct to 31 decimal digits (!!)
Actually, we have:
Exact value = 1.031606386445096122515477354187 130310+
3166/3069 = 1.031606386445096122515477354187 031606+
and you can see that the true sum agrees with our fraction 3166/3069 to 31
decimal digits, but differs afterwards. Thus, the true sum for the even case
is a transcendental number, but extremely close to a simple rational. This
is in contrast with the sum for the odd case, which is exactly rational.
Sum #3:
S = SUM( N = 1, N > Inf, f(2^n)/2^n ) = 114/1025
where f(N) = 1 is N has an even number of digits, 0 otherwise
Our main program is extremely similar to the one for #1 and #2, and the
userdefined function is much simpler:
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 12/LGT(2) @ X=2^N
20 S=S+FNF(X)/X @ NEXT N @ CALL DEC2FRC((S),N,D,.000000001)
30 DISP USING "K,Z.10D,K,K,A,K";"Sum = ";S," = ",N,"/";D @ END
40 !
50 DEF FNF(X)=1MOD(LEN(STR$(X)),2)
Upon running it, we get:
>RUN
Sum = 0.1112195122 = 114/1025
Once again, this result is only approximate, but correct to 30 digits !
In fact, we have:
Exact value = 0.11 12195 12195 12195 12195 12195 12204 97+
114/1025 = 0.11 12195 12195 12195 12195 12195 12195 12+
and so the exact sum, which begins mimicking a 5digit period, actually ceases
to agree with the nice fraction after 30 digits. The sum is also transcendental
and, again, extremely close to a rational value. Computing to, say, 20 or 25 digit
precision would led anyone to think that the 12195 period continued indefinitely,
it's hard to believe that, suddenly, it vanishes forever upon reaching the 30th digit !
Sum #4:
S = SUM( N = 1, N > Inf, f(2^n)/2^n ) = 1/99 (exact)
where f(N) counts the number of odd digits in odd places in the
decimal expansion of N.
In this case, our main program is exactly the same as #1, and
the userdefined function is a simple variation of the one in #1:
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 12/LGT(2) @ X=2^N
20 S=S+FNF(X,"13579")/X @ NEXT N @ CALL DEC2FRC((S),N,D,.000000001)
30 DISP USING "K,Z.10D,K,K,A,K";"Sum = ";S," = ",N,"/";D @ END
40 !
50 DEF FNF(X,D$) @ S$=STR$(X) @ C=0 @ FOR I=1 TO LEN(S$) @ J=LEN(S$)+I1
60 C=C+(POS(D$,S$[I,I]) AND MOD(J,2)) @ NEXT I @ FNF=C @ END DEF
Upon running it we get:
>RUN
Sum = 0.0101010101 = 1/99
which is the exact result. This time the sum is, as in #1, exactly rational.
Sum #5:
S = SUM( N = 1, N > Inf, f(n)/10^n )
where f(x) is the same as in Sum #4.
We only need to change these lines in our main program for #4:
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 12/LGT(2)
20 S=S+FNF(N,"13579")/10^N @ NEXT N @ CALL DEC2FRC((S),N,D,.000000001)
Upon running, it returns:
>RUN
Sum = 0.1010101010 = 10/99
where most unexpectedly, as the function is the very same and the sum is very
similar, the result is only approximate, but correct to 99 digits !!!
The true results is, again, transcendental, but this time much closer to
a rational value.
Why Sum #4 results in an exact rational (1/99) while the extremely similar
Sum #5 results in a transcendental which agrees to 99 digits with 10/99 may seem
as mysterious as the oddeven dissimilar results in Sums #1 and #2. Of course, the
"10" period dissappears upon reaching the 100th digit, but anyone computing the sum to
10, 20, 30, ..., 70, 80, 90 decimals would be adamantly convinced that it would
go on forever.
Sum #6:
S = SUM( N = 1, N > Inf, f(n)/2^n )
where f(x) = Integer part of (Pi/2 * x)
The main program is a trivial variation, and the userdefined function is
also trivial:
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 12/LGT(2)
20 S=S+FNF(N)/2^N @ NEXT N @ CALL DEC2FRC((S),N,D,.000000001)
30 DISP USING "K,Z.10D,K,K,A,K";"Sum = ";S," = ",N,"/";D @ END
40 !
50 DEF FNF(X)=INT(PI/2*X)
Upon running it we get:
>RUN
Sum = 2.6692913385 = 339/127
and, again, this result is only an approximation to the real sum, which is
transcendental. However, it's a very close approximation once more, this
time the fraction agrees with the true sum to almost 69 digits !
Exact value = 2.669291338582677165354330708661417322834645669291338582677165354330 69931+
339/127 = 2.669291338582677165354330708661417322834645669291338582677165354330 70866+
Sum #7:
S = ((SUM( N = 1, N > Inf, e^(n*n/100) )/5+0.1)^2
The main program is very simple, no need to call DEC2FRC, and the userdefined
function is trivial, too
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 50
20 S=S+FNF(N) @ NEXT N @ S=(S/5+.1)^2
30 DISP "S = ";S @ END
40 DEF FNF(X)=EXP(X*X/100)
Unpon running it, we get
>RUN
S = 3.14159265357
which makes us wonder if the exact sum would indeed be Pi. But lo and behold,
it isn't Pi but another transcendental number which nevertheless agrees with Pi
to 428 decimal places !! As my 13year old daughter Laura put it: "It looks like Pi,
it smells like Pi, it tastes like Pi, but it isn't Pi"
Exact value of the sum =
3.14159265358979323846264338327950288419716939937510582097494459230781640628620
89986280348253421170679821480865132823066470938446095505822317253594081284811174
50284102701938521105559644622948954930381964428810975665933446128475648233786783
16527120190914564856692346034861045432664821339360726024914127372458700660631558
81748815209209628292540917153643678925903600113305305488204665213841469519415116
094330572703657595919530921861 46740+
while Pi =
3.14159265358979323846264338327950288419716939937510582097494459230781640628620
89986280348253421170679821480865132823066470938446095505822317253594081284811174
50284102701938521105559644622948954930381964428810975665933446128475648233786783
16527120190914564856692346034861045432664821339360726024914127372458700660631558
81748815209209628292540917153643678925903600113305305488204665213841469519415116
094330572703657595919530921861 17381+
Sum 8:
S = SUM( N = 1, N > Inf, INT(N*e^(Pi*Sqrt(163/9)))/ 5^N)
Again, an extremely simple main program and straightforward userdefined function:
10 DESTROY ALL @ STD @ S=0 @ FOR N=1 TO 18
20 S=S+FNF(N)/5^N @ NEXT N
30 DISP "S = ";S @ END
40 DEF FNF(X)=INT(X*EXP(PI*SQRT(163/9)))
Upon running it, we get:
>RUN
S = 200100
and, as you may suspect by now, this neat integer value is too good to be true
and it's only an approximation to the exact value of the infinite sum which is
transcendental. However, there's no typing both values for you to see the
difference, because 200100 agrees with the exact sum to at least 500,000,000,000
(half a billion) decimal digits !!!!
So it's doubtful you could use your arbitrary precision math package to
empirically test this claim. Now, having such a simple sum return a result which
differs from an integer by less than 10^500000000000 is simply mindboggling !
The Prizes
Everyone who posted their solutions and estimates did extremely well, with special
mentions to Arnaud Amiel (who coded some of the functions in Saturn assembly language and later tried multiprecision),
JeanFrançois Garnier (who not only got all solutions Ok but coded special double
precision programs to compute results to double accuracy), Werner (who got all
results Ok, plus gave some math insight as to why some of them couldn't be exact),
Chris (who kept trying once and again till he got the answers),
and PeterP (who did his best with his trusty 41C).
All of you, either explicitly mentioned above or not, will receive by email whatever PDF articles you want me to send you,
please contact me either via this web site (clicking on my name at the beginning of
each post of mine) or else via my email address which you can find at my web page.
Please send a valid email address plus a list of the articles you do want, and
I'll send them to you at once.
Thanks to all of you posters and lurkers for your interest, and
Best regards from V.
