First, thanks, Andre for starting the thread and turning us / me onto the Euler
Project.
I enjoy implementing algorithms, but math is fun, too!
Since Euler was a mathematician, how about a more mathematical approach.
I haven't seen these approaches yet in my quick scan of the posts, so I will
put them out there:
For the first problem
*********** mathematical note
The number of natural numbers below X that are divisible by 3 or 5 is:
the number divisible by 3, plus the number divisible by 5, minus the number
divisible by 15 (since these number have already been counted twice).
For combining in a more general fashion, i.e. other than 3 and 5, rather than
using the multiple you would use the Least Common Multiple (not implemented
here). For instance, if you wanted the number divisible by 6 or 4, you would
use numdiv(4) + numdiv(6) - numdiv(12), since if you used numdiv(24) you would
miss subtracting off many numbers divisible by both 4 and 6 but not by 24
(12*1, 12*3, 12*5 ...)
Here is a testing routine, followed by a generalization of the problem (no
error correction). For the testing routine, as soon as you are satisfied that
it works as advertised, hold the shift key to jump out of the loop. Then it
will display the results of divisibility by 3 or 5.
on doTest
repeat until the shiftkey is down
ask "X" with 1000
put it into X
ask "N" with 3
put it into N
answer "<= or plain <" with "Eq" or "NoEq"
put it into EorNo
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult
if EorNo is "NoEq" then
put "Number < [[X]] and divisible by [[N]] is [[theResult]]." into
mergeStr
else
put "Number <= [[X]] and divisible by [[N]] is [[theResult]]." into
mergeStr
end if
answer merge(mergeStr)
end repeat
put 1000 into X
put "NoEq" into EorNo
put 3 into N
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult3
put 5 into N
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult5
put 15 into N
put numOfNumsBelowXandDivisByN(X,N,EorNo) into theResult15
put "Number < [[X]] and divisible by 3 or 5 is " & \
"[[theResult3 + theResult5 - theResult15]]." into mergeStr
answer merge(mergeStr)
end doTest
function numOfNumsBelowXandDivisByN X,N, EqOrNoEq
put X into X_
put X_ mod N into XmodN
-- X div N will be the number returned EXCEPT ...
if EqOrNoEq = "NoEq" and XmodN = 0 then -- X divisible by N and it matters
subtract 1 from X_ end if
return X_ div N
end numOfNumsBelowXandDivisByN
For the second problem
******************
The even Fibonacci numbers form a Fibonacci-like sequence
E(1) = 0, E(2) = 2, for n>2: E(n) = 4E(n-1) + E(2)
0, 2, 8, 34, 144, 610, 2584, etc.
Also, the sums of the even Fibs form a slightly less Fibonacci-like sequence
S(1) = 0, S(2)=2, S(3) = 10, for n>3: S(n) = 5*S(n-1) - 3*S(n-2) - S(n-3)
0, 2, 10, 44, 188, 798, 3382, etc.
There may be an even more direct approach to one or both of these sequences
(I don't know if there is), such as with the plain vanilla (no offense
intended) Fibonacci sequence.
The i-th member of the sequence is:
(g^i-(-1/g)^i) / rt5 where rt5 is the square root of 5 and g is the golden
ratio: ( (1+rt5)/2 ).
So that sequence can be calculated explicitly (rather than recursively).
In the testing routine, I start by displaying the explicit calculation of the
first
8 members of the Fibonacci sequence
Then the recursive method of the even Fibs, keeping track of the sums.
Then the recursive method of the sums, only using the even Fibs, by calculation
to test whether to stop.
on doTest
put sqrt(5) into rt5
put (1+rt5)/2 into g
repeat with i = 1 to 8
put (g^i-(-1/g)^i) / rt5 into theF
answer theF
end repeat
-- even Fibs sums by first method
answer "First Method"
put 2 into F1
put 8 into F2
put 10 into theSum
repeat while F2 <= 4000000
put 4*F2 + F1 into newFib
add newFib to theSum
put F2 into F1
put newFib into F2
end repeat
answer "Fib" && F1 & ", Sum" && theSum
answer "Second Method"
put 0 into S1
put 2 into S2
put 10 into S3
repeat while S3 - S2 <= 4000000
put 5*S3 - 3*S2 - S1 into newFib
put S2 into S1
put S3 into S2
put newFib into S3
end repeat
answer "Sum" && S3
end doTest
I'd welcome any comments on these.
>Date: Tue, 23 Feb 2010 13:28:37 -0300
>From: Andre Garzia <[email protected]>
>Subject: Project Euler
>To: How to use Revolution <[email protected]>
>Message-ID:
> <[email protected]>
>Content-Type: text/plain; charset=ISO-8859-1
>
>Hi There Folks,
>
>I don't know if you guys are familiar with http://www.projecteuler.net which
>is officially a very fun project according to my own concepts of fun. It is
>a repository of mathematical problems which require more than simple math to
>solve, it usually require some programming. You can go solving your problems
>and getting scores. I just solved the first one in Rev.
>
>"Add all the natural numbers below one thousand that are multiples of 3 or
>5."
>
>Now, the second one is giving me trouble... rsrsrsrs
>
>"Find the sum of all the even-valued terms in the Fibonacci sequence which
>do not exceed four million."
>
>I think I am going to reach the upper limits of rev math with it.
>
>:D
>
>--
>http://www.andregarzia.com All We Do Is Code.
>
>
>
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
