Farey sequence: Difference between revisions

 

;See also:

*   MathWorld entry   [http://mathworld.wolfram.com/FareySequence.html Farey sequence]

<br><br>

 

{{trans|Lua}}

 

V a = 0

V b = 1

 

L(i) (100..1000).step(100)

 

{{out}}

900: 246327 items

1000: 304193 items

</pre>

 

=={{header|APL}}==

farey←{{⍵[⍋⍵]}∪∊{(0,⍳⍵)÷⍵}¨⍳⍵}

fract←{1∧(0(⍵=0)+⊂⍵)*1 ¯1}

print←{{(⍕⍺),'/',(⍕⍵),' '}⌿↑fract farey ⍵}

Note that this is a brute-force algorithm, not the sequential one given on Wikipedia.

Basically, given n this one generates and then sorts the set

1000 | 304193

</pre>

 

=={{header|AWK}}==

# syntax: GAWK -f FAREY_SEQUENCE.AWK

BEGIN {

return(1+items)

}

{{out}}

<pre>

1000: 304193 items

</pre>

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

printf("\n%d: %llu items\n", n, farey_len(n));

return 0;

{{out}}

<pre>

</pre>

 

{{works with|C sharp|7}}

{{trans|Java}}

using System.Collections.Generic;

using System.Linq;

return seq;

}

{{out}}

<pre style="height:30ex;overflow:scroll">

 

=={{header|C++}}==

 

}

 

}

 

int main() {

return 0;

 

{{Works with|C++17}}

#include <list>

#include <utility>

 

struct farey_sequence: public std::list<std::pair<uint, uint>> {

uint a = 0, b = 1, c = 1, d = n;

const uint k = (n + b) / d;

const uint next_c = k * c - a;

c = next_c;

d = next_d;

}

}

 

return EXIT_SUCCESS;

 

=={{header|Common Lisp}}==

 

The common lisp version of the code is taken from the scala version with some modifications:

