Stern-Brocot sequence: Difference between revisions
Content added Content deleted
ReeceGoding (talk | contribs) m (→{{header|R}}: Syntax highlighting.) |
ReeceGoding (talk | contribs) m (→While loop: Improved syntax.) |
||
| Line 4,907: | Line 4,907: | ||
As with the previous solution, we have used a library for our gcd function. In this case, we have used gmp. |
As with the previous solution, we have used a library for our gcd function. In this case, we have used gmp. |
||
<lang rsplus>genNStern<-function(n) |
<lang rsplus>genNStern <- function(n) |
||
{ |
{ |
||
sternNums<-c( |
sternNums <- c(1, 1) |
||
i<-2 |
i <- 2 |
||
while((endIndex<-length(sternNums))<n) |
while((endIndex <- length(sternNums)) < n) |
||
{ |
{ |
||
#To show off R's vectorization, the following line is deliberately terse. |
#To show off R's vectorization, the following line is deliberately terse. |
||
| Line 4,918: | Line 4,918: | ||
#Note that we do not have to initialize a big sternNums array to do this. |
#Note that we do not have to initialize a big sternNums array to do this. |
||
#True to the algorithm, the new entries are appended to the end of the old sequence. |
#True to the algorithm, the new entries are appended to the end of the old sequence. |
||
sternNums[endIndex+c(1,2)]<-c(sum(sternNums[c(i-1,i)]),sternNums[i]) |
sternNums[endIndex + c(1, 2)] <- c(sum(sternNums[c(i - 1, i)]), sternNums[i]) |
||
i<-i+1 |
i <- i + 1 |
||
} |
} |
||
sternNums[ |
sternNums[seq_len(n)] |
||
} |
} |
||
#N=5000 was picked arbitrarily. The code runs very fast regardless of this number being much more than we need. |
#N=5000 was picked arbitrarily. The code runs very fast regardless of this number being much more than we need. |
||
firstFiveThousandTerms<-genNStern(5000) |
firstFiveThousandTerms <- genNStern(5000) |
||
match(1:10, firstFiveThousandTerms) |
match(1:10, firstFiveThousandTerms) |
||
match(100, firstFiveThousandTerms) |
match(100, firstFiveThousandTerms) |
||
all(sapply(1:999, function(i) gmp::gcd(firstFiveThousandTerms[i],firstFiveThousandTerms[i+1]))==1)</lang> |
all(sapply(1:999, function(i) gmp::gcd(firstFiveThousandTerms[i], firstFiveThousandTerms[i + 1])) == 1)</lang> |
||
{{Output}} |
{{Output}} |
||
<pre>> firstFiveThousandTerms<-genNStern(5000) |
<pre>> firstFiveThousandTerms <- genNStern(5000) |
||
> match(1:10, firstFiveThousandTerms) |
> match(1:10, firstFiveThousandTerms) |
||
[1] 1 3 5 9 11 33 19 21 35 39 |
[1] 1 3 5 9 11 33 19 21 35 39 |
||
> match(100, firstFiveThousandTerms) |
> match(100, firstFiveThousandTerms) |
||
[1] 1179 |
[1] 1179 |
||
> all(sapply(1:999, function(i) gmp::gcd(firstFiveThousandTerms[i],firstFiveThousandTerms[i+1]))==1) |
> all(sapply(1:999, function(i) gmp::gcd(firstFiveThousandTerms[i], firstFiveThousandTerms[i + 1])) == 1) |
||
[1] TRUE</pre> |
[1] TRUE</pre> |
||