Farey sequence: Difference between revisions

The Farey sequences of orders   '''1'''   to   '''5'''   are:

 

:<br>

:<br>

:<br>

:<br>

 

;Task

 

 

<br><br>

 

{{trans|Lua}}

 

V a = 0

V b = 1

 

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

 

{{out}}

</pre>

 

{{out}}

<pre>

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

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>

 

=={{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|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++}}==

 

}

 

}

 

return 0;

 

{{out}}

</pre>

 

 

 

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 1 to 11 do

 

(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}}

 

Farey sequence of order 100 has 3045 terms.

Farey sequence of order 900 has 246327 terms.

Farey sequence of order 1000 has 304193 terms.

</pre>

 

=={{header|Crystal}}==

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

 

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

fracs = [] of BigRational

while c <= n

a, b, c, d = c, d, k * c - a, k * d - b

fracs << BigRational.new(a,b)

puts "Farey sequence for order 1 through 11 (inclusive):"

(1..11).each do |n|

end

 

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

end

{{out}}

<pre>

Number of fractions in the Farey sequence:

</pre>

 

 

 

 

 

 

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}}==

 

 

<br> is to show the first term as &nbsp; <big>'''0/1'''</big>,

<br> and to show the last term as &nbsp; <big>'''1/1'''</big>. <br><br> }}

 

 

(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>

1000 304193

</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>

 

</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|Go}}==

 

import "fmt"

}

}

{{out}}

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

|F(1000)|: 304193

</pre>

 

=={{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)

showFracs =

unwords .

 

main :: IO ()

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}}

 

for den in 1:n, num in 1:den-1

push!(rst, Rational(num, den))

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}}

900: 246327 fractions

1000: 304193 fractions

</pre>

 

=={{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>

 

 

 

 

 

{{out}}

 

 

 

=={{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>

 

=={{header|Pascal}}==

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

nom,dom,n,c,d: longInt;

end;

function InitFarey(maxdom:longINt):tNextFarey;

Begin

end;

end;

function NextFarey(var fn:tNextFarey):boolean;

var

end;

 

var

TestF : tNextFarey;

Begin

repeat

inc(cnt);

until NOT(NextFarey(TestF));

 

repeat

{{Out}}

 

 

=={{header|Perl}}==

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 ===

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>

1000: 304193 items

</pre>

=={{header|Racket}}==

 

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}}

-- Farey Sequence for order 900 has 246327 fractions

-- Farey Sequence for order 1000 has 304193 fractions</pre>

 

=={{header|REXX}}==

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the following for input: &nbsp; &nbsp; <tt> &nbsp; 1 &nbsp; 11 </tt>}}

 

 

=={{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|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>