Paste: PE #73

Author: elasticdog factor Tue, 11 Nov 2008 03:26:11
Plain Text |
```! Copyright (c) 2008 Aaron Schaefer.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel locals make math project-euler.common sequences ;
IN: project-euler.073

! http://projecteuler.net/index.php?section=problems&id=73

! DESCRIPTION
! -----------

! Consider the fraction, n/d, where n and d are positive integers. If n<d and
! HCF(n,d) = 1, it is called a reduced proper fraction.

! If we list the set of reduced proper fractions for d <= 8 in ascending order of
! size, we get:

!     1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8,
!     2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

! It can be seen that there are 3 fractions between 1/3 and 1/2.

! How many fractions lie between 1/3 and 1/2 in the sorted set of reduced
! proper fractions for d <= 10,000?

! SOLUTION
! --------

! Use the properties of a Farey sequence by setting an upper bound of 3/7 and
! then taking the mediant of that fraction and the one to its immediate left
! repeatedly until the denominator is as close to 1000000 as possible without
! going over.

<PRIVATE

! MESSY STACK SHUFFLING, NEED RECURSION HELP?

: (euler073) ( limit lo hi -- )
pick [ 2dup mediant denominator ] dip <= [
2dup mediant dup , tuck swap [ pick ] 2dip (euler073) (euler073)
] [ 3drop ] if ;

! SLIGHTLY CLEANER USING LOCALS, STILL NOT OPTIMAL

:: (euler073a) ( limit lo hi -- )
lo hi mediant denominator limit <= [
lo hi mediant dup ,
[ [ limit lo ] dip (euler073a) ]
[ [ limit ] dip hi (euler073a) ] bi
] when ;

PRIVATE>

: euler073 ( -- answer )
[ 10000 1/3 1/2 (euler073a) ] { } make length ;

! Takes about 30 seconds right now, either way...any suggestions?```

Annotation: mediant word

Author: elasticdog factor Tue, 11 Nov 2008 03:27:28
Plain Text |
```USING: math math.ratios ;

: mediant ( a/c b/d -- (a+b)/(c+d) )
2>fraction [ + ] 2bi@ / ;```

Annotation: using [let

Author: elasticdog factor Tue, 11 Nov 2008 03:45:34
Plain Text |
```<PRIVATE

:: (euler073) ( limit lo hi -- )
[let | m [ lo hi mediant ] |
m denominator limit <= [
m ,
limit lo m (euler073)
limit m hi (euler073)
] when
] ;

PRIVATE>

: euler073 ( -- answer )
[ 10000 1/3 1/2 (euler073) ] { } make length ;```

Annotation: without let

Author: slava factor Tue, 11 Nov 2008 03:49:11
Plain Text |
```:: (euler073) ( limit lo hi -- )
lo hi mediant dup denominator limit <= [
[ , ]
[ [ limit lo ] dip (euler073) ]
[ [ limit ] dip hi (euler073) ]
tri
] when ;```

New Annotation

Summary: actionscriptada95antlrapacheconfapdlapplescriptaspaspect-jassembly-m68kassembly-macro32assembly-parrotassembly-r2000assembly-x86awkbbatchbbjbcelbeanshellbibtexcc#c++chillcilclipscobolcoldfusioncsscsvcudacvs-commitddjangodoxygendsssleiffelembperlerlangfactorfhtmlforthfortranfoxprofreemarkergettextgnuplotgroovyhaskellhexhlslhtaccesshtmli4gliconidlinforminiinno-setupinterlisiojavajavaccjavascriptjcljhtmljmkjsplatexlilypondlispliterate-haskelllotosluamailmakefilemaplemlmodula3moinmqscmyghtymysqlnetrexxnqcnsis2objective-cobjectrexxoccamomnimarkpascalpatchperlphppikepl-sqlpl1pop11postscriptpovraypowerdynamoprogressprologpropertiespspptlpvwavepyrexpythonrcprdrebolredcoderelax-ng-compactrenderman-ribrestrfcrhtmlrpm-specrtfrubyrviews#s+sasschemesdl/prsgmlshellscriptshtmlslatesmalltalksmi-mibsql-loadersqrsquidconfsvn-commitswigtcltemplate-toolkittextexinfotexttpltransact-sqltwikityposcriptuscriptvbscriptvelocityverilogvhdlxmlxqxslzpt