(labels ((helper (begin end)

(let ((med (/ (+ (numerator begin) (numerator end))

(loop for i from 100 to 1001 by 100 do

(format t "Farey sequence of order ~a has ~a terms.~%" i (length (farey i))))

{{out}}

<pre>1: 0/1 1/1

{{trans|the function from Lua, the output from Ruby.}}

Slow Version

 

def farey(n)

puts "F(%4d) =%7d" % [i, farey(i).size]

end

 

{{trans|the function from Python, the output from Ruby.}}

Fast Version

 

def farey(n, length = false)

puts "F(%4d) =%7d" % [i, farey(i, true)]

end

 

{{out}}

 

 

 

 

 

auto farey(in int n) pure nothrow @safe {

writeln("\nFarey sequence fractions, 100 to 1000 by hundreds:\n",

iota(100, 1_001, 100).map!(i => i.farey.walkLength));

{{out}}

<pre>Farey sequence for order 1 through 11:

 

Farey sequence fractions, 100 to 1000 by hundreds:

This is as fast as the C entry (total run-time is 0.20 seconds).

{{trans|C}}

 

void farey(in uint n) nothrow @nogc {

immutable uint n = 10_000_000;

printf("\n%u: %llu items\n", n, fareyLength(n, cache));

{{out}}

<pre>1: 0/1 1/1

 

10000000: 30396356427243 items</pre>

 

=={{header|EchoLisp}}==

 

 

(define distinct-divisors

(compose make-set prime-factors))

(make-set (for*/list ((n N) (d (in-range n N))) (rational n d))))

 

{{out}}

(for ((n (in-range 1 12))) ( printf "F(%d) %s" n (Farey n)))

F(1) { 0 1 }

|F(10000)| = 30397487

|F(100000)| = 3039650755

 

=={{header|EDSAC order code}}==

The code is slightly simplified by adding a formal term -1/0 before the first term 0/1.

The second term can then be included in the calculation loop.

[Farey sequence for Rosetta Code website.

EDSAC program, Initial Orders 2.

E 27 Z [define start of execution]

P F [start with accumulator = 0]

{{out}}

<pre>

=== Count terms ===

Counts the terms by summing Euler's totient function.

[Farey sequence for Rosetta Code website.

Get number of terms by using Euler's totient function.

E 32 Z [define start of execution]

P F [start with accumulator = 0]

{{out}}

<pre>

=={{header|Factor}}==

Factor's <code>ratio</code> type automatically reduces fractions such as <code>0/1</code> and <code>1/1</code> to integers, so we print those separately at the beginning and ending of every sequence. This implementation makes use of the algorithm for calculating the next term from the wiki page [https://en.wikipedia.org/wiki/Farey_sequence#Next_term]. It also makes use of Euler's totient function for recursively calculating the length [https://en.wikipedia.org/wiki/Farey_sequence#Sequence_length_and_index_of_a_fraction].

locals prettyprint sequences sequences.extras sets tools.time ;

IN: rosetta-code.farey-sequence

: main ( -- ) [ part1 part2 nl ] time ;

 

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>F1 = 0/1 1/1

=={{header|FunL}}==

Translation of Python code at [http://en.wikipedia.org/wiki/Farey_sequence#Next_term].

res = seq()

a, b, c, d = 0, 1, 1, n

 

for i <- 100..1000 by 100

 

{{out}}

1000: 304193

</pre>

 

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|Go}}==

 

import "fmt"

}

}

{{out}}

<pre>F(1): 0/1 1/1

=={{header|Haskell}}==

Generating an n'th order Farey sequence follows the algorithm described in Wikipedia. However, for fun, to generate a list of Farey sequences we generate only the highest order sequence, creating the rest by successively pruning the original.

import Data.Ratio ((%), denominator, numerator)

import Text.Printf (PrintfArg, printf)

fprint "%2d %s\n" $ fareys showFracs [1 .. 11]

putStrLn "\nSequence Lengths\n"

Output:

<pre>Farey Sequences

=={{header|J}}==

 

 

 

 

=={{header|Java}}==

{{works with|Java|1.5+}}

This example uses the fact that it generates the fraction candidates from the bottom up as well as <code>Set</code>'s internal duplicate removal (based on <code>Comparable.compareTo</code>) to get rid of un-reduced fractions. It also uses <code>TreeSet</code> to sort based on the value of the fraction.

 

public class Farey{

}

}

{{out}}

<pre>F1: [0/1, 1/1]

F900: 246327 members

F1000: 304193 members</pre>

 

=={{header|Julia}}==

{{trans|Java}}

 

function farey(n::Int)

for n in 100:100:1000

println("F_$n has ", length(farey(n)), " fractions")

 

{{out}}

 

=={{header|Kotlin}}==

 

fun farey(n: Int): List<String> {

for (i in 100..1000 step 100)

println("${"%4d".format(i)}: ${"%6d".format(farey(i).size)} fractions")

 

{{out}}

 

=={{header|langur}}==

var .a, .b, .c, .d = 0, 1, 1, .n

while[=[[0, 1]]] .c <= .n {

val .k = (.n + .b) // .d

_while ~= [[.a, .b]]

}

}

 

 

for .i = 100; .i <= 1000; .i += 100 {

writeln $"\.i:4;: ", len(.farey(.i))

 

=={{header|Lua}}==

function farey (n)

local a, b, c, d, k = 0, 1, 1, n

print()

end

{{out}}

<pre>1: 0/1 1/1

 

=={{header|Maple}}==

farey_sequence := proc(n)

 

#Returns the length of a Farey sequence

farey_len := proc(n)

end proc;

 

for i to 11 do

end do;

printf("\n");

for j from 100 to 1000 by 100 do

<pre>

0/1, 1/1

</pre>

 

FareySequence is a built-in command in the Wolfram Language. However, we have to reformat the output to match the requirements.

TableForm[farey/@Range[11]]

{{out}}

<pre>0/1, 1/1

 

{3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193}</pre>

 

=={{header|Nim}}==

{{trans|D}}

 

proc farey(n: int) =

 

let n = 10_000_000

{{out}}

<pre>

 

=={{header|PARI/GP}}==

countFarey(n)=1+sum(k=1, n, eulerphi(k));

{{out}}

 

%1 = [3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193]</pre>

Using a function, to get next in Farey sequence. calculated as stated in wikipedia article, see Lua [[http://rosettacode.org/wiki/Farey_sequence#Lua]].

So there is no need to store them in a big array..

{$IFDEF FPC }{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}

uses

inc(cnt,100);

until cnt > 1000;

{{Out}}

<pre style ="horizontal=85">

This uses the recurrence from Concrete Mathematics exercise 4.61 to create them quickly (this is also on the Wikipedia page). It also uses the totient sum to quickly get the counts.

{{libheader|ntheory}}

use strict;

use Math::BigRat;

for (1 .. 10, 100000) {

print "F${_}00: ", farey_count(100*$_), " members\n";

{{out}}

<pre>

=== Mapped Rationals ===

Similar to Pari and Raku. Same output, quite slow. Using the recursive formula for the count, utilizing the Memoize module, would be a big help.

use strict;

use Math::BigRat;

my @f = farey(100*$_);

print "F${_}00: ", scalar(@f), " members\n";

 

=={{header|Phix}}==

{{trans|AWK}}

{{out}}

<pre>

{3045,12233,27399,48679,76117,109501,149019,194751,246327,304193}

</pre>

 

=={{header|Prolog}}==

The following uses SWI-Prolog's rationals (rdiv(p,q)) and assumes the availability of predsort/3.

The presentation is top-down.

between(1, 11, I),

farey(I, F),

rcompare(<, A, B) :- A < B, !.

rcompare(>, A, B) :- A > B, !.

Interactive session:<pre>?- task(1).

1: 0/1, 1/1

 

=={{header|PureBasic}}==

 

Structure farey_struc

order+v_step

Wend

{{out}}

<pre>Input-> start end step [start>=1; end<=1000; step>=1; (start<end)] : 1 12 1

 

=={{header|Python}}==

 

 

print(farey(n))

print('Number of fractions in the Farey sequence for order 100 through 1,000 (inclusive) by hundreds:')

 

{{out}}

And as an alternative to importing the Fraction library, we can also sketch out a Ratio type of our own:

{{Works with|Python|3.7}}

 

from itertools import (chain, count, islice)

 

if __name__ == '__main__':

{{Out}}

<pre>Farey sequence for orders 1-11 (inclusive):

900 -> 246327

1000 -> 304193</pre>

 

=={{header|R}}==

farey <- function(n, length_only = FALSE) {

a <- 0

farey(i, length_only = TRUE)

}

{{out}}

<pre>

 

Once again, racket's ''math/number-theory'' package comes to the rescue!

(require math/number-theory)

(define (display-farey-sequence order show-fractions?)

; compute and display the number of fractions in the Farey sequence for order:

; 100 through 1,000 (inclusive) by hundreds.

 

{{out}}

<!-- bug bites at farey(362): sub farey ($order) { unique 0/1, |(1..$order).map: { |(1..$^d).map: { $^n/$d } } } -->

 

my @l = 0/1, 1/1;

(2..$order).map: { push @l, |(1..$^d).map: { $_/$d } }

say "Farey sequence order ";

.say for (1..11).hyper(:1batch).map: { "$_: ", .&farey.sort.map: *.nude.join('/') };

{{out}}

<pre>Farey sequence order

=={{header|REXX}}==

Programming note: &nbsp; if the 1^st argument is negative, &nbsp; then only the count of the fractions is shown.

parse arg LO HI INC . /*obtain optional arguments from the CL*/

if LO=='' | LO=="," then LO= 1 /*Not specified? Then use the default.*/

else $= $ _ /*No? Keep it & keep building.*/

end /*k*/

This REXX program makes use of &nbsp; '''linesize''' &nbsp; REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).

 

 

=={{header|Ring}}==

# Project : Farey sequence

 

ok

return count

Output:

<pre>

F900 = 246327

F1000 = 304193

</pre>

 

=={{header|Ruby}}==

{{trans|Python}}

if length

(n*(n+3))/2 - (2..n).sum{|k| farey(n/k, true)}

for i in (100..1000).step(100)

puts "F(%4d) =%7d" % [i, farey(i, true)]

 

{{out}}

F( 900) = 246327

F(1000) = 304193

</pre>

 

=={{header|Scala}}==

object FareySequence {

 

 

}

 

{{out}}

=={{header|Scheme}}==

 

(import (scheme base)

(scheme write))

(number->string (farey-sequence i #f))))

(newline))

 

{{out}}

 

=={{header|Sidef}}==

1 + sum(1..n, {|k| euler_phi(k) })

}

for n in (100..1000 -> by(100)) {

say ("F(%4d) =%7d" % (n, farey_count(n)))

{{out}}

<pre>

=={{header|Stata}}==

 

function totient(n_) {

n = n_

 

map(&farey_length(),100*(1..10))

 

'''Output'''

=={{header|Swift}}==

Class with computed properties:

let n: Int

 

let m = n * 100

print("\(m): \(Farey(m).sequence.count)")

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

proc farey {n} {

for {set i 100} {$i <= 1000} {incr i 100} {

puts |F($i)|\x20=\x20[llength [farey $i]]

{{out}}

<pre>

</pre>

 

=={{header|Vala}}==

{{trans|Nim}}

public uint d;

public uint n;

for (uint n = 100; n <= 1000; n += 100)

print("%8u: %14u items\n", n, fareyLength(n, cache));

 

{{out}}

1000: 304193 items

</pre>

 

=={{header|Wren}}==

{{trans|Go}}

{{libheader|Wren-math}}

{{libheader|Wren-fmt}}

{{libheader|Wren-rat}}

 

var f //recursive

sum = sum + tot[n]

if (n%100 == 0) System.print("F(%(Fmt.d(4, n))): %(Fmt.dc(7, sum))")

 

{{out}}

F(1000): 304,193

</pre>

 

=={{header|zkl}}==

{{trans|C}}

f1,f2:=T(0,1),T(1,n); // fraction is (num,dnom)

print("%d/%d %d/%d".fmt(0,1,1,n));

}

println();

{{out}}

<pre>

11: 0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1

</pre>

var cache=Dictionary(); // 107 keys to 1,000; 6323@10,000,000

if(z:=cache.find(n)) return(z);

}

cache[n]=len; // len is returned

println("%4d: %7,d items".fmt(n,farey_len(n)));

}

n:=0d10_000_000;

{{out}}

<pre>