How to resolve the algorithm Farey sequence step by step in the Factor programming language

Published on 12 May 2024 09:40 PM
#Factor

How to resolve the algorithm Farey sequence step by step in the Factor programming language

Table of Contents

Problem Statement

The   Farey sequence   Fn   of order   n   is the sequence of completely reduced fractions between   0   and   1   which, when in lowest terms, have denominators less than or equal to   n,   arranged in order of increasing size. The   Farey sequence   is sometimes incorrectly called a   Farey series.

Each Farey sequence:

The Farey sequences of orders   1   to   5   are:

The length   (the number of fractions)   of a Farey sequence asymptotically approaches:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Farey sequence step by step in the Factor programming language

Source code in the factor programming language

USING: formatting io kernel math math.primes.factors math.ranges
locals prettyprint sequences sequences.extras sets tools.time ;
IN: rosetta-code.farey-sequence

! Given the order n and a farey pair, calculate the next member
! of the sequence.
:: p/q ( n a/b c/d -- p/q )
    a/b c/d [ >fraction ] bi@ :> ( a b c d )
    n b + d / >integer [ c * a - ] [ d * b - ] bi / ;
    
: print-farey ( order -- )
    [ "F(%-2d): " printf ] [ 0 1 pick / ] bi "0/1 " write
    [ dup 1 = ] [ dup pprint bl 3dup p/q [ nip ] dip ] until
    3drop "1/1" print ;
    
: φ ( n -- m ) ! Euler's totient function
    [ factors members [ 1 swap recip - ] map-product ] [ * ] bi ;
    
: farey-length ( order -- length )
   dup 1 = [ drop 2 ]
   [ [ 1 - farey-length ] [ φ ] bi + ] if ;
   
: part1 ( -- ) 11 [1,b] [ print-farey ] each nl ;

: part2 ( -- )
    100 1,000 100 <range>
    [ dup farey-length "F(%-4d): %-6d members.\n" printf ] each ;
    
: main ( -- ) [ part1 part2 nl ] time ;

MAIN: main

You may also check:How to resolve the algorithm Monty Hall problem step by step in the R programming language
You may also check:How to resolve the algorithm Knapsack problem/Unbounded step by step in the C programming language
You may also check:How to resolve the algorithm Cullen and Woodall numbers step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Operator precedence step by step in the Haskell programming language
You may also check:How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the PL/I programming language