Yellowstone sequence: Difference between revisions
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
(89 intermediate revisions by 37 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
[[Category:Prime Numbers]] |
|||
<br> |
|||
The '''Yellowstone sequence''', also called the '''Yellowstone permutation''', is defined as: |
The '''Yellowstone sequence''', also called the '''Yellowstone permutation''', is defined as: |
||
Line 6: | Line 6: | ||
For n <= 3, |
For n <= 3, |
||
a(n) = n |
a(n) = n |
||
For n >= 4, |
For n >= 4, |
||
a(n) = the smallest number not already in sequence such that a(n) is relatively prime to a(n-1) and |
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. |
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. |
||
Line 20: | Line 22: | ||
;Task |
;Task |
||
: Find and show as output the first 30 Yellowstone numbers. |
: Find and show as output the first '''30''' Yellowstone numbers. |
||
Line 30: | Line 32: | ||
:* [https://rosettacode.org/wiki/Greatest_common_divisor Greatest common divisor]. |
:* [https://rosettacode.org/wiki/Greatest_common_divisor Greatest common divisor]. |
||
:* [https://rosettacode.org/wiki/Plot_coordinate_pairs Plot coordinate pairs]. |
:* [https://rosettacode.org/wiki/Plot_coordinate_pairs Plot coordinate pairs]. |
||
:* [[EKG sequence convergence]] |
|||
Line 35: | Line 38: | ||
:* The OEIS entry: [https://oeis.org/A098550 A098550 The Yellowstone permutation]. |
:* The OEIS entry: [https://oeis.org/A098550 A098550 The Yellowstone permutation]. |
||
:* Applegate et al, 2015: The Yellowstone Permutation [https://arxiv.org/abs/1501.01669]. |
:* Applegate et al, 2015: The Yellowstone Permutation [https://arxiv.org/abs/1501.01669]. |
||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="11l">T YellowstoneGenerator |
|||
min_ = 1 |
|||
n_ = 0 |
|||
n1_ = 0 |
|||
n2_ = 0 |
|||
Set[Int] sequence_ |
|||
F next() |
|||
.n2_ = .n1_ |
|||
.n1_ = .n_ |
|||
I .n_ < 3 |
|||
.n_++ |
|||
E |
|||
.n_ = .min_ |
|||
L !(.n_ !C .sequence_ & gcd(.n1_, .n_) == 1 & gcd(.n2_, .n_) > 1) |
|||
.n_++ |
|||
.sequence_.add(.n_) |
|||
L |
|||
I .min_ !C .sequence_ |
|||
L.break |
|||
.sequence_.remove(.min_) |
|||
.min_++ |
|||
R .n_ |
|||
print(‘First 30 Yellowstone numbers:’) |
|||
V ygen = YellowstoneGenerator() |
|||
print(ygen.next(), end' ‘’) |
|||
L(i) 1 .< 30 |
|||
print(‘ ’ygen.next(), end' ‘’) |
|||
print()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
{{trans|Ruby}} |
|||
<syntaxhighlight lang="11l">F yellow(n) |
|||
V a = [1, 2, 3] |
|||
V b = Set([1, 2, 3]) |
|||
V i = 4 |
|||
L n > a.len |
|||
I i !C b & gcd(i, a.last) == 1 & gcd(i, a[(len)-2]) > 1 |
|||
a.append(i) |
|||
b.add(i) |
|||
i = 4 |
|||
i++ |
|||
R a |
|||
print(yellow(30))</syntaxhighlight> |
|||
{{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|Action!}}== |
|||
<syntaxhighlight lang="action!">BYTE FUNC Gcd(BYTE a,b) |
|||
BYTE tmp |
|||
IF a<b THEN |
|||
tmp=a a=b b=tmp |
|||
FI |
|||
WHILE b#0 |
|||
DO |
|||
tmp=a MOD b |
|||
a=b b=tmp |
|||
OD |
|||
RETURN (a) |
|||
BYTE FUNC Contains(BYTE ARRAY a BYTE len,value) |
|||
BYTE i |
|||
FOR i=0 TO len-1 |
|||
DO |
|||
IF a(i)=value THEN |
|||
RETURN (1) |
|||
FI |
|||
OD |
|||
RETURN (0) |
|||
PROC Generate(BYTE ARRAY seq BYTE count) |
|||
BYTE i,x |
|||
seq(0)=1 seq(1)=2 seq(2)=3 |
|||
FOR i=3 TO COUNT-1 |
|||
DO |
|||
x=1 |
|||
DO |
|||
IF Contains(seq,i,x)=0 AND |
|||
Gcd(x,seq(i-1))=1 AND Gcd(x,seq(i-2))>1 THEN |
|||
EXIT |
|||
FI |
|||
x==+1 |
|||
OD |
|||
seq(i)=x |
|||
OD |
|||
RETURN |
|||
PROC Main() |
|||
DEFINE COUNT="30" |
|||
BYTE ARRAY seq(COUNT) |
|||
BYTE i |
|||
Generate(seq,COUNT) |
|||
PrintF("First %B Yellowstone numbers:%E",COUNT) |
|||
FOR i=0 TO COUNT-1 |
|||
DO |
|||
PrintB(seq(i)) Put(32) |
|||
OD |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Yellowstone_sequence.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="ada">with Ada.Text_IO; |
|||
with Ada.Containers.Ordered_Sets; |
|||
procedure Yellowstone_Sequence is |
|||
generic -- Allow more than one generator, but must be instantiated |
|||
package Yellowstones is |
|||
function Next return Integer; |
|||
function GCD (Left, Right : Integer) return Integer; |
|||
end Yellowstones; |
|||
package body Yellowstones |
|||
is |
|||
package Sequences is |
|||
new Ada.Containers.Ordered_Sets (Integer); |
|||
-- Internal package state |
|||
N_0 : Integer := 0; |
|||
N_1 : Integer := 0; |
|||
N_2 : Integer := 0; |
|||
Seq : Sequences.Set; |
|||
Min : Integer := 1; |
|||
function GCD (Left, Right : Integer) return Integer |
|||
is (if Right = 0 |
|||
then Left |
|||
else GCD (Right, Left mod Right)); |
|||
function Next return Integer is |
|||
begin |
|||
N_2 := N_1; |
|||
N_1 := N_0; |
|||
if N_0 < 3 then |
|||
N_0 := N_0 + 1; |
|||
else |
|||
N_0 := Min; |
|||
while |
|||
not (not Seq.Contains (N_0) |
|||
and then GCD (N_1, N_0) = 1 |
|||
and then GCD (N_2, N_0) > 1) |
|||
loop |
|||
N_0 := N_0 + 1; |
|||
end loop; |
|||
end if; |
|||
Seq.Insert (N_0); |
|||
while Seq.Contains (Min) loop |
|||
Seq.Delete (Min); |
|||
Min := Min + 1; |
|||
end loop; |
|||
return N_0; |
|||
end Next; |
|||
end Yellowstones; |
|||
procedure First_30 is |
|||
package Yellowstone is new Yellowstones; -- New generator instance |
|||
use Ada.Text_IO; |
|||
begin |
|||
Put_Line ("First 30 Yellowstone numbers:"); |
|||
for A in 1 .. 30 loop |
|||
Put (Yellowstone.Next'Image); Put (" "); |
|||
end loop; |
|||
New_Line; |
|||
end First_30; |
|||
begin |
|||
First_30; |
|||
end Yellowstone_Sequence;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
<syntaxhighlight lang="algol68">BEGIN # find members of the yellowstone sequence: starting from 1, 2, 3 the # |
|||
# subsequent members are the lowest number coprime to the previous one # |
|||
# and not coprime to the one before that, that haven't appeared in the # |
|||
# sequence yet # |
|||
# iterative Greatest Common Divisor routine, returns the gcd of m and n # |
|||
PROC gcd = ( INT m, n )INT: |
|||
BEGIN |
|||
INT a := ABS m, b := ABS n; |
|||
WHILE b /= 0 DO |
|||
INT new a = b; |
|||
b := a MOD b; |
|||
a := new a |
|||
OD; |
|||
a |
|||
END # gcd # ; |
|||
# returns an array of the Yellowstone seuence up to n # |
|||
OP YELLOWSTONE = ( INT n )[]INT: |
|||
BEGIN |
|||
[ 1 : n ]INT result; |
|||
IF n > 0 THEN |
|||
result[ 1 ] := 1; |
|||
IF n > 1 THEN |
|||
result[ 2 ] := 2; |
|||
IF n > 2 THEN |
|||
result[ 3 ] := 3; |
|||
# guess the maximum element will be n, if it is larger, used will be enlarged # |
|||
REF[]BOOL used := HEAP[ 1 : n ]BOOL; |
|||
used[ 1 ] := used[ 2 ] := used[ 3 ] := TRUE; |
|||
FOR i FROM 4 TO UPB used DO used[ i ] := FALSE OD; |
|||
FOR i FROM 4 TO UPB result DO |
|||
INT p1 = result[ i - 1 ]; |
|||
INT p2 = result[ i - 2 ]; |
|||
BOOL found := FALSE; |
|||
FOR j WHILE NOT found DO |
|||
IF j > UPB used THEN |
|||
# not enough elements in used - enlarge it # |
|||
REF[]BOOL new used := HEAP[ 1 : 2 * UPB used ]BOOL; |
|||
new used[ 1 : UPB used ] := used; |
|||
FOR k FROM UPB used + 1 TO UPB new used DO new used[ k ] := FALSE OD; |
|||
used := new used |
|||
FI; |
|||
IF NOT used[ j ] THEN |
|||
IF found := gcd( j, p1 ) = 1 AND gcd( j, p2 ) /= 1 |
|||
THEN |
|||
result[ i ] := j; |
|||
used[ j ] := TRUE |
|||
FI |
|||
FI |
|||
OD |
|||
OD |
|||
FI |
|||
FI |
|||
FI; |
|||
result |
|||
END # YELLOWSTONE # ; |
|||
[]INT ys = YELLOWSTONE 30; |
|||
FOR i TO UPB ys DO |
|||
print( ( " ", whole( ys[ i ], 0 ) ) ) |
|||
OD |
|||
END</syntaxhighlight> |
|||
{{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|Arturo}}== |
|||
<syntaxhighlight lang="rebol">yellowstone: function [n][ |
|||
result: new [1 2 3] |
|||
present: new [1 2 3] |
|||
start: new 4 |
|||
while [n > size result][ |
|||
candidate: new start |
|||
while ø [ |
|||
if all? @[ |
|||
not? contains? present candidate |
|||
1 = gcd @[candidate last result] |
|||
1 <> gcd @[candidate get result (size result)-2] |
|||
][ |
|||
'result ++ candidate |
|||
'present ++ candidate |
|||
while [contains? present start] -> inc 'start |
|||
break |
|||
] |
|||
inc 'candidate |
|||
] |
|||
] |
|||
return result |
|||
] |
|||
print yellowstone 30</syntaxhighlight> |
|||
{{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|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">A := [], in_seq := [] |
|||
loop 30 { |
|||
n := A_Index |
|||
if n <=3 |
|||
A[n] := n, in_seq[n] := true |
|||
else while true |
|||
{ |
|||
s := A_Index |
|||
if !in_seq[s] && relatively_prime(s, A[n-1]) && !relatively_prime(s, A[n-2]) |
|||
{ |
|||
A[n] := s |
|||
in_seq[s] := true |
|||
break |
|||
} |
|||
} |
|||
} |
|||
for i, v in A |
|||
result .= v "," |
|||
MsgBox % result := "[" Trim(result, ",") "]" |
|||
return |
|||
;-------------------------------------- |
|||
relatively_prime(a, b){ |
|||
return (GCD(a, b) = 1) |
|||
} |
|||
;-------------------------------------- |
|||
GCD(a, b) { |
|||
while b |
|||
b := Mod(a | 0x0, a := b) |
|||
return a |
|||
}</syntaxhighlight> |
|||
{{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|C}}== |
|||
{{trans|Ruby}} |
|||
<syntaxhighlight lang="c">#include <stdbool.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
typedef struct lnode_t { |
|||
struct lnode_t *prev; |
|||
struct lnode_t *next; |
|||
int v; |
|||
} Lnode; |
|||
Lnode *make_list_node(int v) { |
|||
Lnode *node = malloc(sizeof(Lnode)); |
|||
if (node == NULL) { |
|||
return NULL; |
|||
} |
|||
node->v = v; |
|||
node->prev = NULL; |
|||
node->next = NULL; |
|||
return node; |
|||
} |
|||
void free_lnode(Lnode *node) { |
|||
if (node == NULL) { |
|||
return; |
|||
} |
|||
node->v = 0; |
|||
node->prev = NULL; |
|||
free_lnode(node->next); |
|||
node->next = NULL; |
|||
} |
|||
typedef struct list_t { |
|||
Lnode *front; |
|||
Lnode *back; |
|||
size_t len; |
|||
} List; |
|||
List *make_list() { |
|||
List *list = malloc(sizeof(List)); |
|||
if (list == NULL) { |
|||
return NULL; |
|||
} |
|||
list->front = NULL; |
|||
list->back = NULL; |
|||
list->len = 0; |
|||
return list; |
|||
} |
|||
void free_list(List *list) { |
|||
if (list == NULL) { |
|||
return; |
|||
} |
|||
list->len = 0; |
|||
list->back = NULL; |
|||
free_lnode(list->front); |
|||
list->front = NULL; |
|||
} |
|||
void list_insert(List *list, int v) { |
|||
Lnode *node; |
|||
if (list == NULL) { |
|||
return; |
|||
} |
|||
node = make_list_node(v); |
|||
if (list->front == NULL) { |
|||
list->front = node; |
|||
list->back = node; |
|||
list->len = 1; |
|||
} else { |
|||
node->prev = list->back; |
|||
list->back->next = node; |
|||
list->back = node; |
|||
list->len++; |
|||
} |
|||
} |
|||
void list_print(List *list) { |
|||
Lnode *it; |
|||
if (list == NULL) { |
|||
return; |
|||
} |
|||
for (it = list->front; it != NULL; it = it->next) { |
|||
printf("%d ", it->v); |
|||
} |
|||
} |
|||
int list_get(List *list, int idx) { |
|||
Lnode *it = NULL; |
|||
if (list != NULL && list->front != NULL) { |
|||
int i; |
|||
if (idx < 0) { |
|||
it = list->back; |
|||
i = -1; |
|||
while (it != NULL && i > idx) { |
|||
it = it->prev; |
|||
i--; |
|||
} |
|||
} else { |
|||
it = list->front; |
|||
i = 0; |
|||
while (it != NULL && i < idx) { |
|||
it = it->next; |
|||
i++; |
|||
} |
|||
} |
|||
} |
|||
if (it == NULL) { |
|||
return INT_MIN; |
|||
} |
|||
return it->v; |
|||
} |
|||
/////////////////////////////////////// |
|||
typedef struct mnode_t { |
|||
int k; |
|||
bool v; |
|||
struct mnode_t *next; |
|||
} Mnode; |
|||
Mnode *make_map_node(int k, bool v) { |
|||
Mnode *node = malloc(sizeof(Mnode)); |
|||
if (node == NULL) { |
|||
return node; |
|||
} |
|||
node->k = k; |
|||
node->v = v; |
|||
node->next = NULL; |
|||
return node; |
|||
} |
|||
void free_mnode(Mnode *node) { |
|||
if (node == NULL) { |
|||
return; |
|||
} |
|||
node->k = 0; |
|||
node->v = false; |
|||
free_mnode(node->next); |
|||
node->next = NULL; |
|||
} |
|||
typedef struct map_t { |
|||
Mnode *front; |
|||
} Map; |
|||
Map *make_map() { |
|||
Map *map = malloc(sizeof(Map)); |
|||
if (map == NULL) { |
|||
return NULL; |
|||
} |
|||
map->front = NULL; |
|||
return map; |
|||
} |
|||
void free_map(Map *map) { |
|||
if (map == NULL) { |
|||
return; |
|||
} |
|||
free_mnode(map->front); |
|||
map->front = NULL; |
|||
} |
|||
void map_insert(Map *map, int k, bool v) { |
|||
if (map == NULL) { |
|||
return; |
|||
} |
|||
if (map->front == NULL) { |
|||
map->front = make_map_node(k, v); |
|||
} else { |
|||
Mnode *it = map->front; |
|||
while (it->next != NULL) { |
|||
it = it->next; |
|||
} |
|||
it->next = make_map_node(k, v); |
|||
} |
|||
} |
|||
bool map_get(Map *map, int k) { |
|||
if (map != NULL) { |
|||
Mnode *it = map->front; |
|||
while (it != NULL && it->k != k) { |
|||
it = it->next; |
|||
} |
|||
if (it != NULL) { |
|||
return it->v; |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
/////////////////////////////////////// |
|||
int gcd(int u, int v) { |
|||
if (u < 0) u = -u; |
|||
if (v < 0) v = -v; |
|||
if (v) { |
|||
while ((u %= v) && (v %= u)); |
|||
} |
|||
return u + v; |
|||
} |
|||
List *yellow(size_t n) { |
|||
List *a; |
|||
Map *b; |
|||
int i; |
|||
a = make_list(); |
|||
list_insert(a, 1); |
|||
list_insert(a, 2); |
|||
list_insert(a, 3); |
|||
b = make_map(); |
|||
map_insert(b, 1, true); |
|||
map_insert(b, 2, true); |
|||
map_insert(b, 3, true); |
|||
i = 4; |
|||
while (n > a->len) { |
|||
if (!map_get(b, i) && gcd(i, list_get(a, -1)) == 1 && gcd(i, list_get(a, -2)) > 1) { |
|||
list_insert(a, i); |
|||
map_insert(b, i, true); |
|||
i = 4; |
|||
} |
|||
i++; |
|||
} |
|||
free_map(b); |
|||
return a; |
|||
} |
|||
int main() { |
|||
List *a = yellow(30); |
|||
list_print(a); |
|||
free_list(a); |
|||
putc('\n', stdout); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{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|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <numeric> |
|||
#include <set> |
|||
template <typename integer> |
|||
class yellowstone_generator { |
|||
public: |
|||
integer next() { |
|||
n2_ = n1_; |
|||
n1_ = n_; |
|||
if (n_ < 3) { |
|||
++n_; |
|||
} else { |
|||
for (n_ = min_; !(sequence_.count(n_) == 0 |
|||
&& std::gcd(n1_, n_) == 1 |
|||
&& std::gcd(n2_, n_) > 1); ++n_) {} |
|||
} |
|||
sequence_.insert(n_); |
|||
for (;;) { |
|||
auto it = sequence_.find(min_); |
|||
if (it == sequence_.end()) |
|||
break; |
|||
sequence_.erase(it); |
|||
++min_; |
|||
} |
|||
return n_; |
|||
} |
|||
private: |
|||
std::set<integer> sequence_; |
|||
integer min_ = 1; |
|||
integer n_ = 0; |
|||
integer n1_ = 0; |
|||
integer n2_ = 0; |
|||
}; |
|||
int main() { |
|||
std::cout << "First 30 Yellowstone numbers:\n"; |
|||
yellowstone_generator<unsigned int> ygen; |
|||
std::cout << ygen.next(); |
|||
for (int i = 1; i < 30; ++i) |
|||
std::cout << ' ' << ygen.next(); |
|||
std::cout << '\n'; |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|D}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="d">import std.numeric; |
|||
import std.range; |
|||
import std.stdio; |
|||
class Yellowstone { |
|||
private bool[int] sequence_; |
|||
private int min_ = 1; |
|||
private int n_ = 0; |
|||
private int n1_ = 0; |
|||
private int n2_ = 0; |
|||
public this() { |
|||
popFront(); |
|||
} |
|||
public bool empty() { |
|||
return false; |
|||
} |
|||
public int front() { |
|||
return n_; |
|||
} |
|||
public void popFront() { |
|||
n2_ = n1_; |
|||
n1_ = n_; |
|||
if (n_ < 3) { |
|||
++n_; |
|||
} else { |
|||
for (n_ = min_; |
|||
!(n_ !in sequence_ && gcd(n1_, n_) == 1 && gcd(n2_, n_) > 1); |
|||
++n_) { |
|||
// empty |
|||
} |
|||
} |
|||
sequence_[n_] = true; |
|||
while (true) { |
|||
if (min_ !in sequence_) { |
|||
break; |
|||
} |
|||
sequence_.remove(min_); |
|||
++min_; |
|||
} |
|||
} |
|||
} |
|||
void main() { |
|||
new Yellowstone().take(30).writeln(); |
|||
}</syntaxhighlight> |
|||
{{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|Delphi}}== |
|||
{{libheader| System.SysUtils}} |
|||
{{libheader| Boost.Generics.Collection}} |
|||
{{libheader| Boost.Process}} |
|||
{{Trans|Go}} |
|||
Boost.Generics.Collection and Boost.Process are part of [https://github.com/MaiconSoft/DelphiBoostLib DelphiBoostLib]. |
|||
<syntaxhighlight lang="delphi"> |
|||
program Yellowstone_sequence; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
System.SysUtils, |
|||
Boost.Generics.Collection, |
|||
Boost.Process; |
|||
function gdc(x, y: Integer): Integer; |
|||
begin |
|||
while y <> 0 do |
|||
begin |
|||
var tmp := x; |
|||
x := y; |
|||
y := tmp mod y; |
|||
end; |
|||
Result := x; |
|||
end; |
|||
function Yellowstone(n: Integer): TArray<Integer>; |
|||
var |
|||
m: TDictionary<Integer, Boolean>; |
|||
a: TArray<Integer>; |
|||
begin |
|||
m.Init; |
|||
SetLength(a, n + 1); |
|||
for var i := 1 to 3 do |
|||
begin |
|||
a[i] := i; |
|||
m[i] := True; |
|||
end; |
|||
var min := 4; |
|||
for var c := 4 to n do |
|||
begin |
|||
var i := min; |
|||
repeat |
|||
if not m[i, false] and (gdc(a[c - 1], i) = 1) and (gdc(a[c - 2], i) > 1) then |
|||
begin |
|||
a[c] := i; |
|||
m[i] := true; |
|||
if i = min then |
|||
inc(min); |
|||
Break; |
|||
end; |
|||
inc(i); |
|||
until false; |
|||
end; |
|||
Result := copy(a, 1, length(a)); |
|||
end; |
|||
begin |
|||
var x: TArray<Integer>; |
|||
SetLength(x, 100); |
|||
for var i in Range(100) do |
|||
x[i] := i + 1; |
|||
var y := yellowstone(High(x)); |
|||
writeln('The first 30 Yellowstone numbers are:'); |
|||
for var i := 0 to 29 do |
|||
Write(y[i], ' '); |
|||
Writeln; |
|||
//Plotting |
|||
var plot := TPipe.Create('gnuplot -p', True); |
|||
plot.WritelnA('unset key; plot ''-'''); |
|||
for var i := 0 to High(x) do |
|||
plot.WriteA('%d %d'#10, [x[i], y[i]]); |
|||
plot.WritelnA('e'); |
|||
writeln('Press enter to close'); |
|||
Readln; |
|||
plot.Kill; |
|||
plot.Free; |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 |
|||
Press enter to close</pre> |
|||
=={{header|EasyLang}}== |
|||
{{trans|Lua}} |
|||
<syntaxhighlight> |
|||
func gcd a b . |
|||
if b = 0 |
|||
return a |
|||
. |
|||
return gcd b (a mod b) |
|||
. |
|||
proc remove_at i . a[] . |
|||
for j = i + 1 to len a[] |
|||
a[j - 1] = a[j] |
|||
. |
|||
len a[] -1 |
|||
. |
|||
proc yellowstone count . yellow[] . |
|||
yellow[] = [ 1 2 3 ] |
|||
num = 4 |
|||
while len yellow[] < count |
|||
yell1 = yellow[len yellow[] - 1] |
|||
yell2 = yellow[len yellow[]] |
|||
for i to len notyellow[] |
|||
test = notyellow[i] |
|||
if gcd yell1 test > 1 and gcd yell2 test = 1 |
|||
break 1 |
|||
. |
|||
. |
|||
if i <= len notyellow[] |
|||
yellow[] &= notyellow[i] |
|||
remove_at i notyellow[] |
|||
else |
|||
while gcd yell1 num <= 1 or gcd yell2 num <> 1 |
|||
notyellow[] &= num |
|||
num += 1 |
|||
. |
|||
yellow[] &= num |
|||
num += 1 |
|||
. |
|||
. |
|||
. |
|||
print "First 30 values in the yellowstone sequence:" |
|||
yellowstone 30 yellow[] |
|||
print yellow[] |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2020-01-23}} |
{{works with|Factor|0.99 2020-01-23}} |
||
< |
<syntaxhighlight lang="factor">USING: accessors assocs colors.constants |
||
combinators.short-circuit io kernel math prettyprint sequences |
combinators.short-circuit io kernel math prettyprint sequences |
||
sets ui ui.gadgets ui.gadgets.charts ui.gadgets.charts.lines ; |
sets ui ui.gadgets ui.gadgets.charts ui.gadgets.charts.lines ; |
||
Line 71: | Line 899: | ||
line new COLOR: blue >>color |
line new COLOR: blue >>color |
||
100 <iota> 100 <yellowstone> zip >>data |
100 <iota> 100 <yellowstone> zip >>data |
||
add-gadget "Yellowstone numbers" open-window</ |
add-gadget "Yellowstone numbers" open-window</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 77: | Line 905: | ||
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 |
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> |
||
=={{header|Forth}}== |
|||
<syntaxhighlight lang="text">: array create cells allot ; |
|||
: th cells + ; \ some helper words |
|||
30 constant #yellow \ number of yellowstones |
|||
#yellow array y \ create array |
|||
( n1 n2 -- n3) |
|||
: gcd dup if tuck mod recurse exit then drop ; |
|||
: init 3 0 do i 1+ y i th ! loop ; ( --) |
|||
: show cr #yellow 0 do y i th ? loop ; ( --) |
|||
: gcd-y[] - cells y + @ over gcd ; ( k i n -- k gcd ) |
|||
: loop1 begin 1+ over 2 gcd-y[] 1 = >r over 1 gcd-y[] 1 > r> or 0= until ; |
|||
: loop2 over true swap 0 ?do over y i th @ = if 0= leave then loop ; |
|||
: yellow #yellow 3 do i 3 begin loop1 loop2 until y rot th ! loop ; |
|||
: main init yellow show ; |
|||
main</syntaxhighlight> |
|||
{{out}} |
|||
<pre>main |
|||
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 ok</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">function gcd(a as uinteger, b as uinteger) as uinteger |
|||
if b = 0 then return a |
|||
return gcd( b, a mod b ) |
|||
end function |
|||
dim as uinteger i, j, k, Y(1 to 100) |
|||
Y(1) = 1 : Y(2) = 2: Y(3) = 3 |
|||
for i = 4 to 100 |
|||
k = 3 |
|||
print i |
|||
do |
|||
k += 1 |
|||
if gcd( k, Y(i-2) ) = 1 orelse gcd( k, Y(i-1) ) > 1 then continue do |
|||
for j = 1 to i-1 |
|||
if Y(j)=k then continue do |
|||
next j |
|||
Y(i) = k |
|||
exit do |
|||
loop |
|||
next i |
|||
for i = 1 to 30 |
|||
print str(Y(i))+" "; |
|||
next i |
|||
print |
|||
screen 13 |
|||
for i = 1 to 100 |
|||
pset (i, 200-Y(i)), 31 |
|||
next i |
|||
while inkey="" |
|||
wend |
|||
end</syntaxhighlight> |
|||
{{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|Go}}== |
=={{header|Go}}== |
||
This uses Gnuplot-X11 to do the plotting rather than a third party Go plotting library. |
This uses Gnuplot-X11 to do the plotting rather than a third party Go plotting library. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 143: | Line 1,032: | ||
w.Close() |
w.Close() |
||
g.Wait() |
g.Wait() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 152: | Line 1,041: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (unfoldr) |
||
yellowstone :: [Integer] |
yellowstone :: [Integer] |
||
yellowstone = 1 : 2 : 3 : unfoldr (Just . f) (2,3,[4..]) |
yellowstone = 1 : 2 : 3 : unfoldr (Just . f) (2, 3, [4 ..]) |
||
where |
|||
f :: (Integer, Integer, [Integer]) -> (Integer, (Integer, Integer, [Integer])) |
|||
f :: |
|||
f (p2, p1, rest) = (next, (p1, next, rest_)) where |
|||
( |
(Integer, Integer, [Integer]) -> |
||
(Integer, (Integer, Integer, [Integer])) |
|||
f (p2, p1, rest) = (next, (p1, next, rest_)) |
|||
select (x:xs) |
|||
where |
|||
| gcd x p1 == 1 && gcd x p2 /= 1 = (x, xs) |
|||
(next, rest_) = select rest |
|||
select :: [Integer] -> (Integer, [Integer]) |
|||
where (y, ys) = select xs |
|||
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 :: IO () |
||
main = print $ take 30 yellowstone</ |
main = print $ take 30 yellowstone</syntaxhighlight> |
||
{{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> |
|||
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). |
|||
Or, defining the Yellowstone permutation in terms of ''iterate'', rather than ''unfoldr'', |
|||
<lang haskell>import qualified Graphics.SVGFonts.ReadFont as F |
|||
import Graphics.Rendering.Chart.Backend.Diagrams |
|||
and displaying a chart of the first 100 terms: |
|||
import Graphics.Rendering.Chart.Easy |
|||
<syntaxhighlight lang="haskell">import Codec.Picture |
|||
import Data.Bifunctor (second) |
|||
import Diagrams.Backend.Rasterific |
import Diagrams.Backend.Rasterific |
||
import Diagrams.Prelude |
import Diagrams.Prelude |
||
import Graphics.Rendering.Chart.Backend.Diagrams |
|||
import Codec.Picture |
|||
import |
import Graphics.Rendering.Chart.Easy |
||
import qualified Graphics.SVGFonts.ReadFont as F |
|||
----------------- |
----------------- YELLOWSTONE PERMUTATION ---------------- |
||
yellowstone :: [Integer] |
yellowstone :: [Integer] |
||
yellowstone = |
|||
yellowstone = 1 : 2 : (active <$> iterate nextWindow (2, 3, [4 ..])) |
|||
1 : |
|||
2 : |
|||
(active <$> iterate nextWindow (2, 3, [4 ..])) |
|||
where |
where |
||
nextWindow :: (Integer, Integer, [Integer]) -> (Integer, Integer, [Integer]) |
|||
nextWindow (p2, p1, rest) = (p1, n, residue) |
nextWindow (p2, p1, rest) = (p1, n, residue) |
||
where |
where |
||
[rp2, rp1] = relativelyPrime <$> [p2, p1] |
[rp2, rp1] = relativelyPrime <$> [p2, p1] |
||
go (x:xs) |
go (x : xs) |
||
| rp1 x && not (rp2 x) = (x, xs) |
| rp1 x && not (rp2 x) = (x, xs) |
||
| otherwise = second ((:) x) (go xs) |
| otherwise = second ((:) x) (go xs) |
||
Line 201: | Line 1,097: | ||
relativelyPrime a b = 1 == gcd a b |
relativelyPrime a b = 1 == gcd a b |
||
----------30 FIRST TERMS, AND CHART OF FIRST 100 |
---------- 30 FIRST TERMS, AND CHART OF FIRST 100 -------- |
||
main :: IO (Image PixelRGBA8) |
main :: IO (Image PixelRGBA8) |
||
main = do |
main = do |
||
Line 208: | Line 1,104: | ||
return $ |
return $ |
||
chartRender env $ |
chartRender env $ |
||
plot |
|||
plot (line "Yellowstone terms" [zip [1 ..] (take 100 yellowstone)]) |
|||
( line |
|||
"Yellowstone terms" |
|||
[zip [1 ..] (take 100 yellowstone)] |
|||
) |
|||
---------------------CHART GENERATION |
--------------------- CHART GENERATION ------------------- |
||
chartRender |
chartRender :: |
||
(Default r, ToRenderable r) => |
|||
DEnv Double -> |
|||
EC r () -> |
|||
Image PixelRGBA8 |
|||
chartRender env ec = |
chartRender env ec = |
||
renderDia |
|||
let (width, _) = envOutputSize env |
|||
Rasterific |
|||
( RasterificOptions |
|||
fst $ runBackendR env (toRenderable (execEC ec)) |
|||
(mkWidth (fst (envOutputSize env))) |
|||
) |
|||
$ fst $ runBackendR env (toRenderable (execEC ec)) |
|||
------------------------ LOCAL FONT |
------------------------ LOCAL FONT ---------------------- |
||
chartEnv :: IO (DEnv Double) |
chartEnv :: IO (DEnv Double) |
||
chartEnv = do |
chartEnv = do |
||
Line 225: | Line 1,130: | ||
sansRB <- F.loadFont "SourceSansPro_RB.svg" |
sansRB <- F.loadFont "SourceSansPro_RB.svg" |
||
let fontChosen fs = |
let fontChosen fs = |
||
case (_font_name fs, |
case ( _font_name fs, |
||
_font_slant fs, |
|||
("sans-serif", FontSlantNormal, FontWeightNormal) -> sansR |
|||
_font_weight fs |
|||
("sans-serif", FontSlantNormal, FontWeightBold) -> sansRB |
|||
) of |
|||
return $ createEnv vectorAlignmentFns 640 400 fontChosen</lang> |
|||
( "sans-serif", |
|||
FontSlantNormal, |
|||
FontWeightNormal |
|||
) -> sansR |
|||
( "sans-serif", |
|||
FontSlantNormal, |
|||
FontWeightBold |
|||
) -> sansRB |
|||
return $ createEnv vectorAlignmentFns 640 400 fontChosen</syntaxhighlight> |
|||
{{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|J}}== |
|||
===tacit=== |
|||
<syntaxhighlight lang="j"> |
|||
Until=: 2 :'u^:(0-:v)^:_' |
|||
assert 44 -: >:Until(>&43) 32 NB. increment until exceeding 43 |
|||
gcd=: +. |
|||
coprime=: 1 = gcd |
|||
prepare=:1 2 3"_ NB. start with the vector 1 2 3 |
|||
condition=: 0 1 -: (coprime _2&{.) NB. trial coprime most recent 2, nay and yay |
|||
append=: , NB. concatenate |
|||
novel=: -.@e. NB. x is not a member of y |
|||
term=: >:@:]Until((condition *. novel)~) 4: |
|||
ys=: (append term)@]^:(0 >. _3+[) prepare |
|||
assert (ys 30) -: 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 |
|||
</syntaxhighlight> |
|||
===explicit=== |
|||
<syntaxhighlight lang="j"> |
|||
GCD=: +. |
|||
relatively_prime=: 1 = GCD |
|||
yellowstone=: {{ |
|||
s=. 1 2 3 NB. initial sequence |
|||
while. y > # s do. |
|||
z=. <./(1+s)-.s NB. lowest positive inteeger not in sequence |
|||
while. if. 0 1 -: z relatively_prime _2{.s do. z e. s end. do. |
|||
z=. z+1 |
|||
end. NB. find next value for sequence |
|||
s=. s, z |
|||
end. |
|||
}} |
|||
</syntaxhighlight> |
|||
<pre> |
|||
yellowstone 30 |
|||
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 |
|||
load'plot' |
|||
'marker'plot yellowstone 100 |
|||
</pre> |
|||
[https://jsoftware.github.io/j-playground/bin/html2/#code=GCD%3D%3A%20%2B.%0Arelatively_prime%3D%3A%201%20%3D%20GCD%0A%0Ayellowstone%3D%3A%20%7B%7B%0A%20%20s%3D.%201%202%203%20%20%20%20%20%20%20%20%20%20%20%20NB.%20initial%20sequence%0A%20%20while.%20y%20%3E%20%23%20s%20do.%0A%20%20%20%20z%3D.%20%3C.%2F%281%2Bs%29-.s%20%20%20%20NB.%20lowest%20positive%20inteeger%20not%20in%20sequence%0A%20%20%20%20while.%20if.%200%201%20-%3A%20z%20relatively_prime%20_2%7B.s%20do.%20z%20e.%20s%20end.%20do.%0A%20%20%20%20%20%20z%3D.%20z%2B1%0A%20%20%20%20end.%20%20%20NB.%20find%20next%20value%20for%20sequence%0A%20%20%20%20s%3D.%20s%2C%20z%0A%20%20end.%0A%7D%7D%0A%0Arequire'plot'%0A'marker'plot%20yellowstone%20100 try it online] |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java"> |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.List; |
import java.util.List; |
||
Line 288: | Line 1,243: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 299: | Line 1,254: | ||
{{Trans|Python}} |
{{Trans|Python}} |
||
{{Works with|ES6}} |
{{Works with|ES6}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 489: | Line 1,444: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{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|jq}}== |
|||
{{works with|jq}} |
|||
<syntaxhighlight lang="jq"> |
|||
# jq optimizes the recursive call of _gcd in the following: |
|||
def gcd(a;b): |
|||
def _gcd: |
|||
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end; |
|||
[a,b] | _gcd ; |
|||
# emit the yellowstone sequence as a stream |
|||
def yellowstone: |
|||
1,2,3, |
|||
({ a: [2, 3], # the last two items only |
|||
b: {"1": true, "2": true, "3" : true}, # a record, to avoid having to save the entire history |
|||
start: 4 } |
|||
| foreach range(1; infinite) as $n (.; |
|||
first( |
|||
.b as $b |
|||
| .start = first( range(.start;infinite) | select($b[tostring]|not) ) |
|||
| foreach range(.start; infinite) as $i (.; |
|||
.emit = null |
|||
| ($i|tostring) as $is |
|||
| if .b[$is] then . |
|||
# "a(n) is relatively prime to a(n-1) and is not relatively prime to a(n-2)" |
|||
elif (gcd($i; .a[1]) == 1) and (gcd($i; .a[0]) > 1) |
|||
then .emit = $i |
|||
| .a = [.a[1], $i] |
|||
| .b[$is] = true |
|||
else . |
|||
end; |
|||
select(.emit)) ); |
|||
.emit )); |
|||
</syntaxhighlight> |
|||
'''The task''' |
|||
<syntaxhighlight lang="jq">"The first 30 entries of the Yellowstone permutation:", |
|||
[limit(30;yellowstone)]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Plots |
||
function yellowstone(N) |
function yellowstone(N) |
||
Line 525: | Line 1,522: | ||
y = yellowstone(100) |
y = yellowstone(100) |
||
plot(x, y) |
plot(x, y) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
The first 30 entries of the Yellowstone permutation: |
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] |
[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> |
|||
[[File:Yellowstone-sequence-graph.png]] |
|||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="scala">fun main() { |
|||
println("First 30 values in the yellowstone sequence:") |
|||
println(yellowstoneSequence(30)) |
|||
} |
|||
private fun yellowstoneSequence(sequenceCount: Int): List<Int> { |
|||
val yellowstoneList = mutableListOf(1, 2, 3) |
|||
var num = 4 |
|||
val notYellowstoneList = mutableListOf<Int>() |
|||
var yellowSize = 3 |
|||
while (yellowSize < sequenceCount) { |
|||
var found = -1 |
|||
for (index in notYellowstoneList.indices) { |
|||
val test = notYellowstoneList[index] |
|||
if (gcd(yellowstoneList[yellowSize - 2], test) > 1 && gcd( |
|||
yellowstoneList[yellowSize - 1], test |
|||
) == 1 |
|||
) { |
|||
found = index |
|||
break |
|||
} |
|||
} |
|||
if (found >= 0) { |
|||
yellowstoneList.add(notYellowstoneList.removeAt(found)) |
|||
yellowSize++ |
|||
} else { |
|||
while (true) { |
|||
if (gcd(yellowstoneList[yellowSize - 2], num) > 1 && gcd( |
|||
yellowstoneList[yellowSize - 1], num |
|||
) == 1 |
|||
) { |
|||
yellowstoneList.add(num) |
|||
yellowSize++ |
|||
num++ |
|||
break |
|||
} |
|||
notYellowstoneList.add(num) |
|||
num++ |
|||
} |
|||
} |
|||
} |
|||
return yellowstoneList |
|||
} |
|||
private fun gcd(a: Int, b: Int): Int { |
|||
return if (b == 0) { |
|||
a |
|||
} else gcd(b, a % b) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 30 values 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]</pre> |
|||
=={{header|Lua}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="lua">function gcd(a, b) |
|||
if b == 0 then |
|||
return a |
|||
end |
|||
return gcd(b, a % b) |
|||
end |
|||
function printArray(a) |
|||
io.write('[') |
|||
for i,v in pairs(a) do |
|||
if i > 1 then |
|||
io.write(', ') |
|||
end |
|||
io.write(v) |
|||
end |
|||
io.write(']') |
|||
return nil |
|||
end |
|||
function removeAt(a, i) |
|||
local na = {} |
|||
for j,v in pairs(a) do |
|||
if j ~= i then |
|||
table.insert(na, v) |
|||
end |
|||
end |
|||
return na |
|||
end |
|||
function yellowstone(sequenceCount) |
|||
local yellow = {1, 2, 3} |
|||
local num = 4 |
|||
local notYellow = {} |
|||
local yellowSize = 3 |
|||
while yellowSize < sequenceCount do |
|||
local found = -1 |
|||
for i,test in pairs(notYellow) do |
|||
if gcd(yellow[yellowSize - 1], test) > 1 and gcd(yellow[yellowSize - 0], test) == 1 then |
|||
found = i |
|||
break |
|||
end |
|||
end |
|||
if found >= 0 then |
|||
table.insert(yellow, notYellow[found]) |
|||
notYellow = removeAt(notYellow, found) |
|||
yellowSize = yellowSize + 1 |
|||
else |
|||
while true do |
|||
if gcd(yellow[yellowSize - 1], num) > 1 and gcd(yellow[yellowSize - 0], num) == 1 then |
|||
table.insert(yellow, num) |
|||
yellowSize = yellowSize + 1 |
|||
num = num + 1 |
|||
break |
|||
end |
|||
table.insert(notYellow, num) |
|||
num = num + 1 |
|||
end |
|||
end |
|||
end |
|||
return yellow |
|||
end |
|||
function main() |
|||
print("First 30 values in the yellowstone sequence:") |
|||
printArray(yellowstone(30)) |
|||
print() |
|||
end |
|||
main()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 30 values 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]</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">state = {1, 2, 3}; |
|||
MakeNext[state_List] := Module[{i = First[state], done = False, out}, |
|||
While[! done, |
|||
If[FreeQ[state, i], |
|||
If[GCD[Last[state], i] == 1, |
|||
If[GCD[state[[-2]], i] > 1, |
|||
out = Append[state, i]; |
|||
done = True; |
|||
] |
|||
] |
|||
]; |
|||
i++; |
|||
]; |
|||
out |
|||
] |
|||
Nest[MakeNext, state, 30 - 3] |
|||
ListPlot[%]</syntaxhighlight> |
|||
{{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} |
|||
(* Graphical visualisation of the data *)</pre> |
|||
=={{header|Nim}}== |
|||
===Procedure version=== |
|||
This version uses a set and, so, is limited to 65536 elements. It is easy to change this limit by using a HashSet (standard module “sets”) instead of a set. See the iterator version which uses such a HashSet. |
|||
<syntaxhighlight lang="nim">import math |
|||
proc yellowstone(n: int): seq[int] = |
|||
assert n >= 3 |
|||
result = @[1, 2, 3] |
|||
var present = {1, 2, 3} |
|||
var start = 4 |
|||
while result.len < n: |
|||
var candidate = start |
|||
while true: |
|||
if candidate notin present and gcd(candidate, result[^1]) == 1 and gcd(candidate, result[^2]) != 1: |
|||
result.add candidate |
|||
present.incl candidate |
|||
while start in present: inc start |
|||
break |
|||
inc candidate |
|||
echo yellowstone(30)</syntaxhighlight> |
|||
{{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> |
|||
===Iterator version=== |
|||
This version uses a HashSet, but using a set as in the previous version is possible if we accept the limit of 65536 elements. |
|||
<syntaxhighlight lang="nim">import math, sets |
|||
iterator yellowstone(n: int): int = |
|||
assert n >= 3 |
|||
for i in 1..3: yield i |
|||
var present = [1, 2, 3].toHashSet |
|||
var prevLast = 2 |
|||
var last = 3 |
|||
var start = 4 |
|||
for _ in 4..n: |
|||
var candidate = start |
|||
while true: |
|||
if candidate notin present and gcd(candidate, last) == 1 and gcd(candidate, prevLast) != 1: |
|||
yield candidate |
|||
present.incl candidate |
|||
prevLast = last |
|||
last = candidate |
|||
while start in present: inc start |
|||
break |
|||
inc candidate |
|||
for n in yellowstone(30): |
|||
stdout.write " ", n |
|||
echo()</syntaxhighlight> |
|||
{{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|PARI/GP}}== |
|||
<syntaxhighlight lang="PARI/GP"> |
|||
yellowstone(n) = { |
|||
my(a=3, o=2, u=[]); |
|||
if(n<3, return(n)); \\ Base case: return n if it is less than 3 |
|||
print1("1, 2"); \\ Print initial values |
|||
for(i = 4, n, \\ Iterate from 4 to n |
|||
print1(", "a); \\ Print current value of a |
|||
u = setunion(u, Set(a)); \\ Add a to the set u |
|||
\\ Remove consecutive elements from u |
|||
while(#u > 1 && u[2] == u[1] + 1, |
|||
u = vecextract(u, "^1") |
|||
); |
|||
\\ Find next value of a |
|||
for(k = u[1] + 1, 1e10, |
|||
if(gcd(k, o) <= 1, next); \\ Skip if gcd(k, o) is greater than 1 |
|||
if(setsearch(u, k), next); \\ Skip if k is in set u |
|||
if(gcd(k, a) != 1, next); \\ Skip if gcd(k, a) is not 1 |
|||
o = a; \\ Update o to current a |
|||
a = k; \\ Update a to k |
|||
break |
|||
) |
|||
); |
|||
a \\ Return the final value of a |
|||
} |
|||
yellowstone(20); \\ Call the function with n = 20 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7, 10, 21, 20, 27 |
|||
</pre> |
</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 580: | Line 1,822: | ||
binmode $fh; |
binmode $fh; |
||
print $fh $gd->png(); |
print $fh $gd->png(); |
||
close $fh;</ |
close $fh;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 30 terms in the Yellowstone sequence: |
<pre>The first 30 terms in the Yellowstone sequence: |
||
Line 587: | Line 1,829: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{ |
{{libheader|Phix/pGUI}} |
||
{{libheader|Phix/online}} |
|||
<lang Phix>function yellowstone(integer N) |
|||
You can run this online [http://phix.x10.mx/p2js/Yellowstone.htm here]. |
|||
sequence a = {1, 2, 3}, |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
b = repeat(true,3) |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
integer i = 4 |
|||
-- demo\rosetta\Yellowstone_sequence.exw |
|||
while length(a) < N do |
|||
--</span> |
|||
if (i>length(b) or b[i]=false) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
and gcd(i,a[$])=1 |
|||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> |
|||
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 |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">yellowstone</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"The first 30 entries of the Yellowstone permutation:\n%v\n", {yellowstone(30)})</lang> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> |
|||
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[$])=</span><span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">b</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 30 entries of the Yellowstone permutation:\n%v\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">yellowstone</span><span style="color: #0000FF;">(</span><span style="color: #000000;">30</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #000080;font-style:italic;">-- a simple plot:</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #7060A8;">IupGraph</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">get_data</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000000;">graph</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">y500</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">yellowstone</span><span style="color: #0000FF;">(</span><span style="color: #000000;">500</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGetIntInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DRAWSIZE"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"XTICK"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;"><</span><span style="color: #000000;">640</span><span style="color: #0000FF;">?</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;"><</span><span style="color: #000000;">300</span><span style="color: #0000FF;">?</span><span style="color: #000000;">100</span><span style="color: #0000FF;">:</span><span style="color: #000000;">50</span><span style="color: #0000FF;">):</span><span style="color: #000000;">20</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YTICK"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;"><</span><span style="color: #000000;">250</span><span style="color: #0000FF;">?</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;"><</span><span style="color: #000000;">140</span><span style="color: #0000FF;">?</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;"><</span><span style="color: #000000;">120</span><span style="color: #0000FF;">?</span><span style="color: #000000;">700</span><span style="color: #0000FF;">:</span><span style="color: #000000;">350</span><span style="color: #0000FF;">):</span><span style="color: #000000;">200</span><span style="color: #0000FF;">):</span><span style="color: #000000;">100</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">500</span><span style="color: #0000FF;">),</span><span style="color: #000000;">y500</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_RED</span><span style="color: #0000FF;">}}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">graph</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGraph</span><span style="color: #0000FF;">(</span><span style="color: #000000;">get_data</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"RASTERSIZE=960x600"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetAttributes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">`GTITLE="Yellowstone Numbers"`</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TITLESTYLE"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_ITALIC</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetAttributes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">`XNAME="n", YNAME="a(n)"`</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetAttributes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"XTICK=20,XMIN=0,XMAX=500"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetAttributes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YTICK=100,YMIN=0,YMAX=1400"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">graph</span><span style="color: #0000FF;">,</span><span style="color: #008000;">`TITLE="Yellowstone Names"`</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupSetAttributes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MINSIZE=290x140"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">IupShow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 614: | Line 1,893: | ||
{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} |
{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> |
||
=== a simple plot === |
|||
=={{header|Phixmonti}}== |
|||
{{libheader|pGUI}} |
|||
{{trans|Ruby}}Require Utilitys library version 1.3 |
|||
<lang Phix>include pGUI.e |
|||
<syntaxhighlight lang="phixmonti">include ..\Utilitys.pmt |
|||
IupOpen() |
|||
IupControlsOpen() |
|||
def gcd /# u v -- n #/ |
|||
Ihandle plot = IupPlot("MENUITEMPROPERTIES=Yes, SIZE=640x320") |
|||
abs int swap abs int swap |
|||
IupSetAttribute(plot, "TITLE", "Yellowstone Numbers"); |
|||
IupSetAttribute(plot, "TITLEFONTSIZE", "10"); |
|||
dup |
|||
IupSetAttribute(plot, "TITLEFONTSTYLE", "ITALIC"); |
|||
while |
|||
IupSetAttribute(plot, "GRIDLINESTYLE", "DOTTED"); |
|||
over over mod rot drop dup |
|||
IupSetAttribute(plot, "GRID", "YES"); |
|||
endwhile |
|||
IupSetAttribute(plot, "AXS_XLABEL", "n"); |
|||
drop |
|||
IupSetAttribute(plot, "AXS_YLABEL", "a(n)"); |
|||
enddef |
|||
IupSetAttribute(plot, "AXS_XFONTSTYLE", "ITALIC"); |
|||
IupSetAttribute(plot, "AXS_YFONTSTYLE", "ITALIC"); |
|||
def test enddef |
|||
IupSetAttribute(plot, "AXS_YTICKSIZEAUTO", "NO"); |
|||
IupSetAttribute(plot, "AXS_YTICKMAJORSIZE", "8"); |
|||
def yellow var n |
|||
IupSetAttribute(plot, "AXS_YTICKMINORSIZE", "0"); |
|||
( 1 2 3 ) var a |
|||
IupPlotBegin(plot) |
|||
newd ( 1 true ) setd ( 2 true ) setd ( 3 true ) setd var b |
|||
sequence y500 = yellowstone(500) |
|||
4 var i |
|||
test |
|||
IupPlotAdd(plot, x, y500[x]) |
|||
while |
|||
end for |
|||
b i getd "Unfound" == >ps |
|||
{} = IupPlotEnd(plot) |
|||
a -1 get >ps -2 get |
|||
--IupSetAttribute(plot, "DS_MODE", "BAR") -- (optional) |
|||
i gcd 1 > ps> i gcd 1 == ps> |
|||
Ihandle dlg = IupDialog(plot) |
|||
and and if |
|||
IupCloseOnEscape(dlg) |
|||
i 0 put var a |
|||
IupSetAttribute(dlg, "TITLE", "Yellowstone Names") |
|||
( i true ) setd var b |
|||
IupMap(dlg) |
|||
4 var i |
|||
IupShowXY(dlg,IUP_CENTER,IUP_CENTER) |
|||
else |
|||
IupMainLoop() |
|||
drop drop |
|||
IupClose()</lang> |
|||
endif |
|||
i 1 + var i |
|||
test |
|||
endwhile |
|||
a |
|||
enddef |
|||
def test n a len nip > enddef |
|||
"The first 30 entries of the Yellowstone permutation:" ? 30 yellow ?</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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] |
|||
=== Press any key to exit ===</pre> |
|||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight lang="picolisp">(load "@lib/frac.l") |
|||
(de yellow (N) |
|||
(let (L (list 3 2 1) I 4 C 3 D) |
|||
(while (> N C) |
|||
(when |
|||
(and |
|||
(not (idx 'D I)) |
|||
(=1 (gcd I (get L 1))) |
|||
(> (gcd I (get L 2)) 1) ) |
|||
(push 'L I) |
|||
(idx 'D I T) |
|||
(setq I 4) |
|||
(inc 'C) ) |
|||
(inc 'I) ) |
|||
(flip L) ) ) |
|||
(println (yellow 30))</syntaxhighlight> |
|||
{{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|PureBasic}}== |
|||
<syntaxhighlight lang="purebasic">Procedure.i gcd(x.i,y.i) |
|||
While y<>0 : t=x : x=y : y=t%y : Wend : ProcedureReturn x |
|||
EndProcedure |
|||
If OpenConsole() |
|||
Dim Y.i(100) |
|||
For i=1 To 100 |
|||
If i<=3 : Y(i)=i : Continue : EndIf : k=3 |
|||
Repeat |
|||
RepLoop: |
|||
k+1 |
|||
For j=1 To i-1 : If Y(j)=k : Goto RepLoop : EndIf : Next |
|||
If gcd(k,Y(i-2))=1 Or gcd(k,Y(i-1))>1 : Continue : EndIf |
|||
Y(i)=k : Break |
|||
ForEver |
|||
Next |
|||
For i=1 To 30 : Print(Str(Y(i))+" ") : Next : Input() |
|||
EndIf</syntaxhighlight> |
|||
{{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|Python}}== |
=={{header|Python}}== |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Yellowstone permutation OEIS A098550''' |
||
from itertools import chain, count, islice |
from itertools import chain, count, islice |
||
Line 750: | Line 2,089: | ||
yield v |
yield v |
||
v = f(v) |
v = f(v) |
||
return |
return go |
||
Line 795: | Line 2,134: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{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|Quackery}}== |
|||
<code>gcd</code> is defined at [[Greatest common divisor#Quackery]]. |
|||
<syntaxhighlight lang="quackery"> [ stack ] is seqbits ( --> s ) |
|||
[ bit |
|||
seqbits take | |
|||
seqbits put ] is seqadd ( n --> ) |
|||
[ bit |
|||
seqbits share & not ] is notinseq ( n --> b ) |
|||
[ temp put |
|||
' [ 1 2 3 ] |
|||
7 seqbits put |
|||
4 |
|||
[ dip |
|||
[ dup -1 peek |
|||
over -2 peek ] |
|||
dup dip |
|||
[ tuck gcd 1 != |
|||
unrot gcd 1 = |
|||
and ] |
|||
swap if |
|||
[ dup dip join |
|||
seqadd |
|||
3 ] |
|||
[ 1+ |
|||
dup notinseq until ] |
|||
over size temp share |
|||
< not until ] |
|||
drop |
|||
seqbits release |
|||
temp take split drop ] is yellowstones ( n --> [ ) |
|||
30 yellowstones echo</syntaxhighlight> |
|||
{{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|Racket}}== |
|||
<syntaxhighlight lang="racket">#lang racket |
|||
(require plot) |
|||
(define a098550 |
|||
(let ((hsh# (make-hash '((1 . 1) (2 . 2) (3 . 3)))) |
|||
(rev# (make-hash '((1 . 1) (2 . 2) (3 . 3))))) |
|||
(λ (n) |
|||
(hash-ref hsh# n |
|||
(λ () |
|||
(let ((a_n (for/first ((i (in-naturals 4)) |
|||
#:unless (hash-has-key? rev# i) |
|||
#:when (and (= (gcd i (a098550 (- n 1))) 1) |
|||
(> (gcd i (a098550 (- n 2))) 1))) |
|||
i))) |
|||
(hash-set! hsh# n a_n) |
|||
(hash-set! rev# a_n n) |
|||
a_n)))))) |
|||
(map a098550 (range 1 (add1 30))) |
|||
(plot (points |
|||
(map (λ (i) (vector i (a098550 i))) (range 1 (add1 100)))))</syntaxhighlight> |
|||
{{out}} |
|||
Just the output text... you'll have to run this yourself in racket to see the plot! |
|||
<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|Raku}}== |
=={{header|Raku}}== |
||
Line 805: | Line 2,218: | ||
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. |
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 |
<syntaxhighlight lang="raku" line>my @yellowstone = 1, 2, 3, -> $q, $p { |
||
state @used = True xx 4; |
state @used = True xx 4; |
||
state $min = 3; |
state $min = 3; |
||
Line 839: | Line 2,252: | ||
$line.spurt: SVG.serialize: $chart.plot: :lines; |
$line.spurt: SVG.serialize: $chart.plot: :lines; |
||
$bars.spurt: SVG.serialize: $chart.plot: :bars;</ |
$bars.spurt: SVG.serialize: $chart.plot: :bars;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 30 terms in the Yellowstone sequence: |
<pre>The first 30 terms in the Yellowstone sequence: |
||
Line 848: | Line 2,261: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===horizontal list of numbers=== |
===horizontal list of numbers=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates any number of terms in the Yellowstone (permutation) sequence.*/ |
||
parse arg m . /*obtain optional argument from the CL.*/ |
parse arg m . /*obtain optional argument from the CL.*/ |
||
if m=='' | m=="," then m= 30 /*Not specified? Then use the default.*/ |
if m=='' | m=="," then m= 30 /*Not specified? Then use the default.*/ |
||
Line 858: | Line 2,271: | ||
do k=1; if !.k then iterate /*Already used? Then skip this number.*/ |
do k=1; if !.k then iterate /*Already used? Then skip this number.*/ |
||
if |
if gcd(k, @.prev)<2 then iterate /*Not meet requirement? Then skip it. */ |
||
if gcd(k, @.#) \==1 then iterate /* " " " " " " */ |
|||
#= #+1; @.#= k; !.k= 1; $= $ k /*bump ctr; assign; mark used; add list*/ |
#= #+1; @.#= k; !.k= 1; $= $ k /*bump ctr; assign; mark used; add list*/ |
||
leave /*find the next Yellowstone seq. number*/ |
leave /*find the next Yellowstone seq. number*/ |
||
Line 866: | Line 2,280: | ||
exit /*stick a fork in it, we're all done. */ |
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</ |
gcd: parse arg x,y; do until y==0; parse value x//y y with y x; end; return x</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input: <tt> 30 </tt>}} |
||
<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 |
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 |
||
Line 874: | Line 2,288: | ||
===vertical histogram plot=== |
===vertical histogram plot=== |
||
A horizontal histogram could also be shown, but it would require a taller (higher) plot with more vertical screen real estate. |
A horizontal histogram could also be shown, but it would require a taller (higher) plot with more vertical screen real estate. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates any number of terms in the Yellowstone (permutation) sequence.*/ |
||
parse arg m . /*obtain optional argument from the CL.*/ |
parse arg m . /*obtain optional argument from the CL.*/ |
||
if m=='' | m=="," then m= |
if m=='' | m=="," then m= 30 /*Not specified? Then use the default.*/ |
||
!.= 0 /*initialize an array of numbers(used).*/ |
!.= 0 /*initialize an array of numbers(used).*/ |
||
# = 0 /*count of Yellowstone numbers in seq. */ |
# = 0 /*count of Yellowstone numbers in seq. */ |
||
$ |
$ = /*list " " " " " */ |
||
do j=1 until #==m; prev= # - 1 |
do j=1 until #==m; prev= # - 1 |
||
if j<5 then do; #= #+1; @.#= j; !.#= j; !.j= 1; $= strip($ j); iterate; end |
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.*/ |
do k=1; if !.k then iterate /*Already used? Then skip this number.*/ |
||
if |
if gcd(k, @.prev)<2 then iterate /*Not meet requirement? Then skip it. */ |
||
if gcd(k, @.#) \==1 then iterate /* " " " " " " */ |
|||
#= # + 1; @.#= k; !.k= 1; $= $ k /*bump ctr; assign; mark used; add list*/ |
|||
leave /*find the next Yellowstone seq. number*/ |
leave /*find the next Yellowstone seq. number*/ |
||
end /*k*/ |
end /*k*/ |
||
end /*j*/ |
end /*j*/ |
||
call $histo $ '(vertical)' |
call $histo $ '(vertical)' /*invoke a REXX vertical histogram plot*/ |
||
exit /*stick a fork in it, we're all done. */ |
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</ |
gcd: parse arg x,y; do until y==0; parse value x//y y with y x; end; return x</syntaxhighlight> |
||
{{out|output|text= when using the |
{{out|output|text= when using the input: <tt> 532 </tt>}} |
||
The |
The plot is shown at three─quarter scale. |
||
<pre style="font-size:75%"> |
<pre style="font-size:75%"> |
||
■ |
|||
■ |
|||
│ |
|||
│ |
|||
│ |
|||
│ |
|||
│ |
|||
│ ■ |
|||
│ |
|||
■ │ │ |
|||
│ |
|||
│ │ ■ │ |
|||
│ |
|||
│ │ │ │ |
|||
│ |
|||
│ │ │ │ |
|||
│ |
|||
│ │ ■ │ │ |
|||
│ |
|||
│ │ │ │ │ |
|||
│ |
|||
│ │ │ │ │ |
|||
■ │ |
|||
│ │ ■ │ │ │ |
|||
│ │ |
|||
■ │ │ │ │ │ │ |
|||
│ │ |
|||
│ │ │ ■ │ │ │ │ |
|||
■ │ │ |
|||
│ │ │ │ │ ■ │ │ │ |
|||
│ │ │ |
|||
│ │ │ ■ │ │ │ │ │ │ |
|||
│ │ │ |
|||
■ │ │ │ ■ │ │ │ │ │ │ │ |
|||
│ │ │ |
|||
■ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
■ │ │ ■ │ |
|||
│ │ │ │ │ ■ │ │ │ │ │ │ │ │ |
|||
│ │ │ ■ │ │ |
|||
│ │ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
│ │ │ │ │ │ |
|||
│ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ |
|||
■ │ │ │ │ │ │ |
|||
│ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
│ │ │ │ │ │ │ |
|||
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
│ │ │ │ ■ │ │ │ |
|||
■ │ ■ │ │ │ │ │ │ │ │ │ │ │■│ │ │■│ |
|||
■ │ │ │ │ │ │ │ │ |
|||
■ │ │ │ │ │ │ │ │ │ │ │ │ │ │││ │ │││ |
|||
│ │ │ │ │ │ │ │ │ |
|||
■ │ │ │ ■ │ │ │ │ │ │ │ │ │ │■ │■│││ │ │││ |
|||
│ │ │ │ │ │ │ │ │ |
|||
│ │ │ │ │ │ │ │ │ │ │ │ │ │ ││ ■│││││ │■│││ |
|||
│ │ │ ■ │ │ │ │ │ │ |
|||
│ │ │ │ ■ │ │ │ │ │ │ │ │ │ │■││ ││││││■│││││ |
|||
│ │ │ │ │ │ │ │ │ │ |
|||
│ │ │ │ ■ │ │ │ │ ■ │ │ │ │ │ │■││││ ││││││││││││ |
|||
│ │ │ ■ │ │ │ │ │ │ │ |
|||
│ │ │ │ │ │ │ │ │ │ │ │ │■│■│ ││││││ ││││││││││││ |
|||
│ │ ■ │ │ │ │ │ │ │ │ │ |
|||
│ │ │ ■ │ │ │ │ │ │■│ │ │ │││││ ■││││││ ││││││││││││ |
|||
│ │ ■ │ │ │ │ │ │ │ │ │ │ |
|||
│ ■ │ │ │ │ │ │ │ │■│││ │ │■│││││ │││││││ ││││││││││││ |
|||
│ │ │ │ │ │ │ │ │ │ │ │ │ ■ |
|||
│ │ │ ■ │ │ │ │ │ │■ │││││ │ │││││││ │││││││ ││││││││││││ |
|||
│ │ │ │ │ │ │ │ │ │ │ │ ■ ■ │ │ |
|||
│ │ │ │ │ ■ │ │ │ │ ││ ■│││││ │■│││││││ │││││││ ││││││││││││ |
|||
■ │ │ │ │ │ │ │ │ │ │ ■ ■ │ │ ■ ■ ■ │ ■ │ │ ■ │ |
|||
│ ■ │ │ │ │ │ │ │ │ │■││ ││││││■│││││││││ │││││││ ││││││││││││ |
|||
│ ■ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ ■ │ │ │ │ ■ │ ■ ■ │ │ ■ │ │ │ ■ |
|||
■ │ │ │ │ │ │ │ │■ │■│ ││││ ││││││││││││││││ │││││││ ││││││││││││ |
|||
│ │ │ │ │ │ │ │ │ │ ■ │ │ ■ ■ │ │ │ ■ ■ │ ■ ■ │ │ │ │ │ │ ■ │ │ ■ │ ■ │ │ │ │ │ │ │ |
|||
│ │ │ │ │ ■ │ │ │ ││ ■│││ ││││ ││││││││││││││││ │││││││ ││││││││││││ |
|||
■ │ │ │ │ │ │ │ │ │ │ │ │ ■ ■ │ ■ ■ │ ■ ■ │ ■ │ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
■ │ │ │ │ │ │ │ │■│ ││ ││││■││││ ││││││││││││││││ │││││││ ■││││││││││││ |
|||
│ │ ■ │ │ │ │ │ │ │ │ ■ │ ■ │ │ ■ │ ■ │ │ ■ │ ■ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
│ │ │ │ │ │ │ │ ■│││■││ │││││││││ ││││││││││││││││ │││││││■│││││││││││││ |
|||
│ │ ■ │ │ │ │ │ │ │ │ ■ │ ■ │ │ ■ │ ■ │ │ │ │ │ │ │ │ │ ■ ■ ■ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ |
|||
■ │ │ │ │ │■│ │■│ │││││││ │││││││││ ││││││││││││││││■│││││││││││││││││││││ |
|||
│ │ ■ │ │ │ │ │ │ │ ■ │ │ ■ │ ■ ■ │ │ │ │ ■ ■ │ ■ │ ■ │ │ │ │ │ │ │ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■│ │ │ │ │ │ │ │ │ │ │ │ |
|||
■ │ ■ │ │ │ │■│││ │││ │││││││ │││││││││ ││││││││││││││││││││││││││││││││││││││ |
|||
│ │ │ │ │ │ │ ■ │ │ ■ │ ■ ■ │ │ ■ │ ■ ■ │ │ │ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■│ │ │ │ │■│■│ ││■│■│ │■│ │■│■│ ■│■│ ■│■│ |
|||
│ │ │ │ │■ │ │││││■│││ │││││││ │││││││││■■││││││││││││││││││││││││││││││││││││││ |
|||
│ │ │ │ │ ■ │ │ │ ■ ■ │ ■ │ ■ │ │ │ ■ │ │ │ │ ■ ■ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■│ │ │ │■│ │ │ │ │ │ │■│■│ ■│■│■│■│■│ ││■│■│ ■│■│││││ ││││││■│││■│││││ ││││ ││││ |
|||
│ ■ │ │■│■││ │ │││││││││ │││││││ │││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
■ │ │ │ │ │ │ │ ■ ■ │ ■ │ │ ■ ■ │ │ │ │ │ │ ■ │ │ ■ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│■│■│ ││■│■│■│││ │■│■│■│■│■│││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ |
|||
■ │ │■│ ││││││ │■│││││││││ │││││││■│││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
│ │ │ │ │ │ ■ ■ │ ■ ■ │ ■ │ ■ │ ■ │ │ │ ■ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│ ■│ │■│■│ ■│■│■│ ■│■│ ■│■│││││││││││││ ││││││││││■│││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ |
|||
│ │ ■■│││ ││││││ │││││││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
│ ■ │ │ │ │ │ ■ ■ │ │ │ ■ │ ■ │ ■ │ ■ │ │ │ ■ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│ ■│■│■│ ■│■│■│■│■│■│││││││││ ││■│││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ |
|||
■ │ │■ │││││ ││││││■■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
■ │ ■ │ │ │ │ ■ ■ │ ■ ■ │ ■ ■ │ │ ■ ■ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│ │■│■│ ■│■│■│■│ ■│■│■│■│■│ ■│││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ |
|||
│■ │■││ │││││ ■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
│ │ │ │ │ ■ │ ■ ■ │ ■ ■ ■ ■ │ │ ■ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│■│ ■│■│ ■│■│■│■│ ■│■│■│││││■│││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ |
|||
■■││ ││││ ■│││││■││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
│ ■ │ │ │ │ ■ ■ ■ ■ │ │ ■ │ │ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ ■│ │ │■│ │ │■│■│■│■│ ■│■│ ■│■│■│■│■│■│││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ |
|||
────┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴ |
|||
│ │ │ │ ■ │ ■ ■ ■ │ ■ ■ ■ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │■│ │■│■│■│■│■│■│■│■│■│■│ ││■│■│││ ■│■│││││││││ ││││ ││││││││││││││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││■││││││││││││││││■││││■││││ |
|||
1234981156213171222231132425311825363934361494546524157485862359696751616171713717181844818191718191 |
|||
│ ■ │ │ │ ■ ■ │ ■ ■ ■ │ ■ ■ ■ │ │ │ │ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│ │■│■│■│■│ ■│■│ ■│■│■│■│ ■│││■│││││││││││││││││││││ ││││││││ ││││││││││││ ││││ ││││││││││││││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││■││││││││││││││││││││││││││■││││││││││■││││││■│││││││││││││││││││││││││││││││││││ |
|||
54 5256 0107291336581278545456109839254709038125616729183498741036627407016102613228322844546 |
|||
■ │ │ │ ■ ■ ■ ■ │ ■ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│ ■│■│■│■│■ ■│■│■│■│■│ ■│││││ ■│││││││││ ││││ ││││││││ ││││││││││││││││││││││││││ ││││││││ ││││││││││││ ││││ ││││││││││││││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││■││││││■││││││││││││││││││││■││││││││■││││││■││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
5 9 3 1 5 5 1 7 3 9 5 5 5 5 5 |
|||
■ │ ■ ■ │ │ ■ ■ ■ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │■│ │■│■│■│ ■│■│■│■ ■│■│■│■│■│■■■│││││ │││││││││ ││││││││││ ││││││ ││││││││││ ││││ ││││││││ ││││││││││││││││││││││││││ ││││││││ ││││││││││││ ││││ ││││││││││││││││││││││■││││■││││││││■││││││││││││││││■││││││││■││││││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
■ ■ │ │ ■ ■ ■ ■ ■ ■ │ │ │ │ │ ■ │ │ │ │ │ ■ ■■│ │■│ ■│■│■│■│■ ■│■│■│■│■│ ■│││ ■│││││││ │││││││ ││││││││││││││││││ │││││││││ ││││││││││ ││││││ ││││││││││ ││││ ││││││││ ││││││││││││││││││││││││││■││││││││■││││││││││││■││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
■ ■ ■ ■ ■ │ │ │ │ ■ ■ │ │ │■│■│ │ │■│ ■│■│■│■│■│■│ ■│■│■│■│■│││ ■│││ │││││││││ ││││││││││ ││││ ││││││││ │││││││ ││││││││││││││││││■│││││││││■││││││││││■││││││■││││││││││■││││■││││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
■ ■ │ ■ │ ■ │ ■ ■ ■■ │■│■■ │■│■│■│■│ ■│■│■│■ ■│││││■│■│││ ││││││││││││ ││││││││││││■││││■│││││││││■││││││││││■││││■││││││││■│││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ |
|||
────────────┴───────┴──┴─┴─┴┴──┴─┴┴┴┴┴┴┴┴┴─┴┴┴┴┴┴┴─┴┴┴┴┴┴┴┴┴─┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴ |
|||
1234981156213171222231132425311825363934361494546524157485862359696751616171713717181844818191718191493921111911151211111111115111161411111216131212121271212713121212712121218151212121211121212812121212191612131322115222212322222223123231252323231252323232323232423242323221232323231262323242323124231292424232323242324242413134137343434137343434343434341313434341383434353513534343435138353513134353535353435363413135353513535351393514545454545454545246454646454546464546464646241464646452414646246464645256464646464647462414624746 |
|||
54 5256 0107291336581278545456109839254709038125616729183498741036627407016102613228322844546702600404850730608191412189172512228283037233031334214140346415350953646473585164657266747775986868799978788909107090090800009151912022100142024221263333353641344047454455582785668673555569606877381793777186898286939992919340004505040611518171222201527296312834356333748414274155575850749536586269617371667972828899375898699780919989790903031414171823143292030350806102824373241231424354552615857248636262309757253716871763868948285 |
|||
5 9 3 1 5 5 1 7 3 9 5 5 5 5 5 9 30741 361 258525634187 0729 074389016 6525458525 0367 45892189 4703490 016725652189476389 274189016 0967214525185456530987230945701839652545673852903618349410327658307497216907251258545658541701839036329496381072145658590421165458547725610309278143653048327437658545256530909276981985452510667810927416387092110343456732987437658590741670329638523123418309612985456309214765381458525497836585907094169369012307412965839072314387 |
|||
3 1 7 7 5 5 3 |
|||
</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
see "working..." + nl |
|||
row = 3 |
|||
num = 2 |
|||
numbers = 1:51 |
|||
first = 2 |
|||
second = 3 |
|||
see "Yellowstone numbers are:" + nl |
|||
see "1 " + first + " " + second + " " |
|||
for n = 4 to len(numbers) |
|||
flag1 = 1 |
|||
flag2 = 1 |
|||
if first < numbers[n] |
|||
min = first |
|||
else |
|||
min = numbers[n] |
|||
ok |
|||
for m = 2 to min |
|||
if first%m = 0 and numbers[n]%m = 0 |
|||
flag1 = 0 |
|||
exit |
|||
ok |
|||
next |
|||
if second < numbers[n] |
|||
min = second |
|||
else |
|||
min = numbers[n] |
|||
ok |
|||
for m = 2 to min |
|||
if second%m = 0 and numbers[n]%m = 0 |
|||
flag2 = 0 |
|||
exit |
|||
ok |
|||
next |
|||
if flag1 = 0 and flag2 = 1 |
|||
see "" + numbers[n] + " " |
|||
first = second |
|||
second = numbers[n] |
|||
del(numbers,n) |
|||
row = row+1 |
|||
if row%10 = 0 |
|||
see nl |
|||
ok |
|||
num = num + 1 |
|||
if num = 29 |
|||
exit |
|||
ok |
|||
n = 3 |
|||
ok |
|||
next |
|||
see "Found " + row + " Yellowstone numbers" + nl |
|||
see "done..." + nl |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
working... |
|||
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 |
|||
Found 30 Yellowstone numbers |
|||
done... |
|||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|Halcyon Calc|4.2.7}} |
|||
{| class="wikitable" |
|||
! Code |
|||
! Comments |
|||
|- |
|||
| |
|||
≪ |
|||
'''IF''' DUP2 < '''THEN''' SWAP '''END''' |
|||
'''WHILE''' DUP '''REPEAT''' SWAP OVER MOD '''END''' |
|||
DROP |
|||
≫ 'GCD' STO |
|||
≪ |
|||
DUP SIZE 1 - GETI ROT ROT GET → am2 am1 |
|||
≪ 3 '''DO''' |
|||
'''DO''' 1 + '''UNTIL''' DUP2 POS NOT '''END''' |
|||
'''UNTIL''' DUP am1 GCD 1 == OVER am2 GCD 1 ≠ AND '''END''' |
|||
+ |
|||
≫ ≫ 'YELLO' STO |
|||
| |
|||
''( a b -- gcd(a,b) )'' |
|||
Ensure a > b |
|||
Euclidean algorithm |
|||
''( { a(1)..a(n-1) } -- { a(1)..a(n) } )'' |
|||
Store locally a(n-1) and a(n-2) |
|||
Find smallest number not already in sequence |
|||
Check primality requirements |
|||
Add a(n) to the sequence |
|||
|} |
|||
The following words in the command line deliver what is required: |
|||
{ 1 2 3 } |
|||
≪ 1 27 START YELLO NEXT ≫ EVAL |
|||
{{out}} |
|||
<pre> |
|||
1: { 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|Ruby}}== |
|||
<syntaxhighlight lang="ruby">def yellow(n) |
|||
a = [1, 2, 3] |
|||
b = { 1 => true, 2 => true, 3 => true } |
|||
i = 4 |
|||
while n > a.length |
|||
if !b[i] && i.gcd(a[-1]) == 1 && i.gcd(a[-2]) > 1 |
|||
a << i |
|||
b[i] = true |
|||
i = 4 |
|||
end |
|||
i += 1 |
|||
end |
|||
a |
|||
end |
|||
p yellow(30)</syntaxhighlight> |
|||
{{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|Rust}}== |
|||
<syntaxhighlight lang="rust">// [dependencies] |
|||
// num = "0.3" |
|||
// plotters = "^0.2.15" |
|||
use num::integer::gcd; |
|||
use plotters::prelude::*; |
|||
use std::collections::HashSet; |
|||
fn yellowstone_sequence() -> impl std::iter::Iterator<Item = u32> { |
|||
let mut sequence: HashSet<u32> = HashSet::new(); |
|||
let mut min = 1; |
|||
let mut n = 0; |
|||
let mut n1 = 0; |
|||
let mut n2 = 0; |
|||
std::iter::from_fn(move || { |
|||
n2 = n1; |
|||
n1 = n; |
|||
if n < 3 { |
|||
n += 1; |
|||
} else { |
|||
n = min; |
|||
while !(!sequence.contains(&n) && gcd(n1, n) == 1 && gcd(n2, n) > 1) { |
|||
n += 1; |
|||
} |
|||
} |
|||
sequence.insert(n); |
|||
while sequence.contains(&min) { |
|||
sequence.remove(&min); |
|||
min += 1; |
|||
} |
|||
Some(n) |
|||
}) |
|||
} |
|||
// Based on the example in the "Quick Start" section of the README file for |
|||
// the plotters library. |
|||
fn plot_yellowstone(filename: &str) -> Result<(), Box<dyn std::error::Error>> { |
|||
let root = BitMapBackend::new(filename, (800, 600)).into_drawing_area(); |
|||
root.fill(&WHITE)?; |
|||
let mut chart = ChartBuilder::on(&root) |
|||
.caption("Yellowstone Sequence", ("sans-serif", 24).into_font()) |
|||
.margin(10) |
|||
.x_label_area_size(20) |
|||
.y_label_area_size(20) |
|||
.build_ranged(0usize..100usize, 0u32..180u32)?; |
|||
chart.configure_mesh().draw()?; |
|||
chart.draw_series(LineSeries::new( |
|||
yellowstone_sequence().take(100).enumerate(), |
|||
&BLUE, |
|||
))?; |
|||
Ok(()) |
|||
} |
|||
fn main() { |
|||
println!("First 30 Yellowstone numbers:"); |
|||
for y in yellowstone_sequence().take(30) { |
|||
print!("{} ", y); |
|||
} |
|||
println!(); |
|||
match plot_yellowstone("yellowstone.png") { |
|||
Ok(()) => {} |
|||
Err(error) => eprintln!("Error: {}", error), |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
A plot of the first 100 Yellowstone numbers is saved to the file "yellowstone.png". |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
[[Media:Yellowstone sequence rust.png]] |
|||
=={{header|Scala}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="Scala"> |
|||
import scala.util.control.Breaks._ |
|||
object YellowstoneSequence extends App { |
|||
println(s"First 30 values in the yellowstone sequence:\n${yellowstoneSequence(30)}") |
|||
def yellowstoneSequence(sequenceCount: Int): List[Int] = { |
|||
var yellowstoneList = List(1, 2, 3) |
|||
var num = 4 |
|||
var notYellowstoneList = List[Int]() |
|||
while (yellowstoneList.size < sequenceCount) { |
|||
val foundIndex = notYellowstoneList.indexWhere(test => |
|||
gcd(yellowstoneList(yellowstoneList.size - 2), test) > 1 && |
|||
gcd(yellowstoneList.last, test) == 1 |
|||
) |
|||
if (foundIndex >= 0) { |
|||
yellowstoneList = yellowstoneList :+ notYellowstoneList(foundIndex) |
|||
notYellowstoneList = notYellowstoneList.patch(foundIndex, Nil, 1) |
|||
} else { |
|||
breakable({ |
|||
while (true) { |
|||
if (gcd(yellowstoneList(yellowstoneList.size - 2), num) > 1 && |
|||
gcd(yellowstoneList.last, num) == 1) { |
|||
yellowstoneList = yellowstoneList :+ num |
|||
num += 1 |
|||
// break the inner while loop |
|||
break |
|||
} |
|||
notYellowstoneList = notYellowstoneList :+ num |
|||
num += 1 |
|||
} |
|||
}); |
|||
} |
|||
} |
|||
yellowstoneList |
|||
} |
|||
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 30 values in the yellowstone sequence: |
|||
List(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|Tcl}}== |
|||
<syntaxhighlight lang="tcl">proc gcd {a b} { |
|||
while {$b} { |
|||
lassign [list $b [expr {$a % $b}]] a b |
|||
} |
|||
return $a |
|||
} |
|||
proc gen_yellowstones {{maxN 30}} { |
|||
set r {} |
|||
for {set n 1} {$n <= $maxN} {incr n} { |
|||
if {$n <= 3} { |
|||
lappend r $n |
|||
} else { |
|||
## NB: list indices start at 0, not 1. |
|||
set pred [lindex $r end ] ;# a(n-1): coprime |
|||
set prepred [lindex $r end-1] ;# a(n-2): not coprime |
|||
for {set k 4} {1} {incr k} { |
|||
if {[lsearch -exact $r $k] >= 0} { continue } |
|||
if {1 != [gcd $k $pred ]} { continue } |
|||
if {1 == [gcd $k $prepred]} { continue } |
|||
## candidate k survived all tests... |
|||
break |
|||
} |
|||
lappend r $k |
|||
} |
|||
} |
|||
return $r |
|||
} |
|||
puts "The first 30 Yellowstone numbers are:" |
|||
puts [gen_yellowstones]</syntaxhighlight> |
|||
{{out}} |
|||
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 |
|||
=={{header|uBasic/4tH}}== |
|||
{{trans|VBA}} |
|||
{{works with|v3.64.0}} |
|||
<syntaxhighlight lang="text">Dim @y(30) |
|||
@y(0) = 1 |
|||
@y(1) = 2 |
|||
@y(2) = 3 |
|||
For i = 3 To 29 |
|||
k = 3 |
|||
Do |
|||
k = k + 1 |
|||
If (FUNC(_gcd(k, @y(i-2))) = 1) + (FUNC(_gcd(k, @y(i-1))) > 1) Then |
|||
Continue |
|||
EndIf |
|||
For j = 0 To i - 1 |
|||
If @y(j) = k Then Unloop : Continue |
|||
Next |
|||
@y(i) = k : Break |
|||
Loop |
|||
Next |
|||
For i = 0 To 29 |
|||
Print @y(i); " "; |
|||
Next |
|||
Print : End |
|||
_gcd Param (2) |
|||
If b@ = 0 Then Return (a@) |
|||
Return (FUNC(_gcd(b@, a@ % b@)))</syntaxhighlight> |
|||
{{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 |
|||
0 OK, 0:670 |
|||
</pre> |
|||
=={{header|VBA}}== |
|||
<syntaxhighlight lang="tcl"> |
|||
Function gcd(a As Long, b As Long) As Long |
|||
If b = 0 Then |
|||
gcd = a |
|||
Exit Function |
|||
End If |
|||
gcd = gcd(b, a Mod b) |
|||
End Function |
|||
Sub Yellowstone() |
|||
Dim i As Long, j As Long, k As Long, Y(1 To 30) As Long |
|||
Y(1) = 1 |
|||
Y(2) = 2 |
|||
Y(3) = 3 |
|||
For i = 4 To 30 |
|||
k = 3 |
|||
Do |
|||
k = k + 1 |
|||
If gcd(k, Y(i - 2)) = 1 Or gcd(k, Y(i - 1)) > 1 Then GoTo EndLoop: |
|||
For j = 1 To i - 1 |
|||
If Y(j) = k Then GoTo EndLoop: |
|||
Next j |
|||
Y(i) = k |
|||
Exit Do |
|||
EndLoop: |
|||
Loop |
|||
Next i |
|||
For i = 1 To 30 |
|||
Debug.Print Y(i) & " "; |
|||
Next i |
|||
End Sub |
|||
</syntaxhighlight> |
|||
{{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|V (Vlang)}}== |
|||
{{trans|go}} |
|||
<syntaxhighlight lang="v (vlang)">fn gcd(xx int, yy int) int { |
|||
mut x := xx |
|||
mut y := yy |
|||
for y != 0 { |
|||
x, y = y, x%y |
|||
} |
|||
return x |
|||
} |
|||
fn yellowstone(n int) []int { |
|||
mut m := map[int]bool{} |
|||
mut a := []int{len: n+1} |
|||
for i in 1..4 { |
|||
a[i] = i |
|||
m[i] = true |
|||
} |
|||
mut 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..] |
|||
} |
|||
fn main() { |
|||
mut x := []int{len: 100} |
|||
for i in 0..100 { |
|||
x[i] = i + 1 |
|||
} |
|||
y := yellowstone(100) |
|||
println("The first 30 Yellowstone numbers are:") |
|||
println(y[..30]) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
{{libheader|Wren-math}} |
|||
Without the extra credit part. |
|||
<syntaxhighlight lang="wren">import "./math" for Int |
|||
var yellowstone = Fn.new { |n| |
|||
var m = {} |
|||
var a = List.filled(n + 1, 0) |
|||
for (i in 1..3) { |
|||
a[i] = i |
|||
m[i] = true |
|||
} |
|||
var min = 4 |
|||
for (c in 4..n) { |
|||
var i = min |
|||
while (true) { |
|||
if (!m[i] && Int.gcd(a[c-1], i) == 1 && Int.gcd(a[c-2], i) > 1) { |
|||
a[c] = i |
|||
m[i] = true |
|||
if (i == min) min = min + 1 |
|||
break |
|||
} |
|||
i = i + 1 |
|||
} |
|||
} |
|||
return a[1..-1] |
|||
} |
|||
var x = List.filled(30, 0) |
|||
for (i in 0...30) x[i] = i + 1 |
|||
var y = yellowstone.call(30) |
|||
System.print("The first 30 Yellowstone numbers are:") |
|||
System.print(y)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang="xpl0">func GCD(N, D); \Return the greatest common divisor of N and D |
|||
int N, D, R; \numerator, denominator, remainder |
|||
[if D > N then |
|||
[R:=D; D:=N; N:=R]; \swap D and N |
|||
while D > 0 do |
|||
[R:= rem(N/D); |
|||
N:= D; |
|||
D:= R; |
|||
]; |
|||
return N; |
|||
]; |
|||
int I, A(30+1), N, T; |
|||
[for I:= 1 to 3 do A(I):= I; \givens |
|||
N:= 4; |
|||
repeat T:= 4; |
|||
loop [if GCD(T, A(N-1)) = 1 and \relatively prime |
|||
GCD(T, A(N-2)) # 1 then \not relatively prime |
|||
[loop [for I:= 1 to N-1 do \test if in sequence |
|||
if T = A(I) then quit; |
|||
quit; |
|||
]; |
|||
if I = N then \T is not in sequence so |
|||
[A(N):= T; \ add it in |
|||
N:= N+1; |
|||
quit; |
|||
]; |
|||
]; |
|||
T:= T+1; \next trial |
|||
]; |
|||
until N > 30; |
|||
for N:= 1 to 30 do |
|||
[IntOut(0, A(N)); ChOut(0, ^ )]; |
|||
\\for N:= 1 to 100 do Point(N, A(N)); \plot demonstration |
|||
]</syntaxhighlight> |
|||
{{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> |
||
Line 955: | Line 2,890: | ||
{{trans|Julia}} |
{{trans|Julia}} |
||
This sequence is limited to the max size of a Dictionary, 64k |
This sequence is limited to the max size of a Dictionary, 64k |
||
< |
<syntaxhighlight lang="zkl">fcn yellowstoneW{ // --> iterator |
||
Walker.zero().tweak(fcn(a,b){ |
Walker.zero().tweak(fcn(a,b){ |
||
foreach i in ([1..]){ |
foreach i in ([1..]){ |
||
Line 965: | Line 2,900: | ||
} |
} |
||
}.fp(List(2,3), Dictionary(1,True, 2,True, 3,True))).push(1,2,3); |
}.fp(List(2,3), Dictionary(1,True, 2,True, 3,True))).push(1,2,3); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">println("The first 30 entries of the Yellowstone permutation:"); |
||
yellowstoneW().walk(30).concat(", ").println();</ |
yellowstoneW().walk(30).concat(", ").println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 974: | Line 2,909: | ||
</pre> |
</pre> |
||
Plot using Gnuplot |
Plot using Gnuplot |
||
< |
<syntaxhighlight lang="zkl">gnuplot:=System.popen("gnuplot","w"); |
||
gnuplot.writeln("unset key; plot '-'"); |
gnuplot.writeln("unset key; plot '-'"); |
||
yellowstoneW().pump(1_000, gnuplot.writeln.fp(" ")); // " 1\n", " 2\n", ... |
yellowstoneW().pump(1_000, gnuplot.writeln.fp(" ")); // " 1\n", " 2\n", ... |
||
gnuplot.writeln("e"); |
gnuplot.writeln("e"); |
||
gnuplot.flush(); |
gnuplot.flush(); |
||
ask("Hit return to finish"); gnuplot.close();</ |
ask("Hit return to finish"); gnuplot.close();</syntaxhighlight> |
||
Offsite Image: [http://www.zenkinetic.com/Images/RosettaCode/yellowstone1000.zkl.png yellowstone] |
Offsite Image: [http://www.zenkinetic.com/Images/RosettaCode/yellowstone1000.zkl.png yellowstone] |
Revision as of 19:24, 9 March 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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].
11l
T YellowstoneGenerator
min_ = 1
n_ = 0
n1_ = 0
n2_ = 0
Set[Int] sequence_
F next()
.n2_ = .n1_
.n1_ = .n_
I .n_ < 3
.n_++
E
.n_ = .min_
L !(.n_ !C .sequence_ & gcd(.n1_, .n_) == 1 & gcd(.n2_, .n_) > 1)
.n_++
.sequence_.add(.n_)
L
I .min_ !C .sequence_
L.break
.sequence_.remove(.min_)
.min_++
R .n_
print(‘First 30 Yellowstone numbers:’)
V ygen = YellowstoneGenerator()
print(ygen.next(), end' ‘’)
L(i) 1 .< 30
print(‘ ’ygen.next(), end' ‘’)
print()
- 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
F yellow(n)
V a = [1, 2, 3]
V b = Set([1, 2, 3])
V i = 4
L n > a.len
I i !C b & gcd(i, a.last) == 1 & gcd(i, a[(len)-2]) > 1
a.append(i)
b.add(i)
i = 4
i++
R a
print(yellow(30))
- 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]
Action!
BYTE FUNC Gcd(BYTE a,b)
BYTE tmp
IF a<b THEN
tmp=a a=b b=tmp
FI
WHILE b#0
DO
tmp=a MOD b
a=b b=tmp
OD
RETURN (a)
BYTE FUNC Contains(BYTE ARRAY a BYTE len,value)
BYTE i
FOR i=0 TO len-1
DO
IF a(i)=value THEN
RETURN (1)
FI
OD
RETURN (0)
PROC Generate(BYTE ARRAY seq BYTE count)
BYTE i,x
seq(0)=1 seq(1)=2 seq(2)=3
FOR i=3 TO COUNT-1
DO
x=1
DO
IF Contains(seq,i,x)=0 AND
Gcd(x,seq(i-1))=1 AND Gcd(x,seq(i-2))>1 THEN
EXIT
FI
x==+1
OD
seq(i)=x
OD
RETURN
PROC Main()
DEFINE COUNT="30"
BYTE ARRAY seq(COUNT)
BYTE i
Generate(seq,COUNT)
PrintF("First %B Yellowstone numbers:%E",COUNT)
FOR i=0 TO COUNT-1
DO
PrintB(seq(i)) Put(32)
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
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
Ada
with Ada.Text_IO;
with Ada.Containers.Ordered_Sets;
procedure Yellowstone_Sequence is
generic -- Allow more than one generator, but must be instantiated
package Yellowstones is
function Next return Integer;
function GCD (Left, Right : Integer) return Integer;
end Yellowstones;
package body Yellowstones
is
package Sequences is
new Ada.Containers.Ordered_Sets (Integer);
-- Internal package state
N_0 : Integer := 0;
N_1 : Integer := 0;
N_2 : Integer := 0;
Seq : Sequences.Set;
Min : Integer := 1;
function GCD (Left, Right : Integer) return Integer
is (if Right = 0
then Left
else GCD (Right, Left mod Right));
function Next return Integer is
begin
N_2 := N_1;
N_1 := N_0;
if N_0 < 3 then
N_0 := N_0 + 1;
else
N_0 := Min;
while
not (not Seq.Contains (N_0)
and then GCD (N_1, N_0) = 1
and then GCD (N_2, N_0) > 1)
loop
N_0 := N_0 + 1;
end loop;
end if;
Seq.Insert (N_0);
while Seq.Contains (Min) loop
Seq.Delete (Min);
Min := Min + 1;
end loop;
return N_0;
end Next;
end Yellowstones;
procedure First_30 is
package Yellowstone is new Yellowstones; -- New generator instance
use Ada.Text_IO;
begin
Put_Line ("First 30 Yellowstone numbers:");
for A in 1 .. 30 loop
Put (Yellowstone.Next'Image); Put (" ");
end loop;
New_Line;
end First_30;
begin
First_30;
end Yellowstone_Sequence;
- 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
ALGOL 68
BEGIN # find members of the yellowstone sequence: starting from 1, 2, 3 the #
# subsequent members are the lowest number coprime to the previous one #
# and not coprime to the one before that, that haven't appeared in the #
# sequence yet #
# iterative Greatest Common Divisor routine, returns the gcd of m and n #
PROC gcd = ( INT m, n )INT:
BEGIN
INT a := ABS m, b := ABS n;
WHILE b /= 0 DO
INT new a = b;
b := a MOD b;
a := new a
OD;
a
END # gcd # ;
# returns an array of the Yellowstone seuence up to n #
OP YELLOWSTONE = ( INT n )[]INT:
BEGIN
[ 1 : n ]INT result;
IF n > 0 THEN
result[ 1 ] := 1;
IF n > 1 THEN
result[ 2 ] := 2;
IF n > 2 THEN
result[ 3 ] := 3;
# guess the maximum element will be n, if it is larger, used will be enlarged #
REF[]BOOL used := HEAP[ 1 : n ]BOOL;
used[ 1 ] := used[ 2 ] := used[ 3 ] := TRUE;
FOR i FROM 4 TO UPB used DO used[ i ] := FALSE OD;
FOR i FROM 4 TO UPB result DO
INT p1 = result[ i - 1 ];
INT p2 = result[ i - 2 ];
BOOL found := FALSE;
FOR j WHILE NOT found DO
IF j > UPB used THEN
# not enough elements in used - enlarge it #
REF[]BOOL new used := HEAP[ 1 : 2 * UPB used ]BOOL;
new used[ 1 : UPB used ] := used;
FOR k FROM UPB used + 1 TO UPB new used DO new used[ k ] := FALSE OD;
used := new used
FI;
IF NOT used[ j ] THEN
IF found := gcd( j, p1 ) = 1 AND gcd( j, p2 ) /= 1
THEN
result[ i ] := j;
used[ j ] := TRUE
FI
FI
OD
OD
FI
FI
FI;
result
END # YELLOWSTONE # ;
[]INT ys = YELLOWSTONE 30;
FOR i TO UPB ys DO
print( ( " ", whole( ys[ i ], 0 ) ) )
OD
END
- 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
Arturo
yellowstone: function [n][
result: new [1 2 3]
present: new [1 2 3]
start: new 4
while [n > size result][
candidate: new start
while ø [
if all? @[
not? contains? present candidate
1 = gcd @[candidate last result]
1 <> gcd @[candidate get result (size result)-2]
][
'result ++ candidate
'present ++ candidate
while [contains? present start] -> inc 'start
break
]
inc 'candidate
]
]
return result
]
print yellowstone 30
- 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
AutoHotkey
A := [], in_seq := []
loop 30 {
n := A_Index
if n <=3
A[n] := n, in_seq[n] := true
else while true
{
s := A_Index
if !in_seq[s] && relatively_prime(s, A[n-1]) && !relatively_prime(s, A[n-2])
{
A[n] := s
in_seq[s] := true
break
}
}
}
for i, v in A
result .= v ","
MsgBox % result := "[" Trim(result, ",") "]"
return
;--------------------------------------
relatively_prime(a, b){
return (GCD(a, b) = 1)
}
;--------------------------------------
GCD(a, b) {
while b
b := Mod(a | 0x0, a := b)
return a
}
- 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]
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct lnode_t {
struct lnode_t *prev;
struct lnode_t *next;
int v;
} Lnode;
Lnode *make_list_node(int v) {
Lnode *node = malloc(sizeof(Lnode));
if (node == NULL) {
return NULL;
}
node->v = v;
node->prev = NULL;
node->next = NULL;
return node;
}
void free_lnode(Lnode *node) {
if (node == NULL) {
return;
}
node->v = 0;
node->prev = NULL;
free_lnode(node->next);
node->next = NULL;
}
typedef struct list_t {
Lnode *front;
Lnode *back;
size_t len;
} List;
List *make_list() {
List *list = malloc(sizeof(List));
if (list == NULL) {
return NULL;
}
list->front = NULL;
list->back = NULL;
list->len = 0;
return list;
}
void free_list(List *list) {
if (list == NULL) {
return;
}
list->len = 0;
list->back = NULL;
free_lnode(list->front);
list->front = NULL;
}
void list_insert(List *list, int v) {
Lnode *node;
if (list == NULL) {
return;
}
node = make_list_node(v);
if (list->front == NULL) {
list->front = node;
list->back = node;
list->len = 1;
} else {
node->prev = list->back;
list->back->next = node;
list->back = node;
list->len++;
}
}
void list_print(List *list) {
Lnode *it;
if (list == NULL) {
return;
}
for (it = list->front; it != NULL; it = it->next) {
printf("%d ", it->v);
}
}
int list_get(List *list, int idx) {
Lnode *it = NULL;
if (list != NULL && list->front != NULL) {
int i;
if (idx < 0) {
it = list->back;
i = -1;
while (it != NULL && i > idx) {
it = it->prev;
i--;
}
} else {
it = list->front;
i = 0;
while (it != NULL && i < idx) {
it = it->next;
i++;
}
}
}
if (it == NULL) {
return INT_MIN;
}
return it->v;
}
///////////////////////////////////////
typedef struct mnode_t {
int k;
bool v;
struct mnode_t *next;
} Mnode;
Mnode *make_map_node(int k, bool v) {
Mnode *node = malloc(sizeof(Mnode));
if (node == NULL) {
return node;
}
node->k = k;
node->v = v;
node->next = NULL;
return node;
}
void free_mnode(Mnode *node) {
if (node == NULL) {
return;
}
node->k = 0;
node->v = false;
free_mnode(node->next);
node->next = NULL;
}
typedef struct map_t {
Mnode *front;
} Map;
Map *make_map() {
Map *map = malloc(sizeof(Map));
if (map == NULL) {
return NULL;
}
map->front = NULL;
return map;
}
void free_map(Map *map) {
if (map == NULL) {
return;
}
free_mnode(map->front);
map->front = NULL;
}
void map_insert(Map *map, int k, bool v) {
if (map == NULL) {
return;
}
if (map->front == NULL) {
map->front = make_map_node(k, v);
} else {
Mnode *it = map->front;
while (it->next != NULL) {
it = it->next;
}
it->next = make_map_node(k, v);
}
}
bool map_get(Map *map, int k) {
if (map != NULL) {
Mnode *it = map->front;
while (it != NULL && it->k != k) {
it = it->next;
}
if (it != NULL) {
return it->v;
}
}
return false;
}
///////////////////////////////////////
int gcd(int u, int v) {
if (u < 0) u = -u;
if (v < 0) v = -v;
if (v) {
while ((u %= v) && (v %= u));
}
return u + v;
}
List *yellow(size_t n) {
List *a;
Map *b;
int i;
a = make_list();
list_insert(a, 1);
list_insert(a, 2);
list_insert(a, 3);
b = make_map();
map_insert(b, 1, true);
map_insert(b, 2, true);
map_insert(b, 3, true);
i = 4;
while (n > a->len) {
if (!map_get(b, i) && gcd(i, list_get(a, -1)) == 1 && gcd(i, list_get(a, -2)) > 1) {
list_insert(a, i);
map_insert(b, i, true);
i = 4;
}
i++;
}
free_map(b);
return a;
}
int main() {
List *a = yellow(30);
list_print(a);
free_list(a);
putc('\n', stdout);
return 0;
}
- 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
C++
#include <iostream>
#include <numeric>
#include <set>
template <typename integer>
class yellowstone_generator {
public:
integer next() {
n2_ = n1_;
n1_ = n_;
if (n_ < 3) {
++n_;
} else {
for (n_ = min_; !(sequence_.count(n_) == 0
&& std::gcd(n1_, n_) == 1
&& std::gcd(n2_, n_) > 1); ++n_) {}
}
sequence_.insert(n_);
for (;;) {
auto it = sequence_.find(min_);
if (it == sequence_.end())
break;
sequence_.erase(it);
++min_;
}
return n_;
}
private:
std::set<integer> sequence_;
integer min_ = 1;
integer n_ = 0;
integer n1_ = 0;
integer n2_ = 0;
};
int main() {
std::cout << "First 30 Yellowstone numbers:\n";
yellowstone_generator<unsigned int> ygen;
std::cout << ygen.next();
for (int i = 1; i < 30; ++i)
std::cout << ' ' << ygen.next();
std::cout << '\n';
return 0;
}
- 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
D
import std.numeric;
import std.range;
import std.stdio;
class Yellowstone {
private bool[int] sequence_;
private int min_ = 1;
private int n_ = 0;
private int n1_ = 0;
private int n2_ = 0;
public this() {
popFront();
}
public bool empty() {
return false;
}
public int front() {
return n_;
}
public void popFront() {
n2_ = n1_;
n1_ = n_;
if (n_ < 3) {
++n_;
} else {
for (n_ = min_;
!(n_ !in sequence_ && gcd(n1_, n_) == 1 && gcd(n2_, n_) > 1);
++n_) {
// empty
}
}
sequence_[n_] = true;
while (true) {
if (min_ !in sequence_) {
break;
}
sequence_.remove(min_);
++min_;
}
}
}
void main() {
new Yellowstone().take(30).writeln();
}
- 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]
Delphi
Boost.Generics.Collection and Boost.Process are part of DelphiBoostLib.
program Yellowstone_sequence;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
Boost.Generics.Collection,
Boost.Process;
function gdc(x, y: Integer): Integer;
begin
while y <> 0 do
begin
var tmp := x;
x := y;
y := tmp mod y;
end;
Result := x;
end;
function Yellowstone(n: Integer): TArray<Integer>;
var
m: TDictionary<Integer, Boolean>;
a: TArray<Integer>;
begin
m.Init;
SetLength(a, n + 1);
for var i := 1 to 3 do
begin
a[i] := i;
m[i] := True;
end;
var min := 4;
for var c := 4 to n do
begin
var i := min;
repeat
if not m[i, false] and (gdc(a[c - 1], i) = 1) and (gdc(a[c - 2], i) > 1) then
begin
a[c] := i;
m[i] := true;
if i = min then
inc(min);
Break;
end;
inc(i);
until false;
end;
Result := copy(a, 1, length(a));
end;
begin
var x: TArray<Integer>;
SetLength(x, 100);
for var i in Range(100) do
x[i] := i + 1;
var y := yellowstone(High(x));
writeln('The first 30 Yellowstone numbers are:');
for var i := 0 to 29 do
Write(y[i], ' ');
Writeln;
//Plotting
var plot := TPipe.Create('gnuplot -p', True);
plot.WritelnA('unset key; plot ''-''');
for var i := 0 to High(x) do
plot.WriteA('%d %d'#10, [x[i], y[i]]);
plot.WritelnA('e');
writeln('Press enter to close');
Readln;
plot.Kill;
plot.Free;
end.
- 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 Press enter to close
EasyLang
func gcd a b .
if b = 0
return a
.
return gcd b (a mod b)
.
proc remove_at i . a[] .
for j = i + 1 to len a[]
a[j - 1] = a[j]
.
len a[] -1
.
proc yellowstone count . yellow[] .
yellow[] = [ 1 2 3 ]
num = 4
while len yellow[] < count
yell1 = yellow[len yellow[] - 1]
yell2 = yellow[len yellow[]]
for i to len notyellow[]
test = notyellow[i]
if gcd yell1 test > 1 and gcd yell2 test = 1
break 1
.
.
if i <= len notyellow[]
yellow[] &= notyellow[i]
remove_at i notyellow[]
else
while gcd yell1 num <= 1 or gcd yell2 num <> 1
notyellow[] &= num
num += 1
.
yellow[] &= num
num += 1
.
.
.
print "First 30 values in the yellowstone sequence:"
yellowstone 30 yellow[]
print yellow[]
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
- 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
Forth
: array create cells allot ;
: th cells + ; \ some helper words
30 constant #yellow \ number of yellowstones
#yellow array y \ create array
( n1 n2 -- n3)
: gcd dup if tuck mod recurse exit then drop ;
: init 3 0 do i 1+ y i th ! loop ; ( --)
: show cr #yellow 0 do y i th ? loop ; ( --)
: gcd-y[] - cells y + @ over gcd ; ( k i n -- k gcd )
: loop1 begin 1+ over 2 gcd-y[] 1 = >r over 1 gcd-y[] 1 > r> or 0= until ;
: loop2 over true swap 0 ?do over y i th @ = if 0= leave then loop ;
: yellow #yellow 3 do i 3 begin loop1 loop2 until y rot th ! loop ;
: main init yellow show ;
main
- Output:
main 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 ok
FreeBASIC
function gcd(a as uinteger, b as uinteger) as uinteger
if b = 0 then return a
return gcd( b, a mod b )
end function
dim as uinteger i, j, k, Y(1 to 100)
Y(1) = 1 : Y(2) = 2: Y(3) = 3
for i = 4 to 100
k = 3
print i
do
k += 1
if gcd( k, Y(i-2) ) = 1 orelse gcd( k, Y(i-1) ) > 1 then continue do
for j = 1 to i-1
if Y(j)=k then continue do
next j
Y(i) = k
exit do
loop
next i
for i = 1 to 30
print str(Y(i))+" ";
next i
print
screen 13
for i = 1 to 100
pset (i, 200-Y(i)), 31
next i
while inkey=""
wend
end
- 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
Go
This uses Gnuplot-X11 to do the plotting rather than a third party Go plotting library.
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()
}
- 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
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
- 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]
Or, defining the Yellowstone permutation in terms of iterate, rather than unfoldr,
and displaying a chart of the first 100 terms:
import Codec.Picture
import Data.Bifunctor (second)
import Diagrams.Backend.Rasterific
import Diagrams.Prelude
import Graphics.Rendering.Chart.Backend.Diagrams
import Graphics.Rendering.Chart.Easy
import qualified Graphics.SVGFonts.ReadFont as F
----------------- YELLOWSTONE PERMUTATION ----------------
yellowstone :: [Integer]
yellowstone =
1 :
2 :
(active <$> iterate nextWindow (2, 3, [4 ..]))
where
nextWindow (p2, p1, rest) = (p1, n, residue)
where
[rp2, rp1] = relativelyPrime <$> [p2, p1]
go (x : xs)
| rp1 x && not (rp2 x) = (x, xs)
| otherwise = second ((:) x) (go xs)
(n, residue) = go rest
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 =
renderDia
Rasterific
( RasterificOptions
(mkWidth (fst (envOutputSize env)))
)
$ 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
- 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]
J
tacit
Until=: 2 :'u^:(0-:v)^:_'
assert 44 -: >:Until(>&43) 32 NB. increment until exceeding 43
gcd=: +.
coprime=: 1 = gcd
prepare=:1 2 3"_ NB. start with the vector 1 2 3
condition=: 0 1 -: (coprime _2&{.) NB. trial coprime most recent 2, nay and yay
append=: , NB. concatenate
novel=: -.@e. NB. x is not a member of y
term=: >:@:]Until((condition *. novel)~) 4:
ys=: (append term)@]^:(0 >. _3+[) prepare
assert (ys 30) -: 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
explicit
GCD=: +.
relatively_prime=: 1 = GCD
yellowstone=: {{
s=. 1 2 3 NB. initial sequence
while. y > # s do.
z=. <./(1+s)-.s NB. lowest positive inteeger not in sequence
while. if. 0 1 -: z relatively_prime _2{.s do. z e. s end. do.
z=. z+1
end. NB. find next value for sequence
s=. s, z
end.
}}
yellowstone 30 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 load'plot' 'marker'plot yellowstone 100
Java
import java.util.ArrayList;
import java.util.List;
public class YellowstoneSequence {
public static void main(String[] args) {
System.out.printf("First 30 values in the yellowstone sequence:%n%s%n", yellowstoneSequence(30));
}
private static List<Integer> yellowstoneSequence(int sequenceCount) {
List<Integer> yellowstoneList = new ArrayList<Integer>();
yellowstoneList.add(1);
yellowstoneList.add(2);
yellowstoneList.add(3);
int num = 4;
List<Integer> notYellowstoneList = new ArrayList<Integer>();
int yellowSize = 3;
while ( yellowSize < sequenceCount ) {
int found = -1;
for ( int index = 0 ; index < notYellowstoneList.size() ; index++ ) {
int test = notYellowstoneList.get(index);
if ( gcd(yellowstoneList.get(yellowSize-2), test) > 1 && gcd(yellowstoneList.get(yellowSize-1), test) == 1 ) {
found = index;
break;
}
}
if ( found >= 0 ) {
yellowstoneList.add(notYellowstoneList.remove(found));
yellowSize++;
}
else {
while ( true ) {
if ( gcd(yellowstoneList.get(yellowSize-2), num) > 1 && gcd(yellowstoneList.get(yellowSize-1), num) == 1 ) {
yellowstoneList.add(num);
yellowSize++;
num++;
break;
}
notYellowstoneList.add(num);
num++;
}
}
}
return yellowstoneList;
}
private static final int gcd(int a, int b) {
if ( b == 0 ) {
return a;
}
return gcd(b, a%b);
}
}
- Output:
First 30 values 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]
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();
})();
- 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
jq
# jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
def _gcd:
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;
[a,b] | _gcd ;
# emit the yellowstone sequence as a stream
def yellowstone:
1,2,3,
({ a: [2, 3], # the last two items only
b: {"1": true, "2": true, "3" : true}, # a record, to avoid having to save the entire history
start: 4 }
| foreach range(1; infinite) as $n (.;
first(
.b as $b
| .start = first( range(.start;infinite) | select($b[tostring]|not) )
| foreach range(.start; infinite) as $i (.;
.emit = null
| ($i|tostring) as $is
| if .b[$is] then .
# "a(n) is relatively prime to a(n-1) and is not relatively prime to a(n-2)"
elif (gcd($i; .a[1]) == 1) and (gcd($i; .a[0]) > 1)
then .emit = $i
| .a = [.a[1], $i]
| .b[$is] = true
else .
end;
select(.emit)) );
.emit ));
The task
"The first 30 entries of the Yellowstone permutation:",
[limit(30;yellowstone)]
- 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]
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)
- 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]
Kotlin
fun main() {
println("First 30 values in the yellowstone sequence:")
println(yellowstoneSequence(30))
}
private fun yellowstoneSequence(sequenceCount: Int): List<Int> {
val yellowstoneList = mutableListOf(1, 2, 3)
var num = 4
val notYellowstoneList = mutableListOf<Int>()
var yellowSize = 3
while (yellowSize < sequenceCount) {
var found = -1
for (index in notYellowstoneList.indices) {
val test = notYellowstoneList[index]
if (gcd(yellowstoneList[yellowSize - 2], test) > 1 && gcd(
yellowstoneList[yellowSize - 1], test
) == 1
) {
found = index
break
}
}
if (found >= 0) {
yellowstoneList.add(notYellowstoneList.removeAt(found))
yellowSize++
} else {
while (true) {
if (gcd(yellowstoneList[yellowSize - 2], num) > 1 && gcd(
yellowstoneList[yellowSize - 1], num
) == 1
) {
yellowstoneList.add(num)
yellowSize++
num++
break
}
notYellowstoneList.add(num)
num++
}
}
}
return yellowstoneList
}
private fun gcd(a: Int, b: Int): Int {
return if (b == 0) {
a
} else gcd(b, a % b)
}
- Output:
First 30 values 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]
Lua
function gcd(a, b)
if b == 0 then
return a
end
return gcd(b, a % b)
end
function printArray(a)
io.write('[')
for i,v in pairs(a) do
if i > 1 then
io.write(', ')
end
io.write(v)
end
io.write(']')
return nil
end
function removeAt(a, i)
local na = {}
for j,v in pairs(a) do
if j ~= i then
table.insert(na, v)
end
end
return na
end
function yellowstone(sequenceCount)
local yellow = {1, 2, 3}
local num = 4
local notYellow = {}
local yellowSize = 3
while yellowSize < sequenceCount do
local found = -1
for i,test in pairs(notYellow) do
if gcd(yellow[yellowSize - 1], test) > 1 and gcd(yellow[yellowSize - 0], test) == 1 then
found = i
break
end
end
if found >= 0 then
table.insert(yellow, notYellow[found])
notYellow = removeAt(notYellow, found)
yellowSize = yellowSize + 1
else
while true do
if gcd(yellow[yellowSize - 1], num) > 1 and gcd(yellow[yellowSize - 0], num) == 1 then
table.insert(yellow, num)
yellowSize = yellowSize + 1
num = num + 1
break
end
table.insert(notYellow, num)
num = num + 1
end
end
end
return yellow
end
function main()
print("First 30 values in the yellowstone sequence:")
printArray(yellowstone(30))
print()
end
main()
- Output:
First 30 values 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]
Mathematica / Wolfram Language
state = {1, 2, 3};
MakeNext[state_List] := Module[{i = First[state], done = False, out},
While[! done,
If[FreeQ[state, i],
If[GCD[Last[state], i] == 1,
If[GCD[state[[-2]], i] > 1,
out = Append[state, i];
done = True;
]
]
];
i++;
];
out
]
Nest[MakeNext, state, 30 - 3]
ListPlot[%]
- 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} (* Graphical visualisation of the data *)
Nim
Procedure version
This version uses a set and, so, is limited to 65536 elements. It is easy to change this limit by using a HashSet (standard module “sets”) instead of a set. See the iterator version which uses such a HashSet.
import math
proc yellowstone(n: int): seq[int] =
assert n >= 3
result = @[1, 2, 3]
var present = {1, 2, 3}
var start = 4
while result.len < n:
var candidate = start
while true:
if candidate notin present and gcd(candidate, result[^1]) == 1 and gcd(candidate, result[^2]) != 1:
result.add candidate
present.incl candidate
while start in present: inc start
break
inc candidate
echo yellowstone(30)
- 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]
Iterator version
This version uses a HashSet, but using a set as in the previous version is possible if we accept the limit of 65536 elements.
import math, sets
iterator yellowstone(n: int): int =
assert n >= 3
for i in 1..3: yield i
var present = [1, 2, 3].toHashSet
var prevLast = 2
var last = 3
var start = 4
for _ in 4..n:
var candidate = start
while true:
if candidate notin present and gcd(candidate, last) == 1 and gcd(candidate, prevLast) != 1:
yield candidate
present.incl candidate
prevLast = last
last = candidate
while start in present: inc start
break
inc candidate
for n in yellowstone(30):
stdout.write " ", n
echo()
- 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
PARI/GP
yellowstone(n) = {
my(a=3, o=2, u=[]);
if(n<3, return(n)); \\ Base case: return n if it is less than 3
print1("1, 2"); \\ Print initial values
for(i = 4, n, \\ Iterate from 4 to n
print1(", "a); \\ Print current value of a
u = setunion(u, Set(a)); \\ Add a to the set u
\\ Remove consecutive elements from u
while(#u > 1 && u[2] == u[1] + 1,
u = vecextract(u, "^1")
);
\\ Find next value of a
for(k = u[1] + 1, 1e10,
if(gcd(k, o) <= 1, next); \\ Skip if gcd(k, o) is greater than 1
if(setsearch(u, k), next); \\ Skip if k is in set u
if(gcd(k, a) != 1, next); \\ Skip if gcd(k, a) is not 1
o = a; \\ Update o to current a
a = k; \\ Update a to k
break
)
);
a \\ Return the final value of a
}
yellowstone(20); \\ Call the function with n = 20
- Output:
1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7, 10, 21, 20, 27
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;
- 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
Phix
You can run this online here.
-- -- demo\rosetta\Yellowstone_sequence.exw -- with javascript_semantics requires("1.0.2") 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)}) -- a simple plot: include pGUI.e include IupGraph.e function get_data(Ihandle graph) sequence y500 = yellowstone(500) integer {w,h} = IupGetIntInt(graph,"DRAWSIZE") IupSetInt(graph,"XTICK",iff(w<640?iff(h<300?100:50):20)) IupSetInt(graph,"YTICK",iff(h<250?iff(h<140?iff(h<120?700:350):200):100)) return {{tagset(500),y500,CD_RED}} end function IupOpen() Ihandle graph = IupGraph(get_data,"RASTERSIZE=960x600") IupSetAttributes(graph,`GTITLE="Yellowstone Numbers"`) IupSetInt(graph,"TITLESTYLE",CD_ITALIC) IupSetAttributes(graph,`XNAME="n", YNAME="a(n)"`) IupSetAttributes(graph,"XTICK=20,XMIN=0,XMAX=500") IupSetAttributes(graph,"YTICK=100,YMIN=0,YMAX=1400") Ihandle dlg = IupDialog(graph,`TITLE="Yellowstone Names"`) IupSetAttributes(dlg,"MINSIZE=290x140") IupShow(dlg) if platform()!=JS then IupMainLoop() IupClose() end if
- 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}
Phixmonti
Require Utilitys library version 1.3
include ..\Utilitys.pmt
def gcd /# u v -- n #/
abs int swap abs int swap
dup
while
over over mod rot drop dup
endwhile
drop
enddef
def test enddef
def yellow var n
( 1 2 3 ) var a
newd ( 1 true ) setd ( 2 true ) setd ( 3 true ) setd var b
4 var i
test
while
b i getd "Unfound" == >ps
a -1 get >ps -2 get
i gcd 1 > ps> i gcd 1 == ps>
and and if
i 0 put var a
( i true ) setd var b
4 var i
else
drop drop
endif
i 1 + var i
test
endwhile
a
enddef
def test n a len nip > enddef
"The first 30 entries of the Yellowstone permutation:" ? 30 yellow ?
- 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] === Press any key to exit ===
PicoLisp
(load "@lib/frac.l")
(de yellow (N)
(let (L (list 3 2 1) I 4 C 3 D)
(while (> N C)
(when
(and
(not (idx 'D I))
(=1 (gcd I (get L 1)))
(> (gcd I (get L 2)) 1) )
(push 'L I)
(idx 'D I T)
(setq I 4)
(inc 'C) )
(inc 'I) )
(flip L) ) )
(println (yellow 30))
- 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)
PureBasic
Procedure.i gcd(x.i,y.i)
While y<>0 : t=x : x=y : y=t%y : Wend : ProcedureReturn x
EndProcedure
If OpenConsole()
Dim Y.i(100)
For i=1 To 100
If i<=3 : Y(i)=i : Continue : EndIf : k=3
Repeat
RepLoop:
k+1
For j=1 To i-1 : If Y(j)=k : Goto RepLoop : EndIf : Next
If gcd(k,Y(i-2))=1 Or gcd(k,Y(i-1))>1 : Continue : EndIf
Y(i)=k : Break
ForEver
Next
For i=1 To 30 : Print(Str(Y(i))+" ") : Next : Input()
EndIf
- 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
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 go
# 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()
- 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]
Quackery
gcd
is defined at Greatest common divisor#Quackery.
[ stack ] is seqbits ( --> s )
[ bit
seqbits take |
seqbits put ] is seqadd ( n --> )
[ bit
seqbits share & not ] is notinseq ( n --> b )
[ temp put
' [ 1 2 3 ]
7 seqbits put
4
[ dip
[ dup -1 peek
over -2 peek ]
dup dip
[ tuck gcd 1 !=
unrot gcd 1 =
and ]
swap if
[ dup dip join
seqadd
3 ]
[ 1+
dup notinseq until ]
over size temp share
< not until ]
drop
seqbits release
temp take split drop ] is yellowstones ( n --> [ )
30 yellowstones echo
- 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 ]
Racket
#lang racket
(require plot)
(define a098550
(let ((hsh# (make-hash '((1 . 1) (2 . 2) (3 . 3))))
(rev# (make-hash '((1 . 1) (2 . 2) (3 . 3)))))
(λ (n)
(hash-ref hsh# n
(λ ()
(let ((a_n (for/first ((i (in-naturals 4))
#:unless (hash-has-key? rev# i)
#:when (and (= (gcd i (a098550 (- n 1))) 1)
(> (gcd i (a098550 (- n 2))) 1)))
i)))
(hash-set! hsh# n a_n)
(hash-set! rev# a_n n)
a_n))))))
(map a098550 (range 1 (add1 30)))
(plot (points
(map (λ (i) (vector i (a098550 i))) (range 1 (add1 100)))))
- Output:
Just the output text... you'll have to run this yourself in racket to see the plot!
'(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)
Raku
(formerly 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.
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;
- 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
REXX
horizontal list of numbers
/*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, @.prev)<2 then iterate /*Not meet requirement? Then skip it. */
if gcd(k, @.#) \==1 then iterate /* " " " " " " */
#= #+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
- output when using the default input: 30
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
vertical histogram plot
A horizontal histogram could also be shown, but it would require a taller (higher) plot with more vertical screen real estate.
/*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, @.prev)<2 then iterate /*Not meet requirement? Then skip it. */
if gcd(k, @.#) \==1 then iterate /* " " " " " " */
#= # + 1; @.#= k; !.k= 1; $= $ k /*bump ctr; assign; mark used; add list*/
leave /*find the next Yellowstone seq. number*/
end /*k*/
end /*j*/
call $histo $ '(vertical)' /*invoke a REXX vertical histogram plot*/
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
- output when using the input: 532
The plot is shown at three─quarter scale.
■ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ ■ │ │ │ │ ■ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ ■ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ ■ ■ │ │ ■ ■ ■ │ ■ │ │ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ ■ │ │ │ │ ■ │ ■ ■ │ │ ■ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ ■ │ │ ■ ■ │ │ │ ■ ■ │ ■ ■ │ │ │ │ │ │ ■ │ │ ■ │ ■ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ ■ ■ │ ■ ■ │ ■ ■ │ ■ │ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ ■ │ ■ │ │ ■ │ ■ │ │ ■ │ ■ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ ■ │ ■ │ │ ■ │ ■ │ │ │ │ │ │ │ │ │ ■ ■ ■ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ ■ │ │ ■ │ ■ ■ │ │ │ │ ■ ■ │ ■ │ ■ │ │ │ │ │ │ │ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ ■ │ ■ ■ │ │ ■ │ ■ ■ │ │ │ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■│ │ │ │ │■│■│ ││■│■│ │■│ │■│■│ ■│■│ ■│■│ │ │ │ │ │ ■ │ │ │ ■ ■ │ ■ │ ■ │ │ │ ■ │ │ │ │ ■ ■ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■│ │ │ │■│ │ │ │ │ │ │■│■│ ■│■│■│■│■│ ││■│■│ ■│■│││││ ││││││■│││■│││││ ││││ ││││ ■ │ │ │ │ │ │ │ ■ ■ │ ■ │ │ ■ ■ │ │ │ │ │ │ ■ │ │ ■ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│■│■│ ││■│■│■│││ │■│■│■│■│■│││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ │ │ │ │ │ │ ■ ■ │ ■ ■ │ ■ │ ■ │ ■ │ │ │ ■ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│ ■│ │■│■│ ■│■│■│ ■│■│ ■│■│││││││││││││ ││││││││││■│││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ │ ■ │ │ │ │ │ ■ ■ │ │ │ ■ │ ■ │ ■ │ ■ │ │ │ ■ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│ ■│■│■│ ■│■│■│■│■│■│││││││││ ││■│││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ ■ │ ■ │ │ │ │ ■ ■ │ ■ ■ │ ■ ■ │ │ ■ ■ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│ │■│■│ ■│■│■│■│ ■│■│■│■│■│ ■│││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ │ │ │ │ │ ■ │ ■ ■ │ ■ ■ ■ ■ │ │ ■ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│■│■│■│ ■│■│ ■│■│■│■│ ■│■│■│││││■│││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ │ ■ │ │ │ │ ■ ■ ■ ■ │ │ ■ │ │ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ ■│ │ │■│ │ │■│■│■│■│ ■│■│ ■│■│■│■│■│■│││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││ ││││││││││││││││ ││││ ││││ │ │ │ │ ■ │ ■ ■ ■ │ ■ ■ ■ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │■│ │■│■│■│■│■│■│■│■│■│■│ ││■│■│││ ■│■│││││││││ ││││ ││││││││││││││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││ ││││││││││││││││││││││││││ ││││││││││ ││││││ ││││││││■││││││││││││││││■││││■││││ │ ■ │ │ │ ■ ■ │ ■ ■ ■ │ ■ ■ ■ │ │ │ │ ■ │ │ ■ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│ │■│■│■│■│ ■│■│ ■│■│■│■│ ■│││■│││││││││││││││││││││ ││││││││ ││││││││││││ ││││ ││││││││││││││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││ ││││││ ││││││││││││││││││││ ││││││││ ││││││ ││││ ││││││││││││││││■││││││││││││││││││││││││││■││││││││││■││││││■│││││││││││││││││││││││││││││││││││ ■ │ │ │ ■ ■ ■ ■ │ ■ ■ ■ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │■│■│ ■│■│■│■│■ ■│■│■│■│■│ ■│││││ ■│││││││││ ││││ ││││││││ ││││││││││││││││││││││││││ ││││││││ ││││││││││││ ││││ ││││││││││││││││││││││ ││││ ││││││││ ││││││││││││││││ ││││││││ ││││││││││ ││││││││││■││││││■││││││││││││││││││││■││││││││■││││││■││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ ■ │ ■ ■ │ │ ■ ■ ■ │ │ │ │ │ ■ │ │ │ │ │ │ │ │ │ │■│ │■│■│■│ ■│■│■│■ ■│■│■│■│■│■■■│││││ │││││││││ ││││││││││ ││││││ ││││││││││ ││││ ││││││││ ││││││││││││││││││││││││││ ││││││││ ││││││││││││ ││││ ││││││││││││││││││││││■││││■││││││││■││││││││││││││││■││││││││■││││││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ ■ ■ │ │ ■ ■ ■ ■ ■ ■ │ │ │ │ │ ■ │ │ │ │ │ ■ ■■│ │■│ ■│■│■│■│■ ■│■│■│■│■│ ■│││ ■│││││││ │││││││ ││││││││││││││││││ │││││││││ ││││││││││ ││││││ ││││││││││ ││││ ││││││││ ││││││││││││││││││││││││││■││││││││■││││││││││││■││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ ■ ■ ■ ■ ■ │ │ │ │ ■ ■ │ │ │■│■│ │ │■│ ■│■│■│■│■│■│ ■│■│■│■│■│││ ■│││ │││││││││ ││││││││││ ││││ ││││││││ │││││││ ││││││││││││││││││■│││││││││■││││││││││■││││││■││││││││││■││││■││││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ ■ ■ │ ■ │ ■ │ ■ ■ ■■ │■│■■ │■│■│■│■│ ■│■│■│■ ■│││││■│■│││ ││││││││││││ ││││││││││││■││││■│││││││││■││││││││││■││││■││││││││■│││││││■│││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││││ ────────────┴───────┴──┴─┴─┴┴──┴─┴┴┴┴┴┴┴┴┴─┴┴┴┴┴┴┴─┴┴┴┴┴┴┴┴┴─┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴ 1234981156213171222231132425311825363934361494546524157485862359696751616171713717181844818191718191493921111911151211111111115111161411111216131212121271212713121212712121218151212121211121212812121212191612131322115222212322222223123231252323231252323232323232423242323221232323231262323242323124231292424232323242324242413134137343434137343434343434341313434341383434353513534343435138353513134353535353435363413135353513535351393514545454545454545246454646454546464546464646241464646452414646246464645256464646464647462414624746 54 5256 0107291336581278545456109839254709038125616729183498741036627407016102613228322844546702600404850730608191412189172512228283037233031334214140346415350953646473585164657266747775986868799978788909107090090800009151912022100142024221263333353641344047454455582785668673555569606877381793777186898286939992919340004505040611518171222201527296312834356333748414274155575850749536586269617371667972828899375898699780919989790903031414171823143292030350806102824373241231424354552615857248636262309757253716871763868948285 5 9 3 1 5 5 1 7 3 9 5 5 5 5 5 9 30741 361 258525634187 0729 074389016 6525458525 0367 45892189 4703490 016725652189476389 274189016 0967214525185456530987230945701839652545673852903618349410327658307497216907251258545658541701839036329496381072145658590421165458547725610309278143653048327437658545256530909276981985452510667810927416387092110343456732987437658590741670329638523123418309612985456309214765381458525497836585907094169369012307412965839072314387 3 1 7 7 5 5 3
Ring
see "working..." + nl
row = 3
num = 2
numbers = 1:51
first = 2
second = 3
see "Yellowstone numbers are:" + nl
see "1 " + first + " " + second + " "
for n = 4 to len(numbers)
flag1 = 1
flag2 = 1
if first < numbers[n]
min = first
else
min = numbers[n]
ok
for m = 2 to min
if first%m = 0 and numbers[n]%m = 0
flag1 = 0
exit
ok
next
if second < numbers[n]
min = second
else
min = numbers[n]
ok
for m = 2 to min
if second%m = 0 and numbers[n]%m = 0
flag2 = 0
exit
ok
next
if flag1 = 0 and flag2 = 1
see "" + numbers[n] + " "
first = second
second = numbers[n]
del(numbers,n)
row = row+1
if row%10 = 0
see nl
ok
num = num + 1
if num = 29
exit
ok
n = 3
ok
next
see "Found " + row + " Yellowstone numbers" + nl
see "done..." + nl
- Output:
working... 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 Found 30 Yellowstone numbers done...
RPL
Code | Comments |
---|---|
≪ IF DUP2 < THEN SWAP END WHILE DUP REPEAT SWAP OVER MOD END DROP ≫ 'GCD' STO ≪ DUP SIZE 1 - GETI ROT ROT GET → am2 am1 ≪ 3 DO DO 1 + UNTIL DUP2 POS NOT END UNTIL DUP am1 GCD 1 == OVER am2 GCD 1 ≠ AND END + ≫ ≫ 'YELLO' STO |
( a b -- gcd(a,b) ) Ensure a > b Euclidean algorithm ( { a(1)..a(n-1) } -- { a(1)..a(n) } ) Store locally a(n-1) and a(n-2) Find smallest number not already in sequence Check primality requirements Add a(n) to the sequence |
The following words in the command line deliver what is required:
{ 1 2 3 } ≪ 1 27 START YELLO NEXT ≫ EVAL
- Output:
1: { 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 ]
Ruby
def yellow(n)
a = [1, 2, 3]
b = { 1 => true, 2 => true, 3 => true }
i = 4
while n > a.length
if !b[i] && i.gcd(a[-1]) == 1 && i.gcd(a[-2]) > 1
a << i
b[i] = true
i = 4
end
i += 1
end
a
end
p yellow(30)
- 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]
Rust
// [dependencies]
// num = "0.3"
// plotters = "^0.2.15"
use num::integer::gcd;
use plotters::prelude::*;
use std::collections::HashSet;
fn yellowstone_sequence() -> impl std::iter::Iterator<Item = u32> {
let mut sequence: HashSet<u32> = HashSet::new();
let mut min = 1;
let mut n = 0;
let mut n1 = 0;
let mut n2 = 0;
std::iter::from_fn(move || {
n2 = n1;
n1 = n;
if n < 3 {
n += 1;
} else {
n = min;
while !(!sequence.contains(&n) && gcd(n1, n) == 1 && gcd(n2, n) > 1) {
n += 1;
}
}
sequence.insert(n);
while sequence.contains(&min) {
sequence.remove(&min);
min += 1;
}
Some(n)
})
}
// Based on the example in the "Quick Start" section of the README file for
// the plotters library.
fn plot_yellowstone(filename: &str) -> Result<(), Box<dyn std::error::Error>> {
let root = BitMapBackend::new(filename, (800, 600)).into_drawing_area();
root.fill(&WHITE)?;
let mut chart = ChartBuilder::on(&root)
.caption("Yellowstone Sequence", ("sans-serif", 24).into_font())
.margin(10)
.x_label_area_size(20)
.y_label_area_size(20)
.build_ranged(0usize..100usize, 0u32..180u32)?;
chart.configure_mesh().draw()?;
chart.draw_series(LineSeries::new(
yellowstone_sequence().take(100).enumerate(),
&BLUE,
))?;
Ok(())
}
fn main() {
println!("First 30 Yellowstone numbers:");
for y in yellowstone_sequence().take(30) {
print!("{} ", y);
}
println!();
match plot_yellowstone("yellowstone.png") {
Ok(()) => {}
Err(error) => eprintln!("Error: {}", error),
}
}
- Output:
A plot of the first 100 Yellowstone numbers is saved to the file "yellowstone.png".
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
Media:Yellowstone sequence rust.png
Scala
import scala.util.control.Breaks._
object YellowstoneSequence extends App {
println(s"First 30 values in the yellowstone sequence:\n${yellowstoneSequence(30)}")
def yellowstoneSequence(sequenceCount: Int): List[Int] = {
var yellowstoneList = List(1, 2, 3)
var num = 4
var notYellowstoneList = List[Int]()
while (yellowstoneList.size < sequenceCount) {
val foundIndex = notYellowstoneList.indexWhere(test =>
gcd(yellowstoneList(yellowstoneList.size - 2), test) > 1 &&
gcd(yellowstoneList.last, test) == 1
)
if (foundIndex >= 0) {
yellowstoneList = yellowstoneList :+ notYellowstoneList(foundIndex)
notYellowstoneList = notYellowstoneList.patch(foundIndex, Nil, 1)
} else {
breakable({
while (true) {
if (gcd(yellowstoneList(yellowstoneList.size - 2), num) > 1 &&
gcd(yellowstoneList.last, num) == 1) {
yellowstoneList = yellowstoneList :+ num
num += 1
// break the inner while loop
break
}
notYellowstoneList = notYellowstoneList :+ num
num += 1
}
});
}
}
yellowstoneList
}
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}
- Output:
First 30 values in the yellowstone sequence: List(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)
Tcl
proc gcd {a b} {
while {$b} {
lassign [list $b [expr {$a % $b}]] a b
}
return $a
}
proc gen_yellowstones {{maxN 30}} {
set r {}
for {set n 1} {$n <= $maxN} {incr n} {
if {$n <= 3} {
lappend r $n
} else {
## NB: list indices start at 0, not 1.
set pred [lindex $r end ] ;# a(n-1): coprime
set prepred [lindex $r end-1] ;# a(n-2): not coprime
for {set k 4} {1} {incr k} {
if {[lsearch -exact $r $k] >= 0} { continue }
if {1 != [gcd $k $pred ]} { continue }
if {1 == [gcd $k $prepred]} { continue }
## candidate k survived all tests...
break
}
lappend r $k
}
}
return $r
}
puts "The first 30 Yellowstone numbers are:"
puts [gen_yellowstones]
- 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
uBasic/4tH
Dim @y(30)
@y(0) = 1
@y(1) = 2
@y(2) = 3
For i = 3 To 29
k = 3
Do
k = k + 1
If (FUNC(_gcd(k, @y(i-2))) = 1) + (FUNC(_gcd(k, @y(i-1))) > 1) Then
Continue
EndIf
For j = 0 To i - 1
If @y(j) = k Then Unloop : Continue
Next
@y(i) = k : Break
Loop
Next
For i = 0 To 29
Print @y(i); " ";
Next
Print : End
_gcd Param (2)
If b@ = 0 Then Return (a@)
Return (FUNC(_gcd(b@, a@ % b@)))
- 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 0 OK, 0:670
VBA
Function gcd(a As Long, b As Long) As Long
If b = 0 Then
gcd = a
Exit Function
End If
gcd = gcd(b, a Mod b)
End Function
Sub Yellowstone()
Dim i As Long, j As Long, k As Long, Y(1 To 30) As Long
Y(1) = 1
Y(2) = 2
Y(3) = 3
For i = 4 To 30
k = 3
Do
k = k + 1
If gcd(k, Y(i - 2)) = 1 Or gcd(k, Y(i - 1)) > 1 Then GoTo EndLoop:
For j = 1 To i - 1
If Y(j) = k Then GoTo EndLoop:
Next j
Y(i) = k
Exit Do
EndLoop:
Loop
Next i
For i = 1 To 30
Debug.Print Y(i) & " ";
Next i
End Sub
- 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
V (Vlang)
fn gcd(xx int, yy int) int {
mut x := xx
mut y := yy
for y != 0 {
x, y = y, x%y
}
return x
}
fn yellowstone(n int) []int {
mut m := map[int]bool{}
mut a := []int{len: n+1}
for i in 1..4 {
a[i] = i
m[i] = true
}
mut 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..]
}
fn main() {
mut x := []int{len: 100}
for i in 0..100 {
x[i] = i + 1
}
y := yellowstone(100)
println("The first 30 Yellowstone numbers are:")
println(y[..30])
}
- 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]
Wren
Without the extra credit part.
import "./math" for Int
var yellowstone = Fn.new { |n|
var m = {}
var a = List.filled(n + 1, 0)
for (i in 1..3) {
a[i] = i
m[i] = true
}
var min = 4
for (c in 4..n) {
var i = min
while (true) {
if (!m[i] && Int.gcd(a[c-1], i) == 1 && Int.gcd(a[c-2], i) > 1) {
a[c] = i
m[i] = true
if (i == min) min = min + 1
break
}
i = i + 1
}
}
return a[1..-1]
}
var x = List.filled(30, 0)
for (i in 0...30) x[i] = i + 1
var y = yellowstone.call(30)
System.print("The first 30 Yellowstone numbers are:")
System.print(y)
- 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]
XPL0
func GCD(N, D); \Return the greatest common divisor of N and D
int N, D, R; \numerator, denominator, remainder
[if D > N then
[R:=D; D:=N; N:=R]; \swap D and N
while D > 0 do
[R:= rem(N/D);
N:= D;
D:= R;
];
return N;
];
int I, A(30+1), N, T;
[for I:= 1 to 3 do A(I):= I; \givens
N:= 4;
repeat T:= 4;
loop [if GCD(T, A(N-1)) = 1 and \relatively prime
GCD(T, A(N-2)) # 1 then \not relatively prime
[loop [for I:= 1 to N-1 do \test if in sequence
if T = A(I) then quit;
quit;
];
if I = N then \T is not in sequence so
[A(N):= T; \ add it in
N:= N+1;
quit;
];
];
T:= T+1; \next trial
];
until N > 30;
for N:= 1 to 30 do
[IntOut(0, A(N)); ChOut(0, ^ )];
\\for N:= 1 to 100 do Point(N, A(N)); \plot demonstration
]
- 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
zkl
This sequence is limited to the max size of a Dictionary, 64k
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);
}
println("The first 30 entries of the Yellowstone permutation:");
yellowstoneW().walk(30).concat(", ").println();
- 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
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();
Offsite Image: yellowstone
- Programming Tasks
- Solutions by Programming Task
- Prime Numbers
- 11l
- Action!
- Ada
- ALGOL 68
- Arturo
- AutoHotkey
- C
- C++
- D
- Delphi
- System.SysUtils
- Boost.Generics.Collection
- Boost.Process
- EasyLang
- Factor
- Forth
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- Mathematica
- Wolfram Language
- Nim
- PARI/GP
- Perl
- Phix
- Phix/pGUI
- Phix/online
- Phixmonti
- PicoLisp
- PureBasic
- Python
- Quackery
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Tcl
- UBasic/4tH
- VBA
- V (Vlang)
- Wren
- Wren-math
- XPL0
- Zkl