Project Euler

[Michael Kann]

Mick, 

You beat me to it on the Fibonacci series. I also thought about using the golden ratio. Using a few other relationships allows one to compose a rather compact script.

1. the F numbers are always odd odd even, odd odd even

--- this allows you to use "step 3" in the loop
--- you will only check even numbers and stop at the last one
--- before four million

2. F1 + F2 + F3 . . . Fn = F(n+2)- 1

--- this allows you to do the summation at the end
--- If you know Fn then you just go up a couple more
--- numbers to get the sum of the first n numbers

3. If you stop the summation at F(even) then the sum of
   the even numbers will be 1/2 of the total sum

-- 1,1,TWO,3,5,EIGHT,13,21,THIRTY-FOUR
-- The two numbers sum to the EVENS (by definition)

----Here's the script -- 555 is just any large number

on mouseUp
put (1+ sqrt(5))/2 into g
repeat with n = 0 to 555 step 3
   if (g^n)/sqrt(5) > 4E6 then exit repeat 
end repeat 
put (round((g^(n-1))/sqrt(5)) - 1) / 2 
end mouseUp 
-------------------------------------
The golden ratio technique is most valuable if you want to hit a very large F number. You don't have to count up to it. It is like random access memory.



Here's another interesting property of a F series:

1 1 2 3 5 8 13 21

Take the square of 8 -- 64. It is off by one from the product 5*13. That holds for any 3 numbers in a row. Sometimes the square is one more than the products of its neighbors, sometimes one less: but always one off.  



--- On Thu, 2/25/10, Mick Collins <mickclns at mac.com> wrote:

> From: Mick Collins <mickclns at mac.com>
> Subject: Re: Project Euler
> To: use-revolution at lists.runrev.com
> Date: Thursday, February 25, 2010, 2:13 PM
> 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 <andre at andregarzia.com>
> >Subject: Project Euler
> >To: How to use Revolution <use-revolution at lists.runrev.com>
> >Message-ID:
> >    <7c87a2a11002230828ia2f0ff1s399ab3ae1b2d0c01 at mail.gmail.com>
> >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
> use-revolution at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage
> your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-revolution
>