Yellowstone sequence: Difference between revisions
(→{{header|JavaScript}}: Added a JS draft. (No plot yet).) |
|||
Line 236: | Line 236: | ||
{{Out}} |
{{Out}} |
||
<pre>[1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17]</pre> |
<pre>[1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17]</pre> |
||
=={{header|JavaScript}}== |
|||
{{Trans|Python}} |
|||
<lang javascript>(() => { |
|||
'use strict'; |
|||
// yellowstone :: Generator [Int] |
|||
function* yellowStone() { |
|||
// A non finite stream of terms in the |
|||
// Yellowstone permutation of the natural numbers. |
|||
// OEIS A098550 |
|||
const nextWindow = ([p2, p1, rest]) => { |
|||
const [rp2, rp1] = [p2, p1].map( |
|||
relativelyPrime |
|||
); |
|||
const go = xxs => { |
|||
const [x, xs] = Array.from( |
|||
uncons(xxs).Just |
|||
); |
|||
return rp1(x) && !rp2(x) ? ( |
|||
Tuple(x)(xs) |
|||
) : secondArrow(cons(x))( |
|||
go(xs) |
|||
); |
|||
}; |
|||
return [p1, ...Array.from(go(rest))]; |
|||
}; |
|||
const A098550 = fmapGen(x => x[1])( |
|||
iterate(nextWindow)( |
|||
[2, 3, enumFrom(4)] |
|||
) |
|||
); |
|||
yield 1 |
|||
yield 2 |
|||
while (true)(yield A098550.next().value) |
|||
}; |
|||
// relativelyPrime :: Int -> Int -> Bool |
|||
const relativelyPrime = a => |
|||
// True if a is relatively prime to b. |
|||
b => 1 === gcd(a)(b); |
|||
// ------------------------TEST------------------------ |
|||
const main = () => console.log( |
|||
take(30)( |
|||
yellowStone() |
|||
) |
|||
); |
|||
// -----------------GENERIC FUNCTIONS------------------ |
|||
// Just :: a -> Maybe a |
|||
const Just = x => ({ |
|||
type: 'Maybe', |
|||
Nothing: false, |
|||
Just: x |
|||
}); |
|||
// Nothing :: Maybe a |
|||
const Nothing = () => ({ |
|||
type: 'Maybe', |
|||
Nothing: true, |
|||
}); |
|||
// Tuple (,) :: a -> b -> (a, b) |
|||
const Tuple = a => |
|||
b => ({ |
|||
type: 'Tuple', |
|||
'0': a, |
|||
'1': b, |
|||
length: 2 |
|||
}); |
|||
// abs :: Num -> Num |
|||
const abs = |
|||
// Absolute value of a given number - without the sign. |
|||
Math.abs; |
|||
// cons :: a -> [a] -> [a] |
|||
const cons = x => |
|||
xs => Array.isArray(xs) ? ( |
|||
[x].concat(xs) |
|||
) : 'GeneratorFunction' !== xs |
|||
.constructor.constructor.name ? ( |
|||
x + xs |
|||
) : ( // cons(x)(Generator) |
|||
function*() { |
|||
yield x; |
|||
let nxt = xs.next() |
|||
while (!nxt.done) { |
|||
yield nxt.value; |
|||
nxt = xs.next(); |
|||
} |
|||
} |
|||
)(); |
|||
// enumFrom :: Enum a => a -> [a] |
|||
function* enumFrom(x) { |
|||
// A non-finite succession of enumerable |
|||
// values, starting with the value x. |
|||
let v = x; |
|||
while (true) { |
|||
yield v; |
|||
v = 1 + v; |
|||
} |
|||
} |
|||
// fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b] |
|||
const fmapGen = f => |
|||
function*(gen) { |
|||
let v = take(1)(gen); |
|||
while (0 < v.length) { |
|||
yield(f(v[0])) |
|||
v = take(1)(gen) |
|||
} |
|||
}; |
|||
// gcd :: Int -> Int -> Int |
|||
const gcd = x => y => { |
|||
const |
|||
_gcd = (a, b) => (0 === b ? a : _gcd(b, a % b)), |
|||
abs = Math.abs; |
|||
return _gcd(abs(x), abs(y)); |
|||
}; |
|||
// iterate :: (a -> a) -> a -> Gen [a] |
|||
const iterate = f => |
|||
function*(x) { |
|||
let v = x; |
|||
while (true) { |
|||
yield(v); |
|||
v = f(v); |
|||
} |
|||
}; |
|||
// length :: [a] -> Int |
|||
const length = xs => |
|||
// Returns Infinity over objects without finite |
|||
// length. This enables zip and zipWith to choose |
|||
// the shorter argument when one is non-finite, |
|||
// like cycle, repeat etc |
|||
(Array.isArray(xs) || 'string' === typeof xs) ? ( |
|||
xs.length |
|||
) : Infinity; |
|||
// secondArrow :: (a -> b) -> ((c, a) -> (c, b)) |
|||
const secondArrow = f => xy => |
|||
// A function over a simple value lifted |
|||
// to a function over a tuple. |
|||
// f (a, b) -> (a, f(b)) |
|||
Tuple(xy[0])( |
|||
f(xy[1]) |
|||
); |
|||
// take :: Int -> [a] -> [a] |
|||
// take :: Int -> String -> String |
|||
const take = n => |
|||
// The first n elements of a list, |
|||
// string of characters, or stream. |
|||
xs => 'GeneratorFunction' !== xs |
|||
.constructor.constructor.name ? ( |
|||
xs.slice(0, n) |
|||
) : [].concat.apply([], Array.from({ |
|||
length: n |
|||
}, () => { |
|||
const x = xs.next(); |
|||
return x.done ? [] : [x.value]; |
|||
})); |
|||
// uncons :: [a] -> Maybe (a, [a]) |
|||
const uncons = xs => { |
|||
// Just a tuple of the head of xs and its tail, |
|||
// Or Nothing if xs is an empty list. |
|||
const lng = length(xs); |
|||
return (0 < lng) ? ( |
|||
Infinity > lng ? ( |
|||
Just(Tuple(xs[0])(xs.slice(1))) // Finite list |
|||
) : (() => { |
|||
const nxt = take(1)(xs); |
|||
return 0 < nxt.length ? ( |
|||
Just(Tuple(nxt[0])(xs)) |
|||
) : Nothing(); |
|||
})() // Lazy generator |
|||
) : Nothing(); |
|||
}; |
|||
// MAIN --- |
|||
return main(); |
|||
})();</lang> |
|||
{{Out}} |
|||
<pre>1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
Revision as of 01:12, 24 February 2020
The Yellowstone sequence, also called the Yellowstone permutation, is defined as:
For n <= 3,
a(n) = n.
For n >= 4,
a(n) = the smallest number not already in sequence such that a(n) is relatively prime to a(n-1) and is not relatively prime to a(n-2).
The sequence is a permutation of the natural numbers, and gets its name from what its authors felt was a spiking, geyser like appearance of a plot of the sequence.
- Example
a(4) is 4 because 4 is the smallest number following 1, 2, 3 in the sequence that is relatively prime to the entry before it (3), and is not relatively prime to the number two entries before it (2).
- Task
- Find and show as output the first 30 Yellowstone numbers.
- Extra
- Demonstrate how to plot, with x = n and y coordinate a(n), the first 100 Yellowstone numbers.
- Related tasks
- See also
-
- The OEIS entry: A098550 The Yellowstone permutation.
- Applegate et al, 2015: The Yellowstone Permutation [1].
Factor
<lang factor>USING: accessors assocs colors.constants combinators.short-circuit io kernel math prettyprint sequences sets ui ui.gadgets ui.gadgets.charts ui.gadgets.charts.lines ;
- yellowstone? ( n hs seq -- ? )
{ [ drop in? not ] [ nip last gcd nip 1 = ] [ nip dup length 2 - swap nth gcd nip 1 > ] } 3&& ;
- next-yellowstone ( hs seq -- n )
[ 4 ] 2dip [ 3dup yellowstone? ] [ [ 1 + ] 2dip ] until 2drop ;
- next ( hs seq -- hs' seq' )
2dup next-yellowstone [ suffix! ] [ pick adjoin ] bi ;
- <yellowstone> ( n -- seq )
[ HS{ 1 2 3 } clone dup V{ } set-like ] dip dup 3 <= [ head nip ] [ 3 - [ next ] times nip ] if ;
! Show first 30 Yellowstone numbers.
"First 30 Yellowstone numbers:" print 30 <yellowstone> [ pprint bl ] each nl
! Plot first 100 Yellowstone numbers.
chart new { { 0 100 } { 0 175 } } >>axes line new COLOR: blue >>color 100 <iota> 100 <yellowstone> zip >>data add-gadget "Yellowstone numbers" open-window</lang>
- Output:
First 30 Yellowstone numbers: 1 2 3 4 9 8 15 14 5 6 25 12 35 16 7 10 21 20 27 22 39 11 13 33 26 45 28 51 32 17
Go
This uses Gnuplot-X11 to do the plotting rather than a third party Go plotting library. <lang go>package main
import (
"fmt" "log" "os/exec"
)
func gcd(x, y int) int {
for y != 0 { x, y = y, x%y } return x
}
func yellowstone(n int) []int {
m := make(map[int]bool) a := make([]int, n+1) for i := 1; i < 4; i++ { a[i] = i m[i] = true } min := 4 for c := 4; c <= n; c++ { for i := min; ; i++ { if !m[i] && gcd(a[c-1], i) == 1 && gcd(a[c-2], i) > 1 { a[c] = i m[i] = true if i == min { min++ } break } } } return a[1:]
}
func check(err error) {
if err != nil { log.Fatal(err) }
}
func main() {
x := make([]int, 100) for i := 0; i < 100; i++ { x[i] = i + 1 } y := yellowstone(100) fmt.Println("The first 30 Yellowstone numbers are:") fmt.Println(y[:30]) g := exec.Command("gnuplot", "-persist") w, err := g.StdinPipe() check(err) check(g.Start()) fmt.Fprintln(w, "unset key; plot '-'") for i, xi := range x { fmt.Fprintf(w, "%d %d\n", xi, y[i]) } fmt.Fprintln(w, "e") w.Close() g.Wait()
}</lang>
- Output:
The first 30 Yellowstone numbers are: [1 2 3 4 9 8 15 14 5 6 25 12 35 16 7 10 21 20 27 22 39 11 13 33 26 45 28 51 32 17]
Haskell
<lang haskell>import Data.List (unfoldr)
yellowstone :: [Integer] yellowstone = 1 : 2 : 3 : unfoldr (Just . f) (2,3,[4..]) where
f :: (Integer, Integer, [Integer]) -> (Integer, (Integer, Integer, [Integer])) f (p2, p1, rest) = (next, (p1, next, rest_)) where (next, rest_) = select rest select :: [Integer] -> (Integer, [Integer]) select (x:xs) | gcd x p1 == 1 && gcd x p2 /= 1 = (x, xs) | otherwise = (y, x:ys) where (y, ys) = select xs
main :: IO () main = print $ take 30 yellowstone</lang>
- Output:
[1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17]
A variation on the definition of the Yellowstone permutation (in terms of iterate, as an alternative to unfoldr), and a basic chart of the first 100 terms. (Plotting tested only on Haskell for Mac).
<lang haskell>{-# LANGUAGE FlexibleContexts, TypeFamilies #-}
module Yellowstone where
import qualified Graphics.SVGFonts.ReadFont as F import Graphics.Rendering.Chart.Backend.Diagrams import Graphics.Rendering.Chart.Easy import Diagrams.Backend.Rasterific import Diagrams.Prelude import Codec.Picture import Control.Arrow (second)
YELLOWSTONE PERMUTATION------------------
yellowstone :: [Integer] yellowstone = 1 : 2 : (active <$> iterate nextWindow (2, 3, [4 ..]))
where nextWindow :: (Integer, Integer, [Integer]) -> (Integer, Integer, [Integer]) nextWindow (p2, p1, rest) = let [rp2, rp1] = relativelyPrime <$> [p2, p1] go (x:xs) | (rp1 x && not (rp2 x)) = (x, xs) | otherwise = second ((:) x) (go xs) (n, residue) = go rest in (p1, n, residue) active (_, x, _) = x
relativelyPrime :: Integer -> Integer -> Bool relativelyPrime a b = 1 == gcd a b
30 FIRST TERMS, AND CHART OF FIRST 100-----------
main :: IO (Image PixelRGBA8) main = do
print $ take 30 yellowstone env <- chartEnv return $ chartRender env $ plot (line "Yellowstone terms" [zip [1 ..] (take 100 yellowstone)])
CHART GENERATION----------------------
chartRender
:: (Default r, ToRenderable r) => DEnv Double -> EC r () -> Image PixelRGBA8
chartRender env ec =
let (width, _) = envOutputSize env in renderDia Rasterific (RasterificOptions (mkWidth width)) $ fst $ runBackendR env (toRenderable (execEC ec))
LOCAL FONT------------------------
chartEnv :: IO (DEnv Double) chartEnv = do
sansR <- F.loadFont "SourceSansPro_R.svg" sansRB <- F.loadFont "SourceSansPro_RB.svg" let fontChosen fs = case (_font_name fs, _font_slant fs, _font_weight fs) of ("sans-serif", FontSlantNormal, FontWeightNormal) -> sansR ("sans-serif", FontSlantNormal, FontWeightBold) -> sansRB return $ createEnv vectorAlignmentFns 640 400 fontChosen</lang>
- Output:
[1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17]
JavaScript
<lang javascript>(() => {
'use strict';
// yellowstone :: Generator [Int] function* yellowStone() { // A non finite stream of terms in the // Yellowstone permutation of the natural numbers. // OEIS A098550 const nextWindow = ([p2, p1, rest]) => { const [rp2, rp1] = [p2, p1].map( relativelyPrime ); const go = xxs => { const [x, xs] = Array.from( uncons(xxs).Just ); return rp1(x) && !rp2(x) ? ( Tuple(x)(xs) ) : secondArrow(cons(x))( go(xs) ); }; return [p1, ...Array.from(go(rest))]; }; const A098550 = fmapGen(x => x[1])( iterate(nextWindow)( [2, 3, enumFrom(4)] ) ); yield 1 yield 2 while (true)(yield A098550.next().value) };
// relativelyPrime :: Int -> Int -> Bool const relativelyPrime = a => // True if a is relatively prime to b. b => 1 === gcd(a)(b);
// ------------------------TEST------------------------ const main = () => console.log( take(30)( yellowStone() ) );
// -----------------GENERIC FUNCTIONS------------------
// Just :: a -> Maybe a const Just = x => ({ type: 'Maybe', Nothing: false, Just: x });
// Nothing :: Maybe a const Nothing = () => ({ type: 'Maybe', Nothing: true, });
// Tuple (,) :: a -> b -> (a, b) const Tuple = a => b => ({ type: 'Tuple', '0': a, '1': b, length: 2 });
// abs :: Num -> Num const abs = // Absolute value of a given number - without the sign. Math.abs;
// cons :: a -> [a] -> [a] const cons = x => xs => Array.isArray(xs) ? ( [x].concat(xs) ) : 'GeneratorFunction' !== xs .constructor.constructor.name ? ( x + xs ) : ( // cons(x)(Generator) function*() { yield x; let nxt = xs.next() while (!nxt.done) { yield nxt.value; nxt = xs.next(); } } )();
// enumFrom :: Enum a => a -> [a] function* enumFrom(x) { // A non-finite succession of enumerable // values, starting with the value x. let v = x; while (true) { yield v; v = 1 + v; } }
// fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b] const fmapGen = f => function*(gen) { let v = take(1)(gen); while (0 < v.length) { yield(f(v[0])) v = take(1)(gen) } };
// gcd :: Int -> Int -> Int const gcd = x => y => { const _gcd = (a, b) => (0 === b ? a : _gcd(b, a % b)), abs = Math.abs; return _gcd(abs(x), abs(y)); };
// iterate :: (a -> a) -> a -> Gen [a] const iterate = f => function*(x) { let v = x; while (true) { yield(v); v = f(v); } };
// length :: [a] -> Int const length = xs => // Returns Infinity over objects without finite // length. This enables zip and zipWith to choose // the shorter argument when one is non-finite, // like cycle, repeat etc (Array.isArray(xs) || 'string' === typeof xs) ? ( xs.length ) : Infinity;
// secondArrow :: (a -> b) -> ((c, a) -> (c, b)) const secondArrow = f => xy => // A function over a simple value lifted // to a function over a tuple. // f (a, b) -> (a, f(b)) Tuple(xy[0])( f(xy[1]) );
// take :: Int -> [a] -> [a] // take :: Int -> String -> String const take = n => // The first n elements of a list, // string of characters, or stream. xs => 'GeneratorFunction' !== xs .constructor.constructor.name ? ( xs.slice(0, n) ) : [].concat.apply([], Array.from({ length: n }, () => { const x = xs.next(); return x.done ? [] : [x.value]; }));
// uncons :: [a] -> Maybe (a, [a]) const uncons = xs => { // Just a tuple of the head of xs and its tail, // Or Nothing if xs is an empty list. const lng = length(xs); return (0 < lng) ? ( Infinity > lng ? ( Just(Tuple(xs[0])(xs.slice(1))) // Finite list ) : (() => { const nxt = take(1)(xs); return 0 < nxt.length ? ( Just(Tuple(nxt[0])(xs)) ) : Nothing(); })() // Lazy generator ) : Nothing(); };
// MAIN --- return main();
})();</lang>
- Output:
1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17
Julia
<lang julia>using Plots
function yellowstone(N)
a = [1, 2, 3] b = Dict(1 => 1, 2 => 1, 3 => 1) start = 4 while length(a) < N inseries = true for i in start:typemax(Int) if haskey(b, i) if inseries start += 1 end else inseries = false end if !haskey(b, i) && (gcd(i, a[end]) == 1) && (gcd(i, a[end - 1]) > 1) push!(a, i) b[i] = 1 break end end end return a
end
println("The first 30 entries of the Yellowstone permutation:\n", yellowstone(30))
x = 1:100 y = yellowstone(100) plot(x, y)
</lang>
- Output:
The first 30 entries of the Yellowstone permutation: [1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7, 10, 21, 20, 27, 22, 39, 11, 13, 33, 26, 45, 28, 51, 32, 17]
Perl
<lang perl>use strict; use warnings; use feature 'say';
use List::Util qw(first); use GD::Graph::bars;
use constant Inf => 1e5;
sub gcd {
my ($u, $v) = @_; while ($v) { ($u, $v) = ($v, $u % $v); } return abs($u);
}
sub yellowstone {
my($terms) = @_; my @s = (1, 2, 3); my @used = (1) x 4; my $min = 3; while (1) { my $index = first { not defined $used[$_] and gcd($_,$s[-2]) != 1 and gcd($_,$s[-1]) == 1 } $min .. Inf; $used[$index] = 1; $min = (first { not defined $used[$_] } 0..@used-1) || @used-1; push @s, $index; last if @s == $terms; } @s;
}
say "The first 30 terms in the Yellowstone sequence:\n" . join ' ', yellowstone(30);
my @data = ( [1..500], [yellowstone(500)]); my $graph = GD::Graph::bars->new(800, 600); $graph->set(
title => 'Yellowstone sequence', y_max_value => 1400, x_tick_number => 5, r_margin => 10, dclrs => [ 'blue' ],
) or die $graph->error; my $gd = $graph->plot(\@data) or die $graph->error;
open my $fh, '>', 'yellowstone-sequence.png'; binmode $fh; print $fh $gd->png(); close $fh;</lang>
- Output:
The first 30 terms in the Yellowstone sequence: 1 2 3 4 9 8 15 14 5 6 25 12 35 16 7 10 21 20 27 22 39 11 13 33 26 45 28 51 32 17
See graph at off-site PNG image
Perl 6
Not really clear whether a line graph or bar graph was desired, so generate both. Also, 100 points don't really give a good feel for the overall shape so do 500.
<lang perl6>my @yellowstone = 1, 2, 3, -> $q, $p {
state @used = True xx 4; state $min = 3; my \index = ($min .. *).first: { not @used[$_] and $_ gcd $q != 1 and $_ gcd $p == 1 }; @used[index] = True; $min = @used.first(!*, :k) // +@used - 1; index
} … *;
put "The first 30 terms in the Yellowstone sequence:\n", @yellowstone[^30];
use SVG; use SVG::Plot;
my @x = ^500;
my $chart = SVG::Plot.new(
background => 'white', width => 1000, height => 600, plot-width => 950, plot-height => 550, x => @x, x-tick-step => { 10 }, y-tick-step => { 50 }, min-y-axis => 0, values => [@yellowstone[@x],], title => "Yellowstone Sequence - First {+@x} values (zero indexed)",
);
my $line = './Yellowstone-sequence-line-perl6.svg'.IO; my $bars = './Yellowstone-sequence-bars-perl6.svg'.IO;
$line.spurt: SVG.serialize: $chart.plot: :lines; $bars.spurt: SVG.serialize: $chart.plot: :bars;</lang>
- Output:
The first 30 terms in the Yellowstone sequence: 1 2 3 4 9 8 15 14 5 6 25 12 35 16 7 10 21 20 27 22 39 11 13 33 26 45 28 51 32 17
See (offsite SVG images) Line graph or Bar graph
Phix
<lang Phix>function yellowstone(integer N)
sequence a = {1, 2, 3}, b = repeat(true,3) integer i = 4 while length(a) < N do if (i>length(b) or b[i]=false) and gcd(i,a[$])=1 and gcd(i,a[$-1])>1 then a &= i if i>length(b) then b &= repeat(false,i-length(b)) end if b[i] = true i = 4 end if i += 1 end while return a
end function
printf(1,"The first 30 entries of the Yellowstone permutation:\n%v\n", {yellowstone(30)})</lang>
- Output:
The first 30 entries of the Yellowstone permutation: {1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17}
a simple plot
<lang Phix>include pGUI.e IupOpen() IupControlsOpen() Ihandle plot = IupPlot("MENUITEMPROPERTIES=Yes, SIZE=640x320") IupSetAttribute(plot, "TITLE", "Yellowstone Numbers"); IupSetAttribute(plot, "TITLEFONTSIZE", "10"); IupSetAttribute(plot, "TITLEFONTSTYLE", "ITALIC"); IupSetAttribute(plot, "GRIDLINESTYLE", "DOTTED"); IupSetAttribute(plot, "GRID", "YES"); IupSetAttribute(plot, "AXS_XLABEL", "n"); IupSetAttribute(plot, "AXS_YLABEL", "a(n)"); IupSetAttribute(plot, "AXS_XFONTSTYLE", "ITALIC"); IupSetAttribute(plot, "AXS_YFONTSTYLE", "ITALIC"); IupSetAttribute(plot, "AXS_YTICKSIZEAUTO", "NO"); IupSetAttribute(plot, "AXS_YTICKMAJORSIZE", "8"); IupSetAttribute(plot, "AXS_YTICKMINORSIZE", "0"); IupPlotBegin(plot) sequence y500 = yellowstone(500) for x=1 to 500 do
IupPlotAdd(plot, x, y500[x])
end for {} = IupPlotEnd(plot) --IupSetAttribute(plot, "DS_MODE", "BAR") -- (optional) Ihandle dlg = IupDialog(plot) IupCloseOnEscape(dlg) IupSetAttribute(dlg, "TITLE", "Yellowstone Names") IupMap(dlg) IupShowXY(dlg,IUP_CENTER,IUP_CENTER) IupMainLoop() IupClose()</lang>
Python
<lang python>Yellowstone permutation OEIS A098550
from itertools import chain, count, islice from operator import itemgetter from math import gcd
from matplotlib import pyplot
- yellowstone :: [Int]
def yellowstone():
A non-finite stream of terms from the Yellowstone permutation. OEIS A098550. # relativelyPrime :: Int -> Int -> Bool def relativelyPrime(a): return lambda b: 1 == gcd(a, b)
# nextWindow :: (Int, Int, [Int]) -> (Int, Int, [Int]) def nextWindow(triple): p2, p1, rest = triple [rp2, rp1] = map(relativelyPrime, [p2, p1])
# match :: [Int] -> (Int, [Int]) def match(xxs): x, xs = uncons(xxs)['Just'] return (x, xs) if rp1(x) and not rp2(x) else ( second(cons(x))( match(xs) ) ) n, residue = match(rest) return (p1, n, residue)
return chain( range(1, 3), map( itemgetter(1), iterate(nextWindow)( (2, 3, count(4)) ) ) )
- TEST ----------------------------------------------------
- main :: IO ()
def main():
Terms of the Yellowstone permutation.
print(showList( take(30)(yellowstone()) )) pyplot.plot( take(100)(yellowstone()) ) pyplot.xlabel(main.__doc__) pyplot.show()
- GENERIC -------------------------------------------------
- Just :: a -> Maybe a
def Just(x):
Constructor for an inhabited Maybe (option type) value. Wrapper containing the result of a computation. return {'type': 'Maybe', 'Nothing': False, 'Just': x}
- Nothing :: Maybe a
def Nothing():
Constructor for an empty Maybe (option type) value. Empty wrapper returned where a computation is not possible. return {'type': 'Maybe', 'Nothing': True}
- cons :: a -> [a] -> [a]
def cons(x):
Construction of a list from x as head, and xs as tail. return lambda xs: [x] + xs if ( isinstance(xs, list) ) else x + xs if ( isinstance(xs, str) ) else chain([x], xs)
- iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
An infinite list of repeated applications of f to x. def go(x): v = x while True: yield v v = f(v) return lambda x: go(x)
- second :: (a -> b) -> ((c, a) -> (c, b))
def second(f):
A simple function lifted to a function over a tuple, with f applied only to the second of two values. return lambda xy: (xy[0], f(xy[1]))
- showList :: [a] -> String
def showList(xs):
Stringification of a list. return '[' + ','.join(repr(x) for x in xs) + ']'
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n, or xs itself if n > length xs. return lambda xs: ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) )
- uncons :: [a] -> Maybe (a, [a])
def uncons(xs):
The deconstruction of a non-empty list (or generator stream) into two parts: a head value, and the remaining values. if isinstance(xs, list): return Just((xs[0], xs[1:])) if xs else Nothing() else: nxt = take(1)(xs) return Just((nxt[0], xs)) if nxt else Nothing()
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
1,2,3,4,9,8,15,14,5,6,25,12,35,16,7,10,21,20,27,22,39,11,13,33,26,45,28,51,32,17]
REXX
<lang rexx>/*REXX program calculates any number of terms in the Yellowstone (permutation) sequence.*/ parse arg m . /*obtain optional argument from the CL.*/ if m== | m=="," then m= 30 /*Not specified? Then use the default.*/ !.= 0 /*initialize an array of numbers(used).*/
- = 0 /*count of Yellowstone numbers in seq. */
$= /*list " " " " " */
do j=1 until #==m; prev= # - 1 if j<5 then do; #= #+1; @.#= j; !.#= j; !.j= 1; $= strip($ j); iterate; end
do k=1; if !.k then iterate /*Already used? Then skip this number.*/ if gcd(k, @.#)\==1 | gcd(k, @.prev)<2 then iterate /*not meet requirement?*/ #= #+1; @.#= k; !.k= 1; $= $ k /*bump ctr; assign; mark used; add list*/ leave /*find the next Yellowstone seq. number*/ end /*k*/ end /*j*/
say $ /*display a list of a Yellowstone seq. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: parse arg x,y; do until y==0; parse value x//y y with y x; end; return x</lang>
- output when using the default input:
1 2 3 4 9 8 15 14 5 6 25 12 35 16 7 10 21 20 27 22 39 11 13 33 26 45 28 51 32 17
zkl
This sequence is limited to the max size of a Dictionary, 64k <lang zkl>fcn yellowstoneW{ // --> iterator
Walker.zero().tweak(fcn(a,b){ foreach i in ([1..]){ if(not b.holds(i) and i.gcd(a[-1])==1 and i.gcd(a[-2]) >1){
a.del(0).append(i); // only keep last two terms b[i]=True; return(i); }
} }.fp(List(2,3), Dictionary(1,True, 2,True, 3,True))).push(1,2,3);
}</lang> <lang zkl>println("The first 30 entries of the Yellowstone permutation:"); yellowstoneW().walk(30).concat(", ").println();</lang>
- Output:
The first 30 entries of the Yellowstone permutation: 1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7, 10, 21, 20, 27, 22, 39, 11, 13, 33, 26, 45, 28, 51, 32, 17
Plot using Gnuplot <lang zkl>gnuplot:=System.popen("gnuplot","w"); gnuplot.writeln("unset key; plot '-'"); yellowstoneW().pump(1_000, gnuplot.writeln.fp(" ")); // " 1\n", " 2\n", ... gnuplot.writeln("e"); gnuplot.flush(); ask("Hit return to finish"); gnuplot.close();</lang> Offsite Image: yellowstone