Rosetta Code

Klarner-Rado sequence: Difference between revisions

Page Discussion

Klarner-Rado sequence (view source)

Revision as of 08:21, 7 April 2024

21,437 bytes added ,  1 month ago
m
Minor update to Forth code
No edit summary
m (Minor update to Forth code)
 
(18 intermediate revisions by 10 users not shown)
Line 1:
{{draft task}}
 
Klarner-Rado sequences are a class of similar sequences that were studied by the mathematicians David Klarner and Richard Rado.
Line 138:
 
=={{header|AppleScript}}==
One way to test numbers for membership of the sequence is to feed them to a recursive handler which determines whether or not there's a Klarner-Rado route from them down to 01. It makes finding the elements in order simple, but takes aboutnearly five and a halfsix minutes to get toa themillion millionthof onethem.
 
<syntaxhighlight lang="applescript">-- Is n in the Klarner-Rado sequence?
-- Fully recursive:
(*
(* on isKlarnerRado(n)
on isKlarnerRado(n)
set n to n - 1
return ((n = 01) or ((n mod 23 = 01) and (isKlarnerRado(n div 23))) or ((n mod 3 = 0) and (isKlarnerRado(n div 3))))¬
end ((n mod 2 = 1) and (isKlarnerRado(n div *2))))
end isKlarnerRado
*)
 
-- Optimised withWith tail call elimination. 90About a secondsminute faster than the above in this script.
-- Interestingly, leaving out the 'else's and comparing n mod 2 directly with 0 slows it down!
on isKlarnerRado(n)
set n to n - 1
repeat
if ((n = 01) or ((n mod 3 = 01) and (isKlarnerRado(n div 3)))) then
return true
else if (n mod 2 =< 01) then
set n to n div 2 - 1
else
return false
else
set n to n div 2
end if
end repeat
Line 520 ⟶ 522:
54381285
1031926801</pre>
 
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
 
class KlarnerRadoSequence {
 
static void Main(string[] args) {
const int limit = 1_000_000;
int[] klarnerRado = InitialiseKlarnerRadoSequence(limit);
 
Console.WriteLine("The first 100 elements of the Klarner-Rado sequence:");
for (int i = 1; i <= 100; i++) {
Console.Write($"{klarnerRado[i],3}{(i % 10 == 0 ? "\n" : " ")}");
}
Console.WriteLine();
 
int index = 1_000;
while (index <= limit) {
Console.WriteLine($"The {index}th element of Klarner-Rado sequence is {klarnerRado[index]}");
index *= 10;
}
}
 
private static int[] InitialiseKlarnerRadoSequence(int limit) {
int[] result = new int[limit + 1];
int i2 = 1, i3 = 1;
int m2 = 1, m3 = 1;
for (int i = 1; i <= limit; i++) {
int minimum = Math.Min(m2, m3);
result[i] = minimum;
if (m2 == minimum) {
m2 = result[i2] * 2 + 1;
i2 += 1;
}
if (m3 == minimum) {
m3 = result[i3] * 3 + 1;
i3 += 1;
}
}
return result;
}
}
</syntaxhighlight>
{{out}}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000th element of Klarner-Rado sequence is 8487
The 10000th element of Klarner-Rado sequence is 157653
The 100000th element of Klarner-Rado sequence is 2911581
The 1000000th element of Klarner-Rado sequence is 54381285
 
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
 
std::vector<uint32_t> initialise_klarner_rado_sequence(const uint32_t& limit) {
std::vector<uint32_t> result(limit + 1);
uint32_t i2 = 1, i3 = 1;
uint32_t m2 = 1, m3 = 1;
for ( uint32_t i = 1; i <= limit; ++i ) {
uint32_t minimum = std::min(m2, m3);
result[i] = minimum;;
if ( m2 == minimum ) {
m2 = result[i2] * 2 + 1;
i2++;
}
if ( m3 == minimum ) {
m3 = result[i3] * 3 + 1;
i3++;
}
}
return result;
}
 
int main() {
const uint32_t limit = 1'000'000;
std::vector<uint32_t> klarner_rado = initialise_klarner_rado_sequence(limit);
 
std::cout << "The first 100 elements of the Klarner-Rado sequence:" << std::endl;
for ( uint32_t i = 1; i <= 100; ++i ) {
std::cout << std::setw(3) << klarner_rado[i] << ( i % 10 == 0 ? "\n" : " " );
}
std::cout << std::endl;
 
uint32_t index = 1'000;
while ( index <= limit ) {
std::cout << "The " << index << "th element of Klarner-Rado sequence is " << klarner_rado[index] << std::endl;
index *= 10;
}
}
</syntaxhighlight>
{{ out }}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000th element of Klarner-Rado sequence is 8487
The 10000th element of Klarner-Rado sequence is 157653
The 100000th element of Klarner-Rado sequence is 2911581
The 1000000th element of Klarner-Rado sequence is 54381285
</pre>
 
=={{header|Delphi}}==
Line 608 ⟶ 740:
</pre>
 
 
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight>
m2 = 1
m3 = 1
for o = 1 to 1000000
if m2 < m3
m = m2
else
m = m3
.
klarner_rado[] &= m
if m2 = m
i2 += 1
m2 = klarner_rado[i2] * 2 + 1
.
if m3 = m
i3 += 1
m3 = klarner_rado[i3] * 3 + 1
.
.
for i = 1 to 100
write klarner_rado[i] & " "
.
print ""
print ""
i = 1000
while i < o
write klarner_rado[i] & " "
i *= 10
.
</syntaxhighlight>
 
=={{header|F_Sharp|F#}}==
Line 622 ⟶ 787:
kr[99999] is 2911581
kr[999999] is 54381285
</pre>
 
=={{header|Forth}}==
{{works with|Gforth}}
{{trans|C++}}
<syntaxhighlight lang="forth">1000000 constant limit
create kr_sequence limit 1+ cells allot
 
: kr cells kr_sequence + ;
 
: init_kr_sequence
1 1 1 1 { i2 i3 m2 m3 }
limit 1+ 1 do
m2 m3 min dup i kr !
dup m2 = if
i2 kr @ 2* 1+ to m2
i2 1+ to i2
then
m3 = if
i3 kr @ 3 * 1+ to m3
i3 1+ to i3
then
loop ;
 
: main
init_kr_sequence
." The first 100 elements of the Klarner-Rado sequence:" cr
101 1 do
i kr @ 3 .r
i 10 mod 0= if cr else space then
loop
cr
1000
begin
dup limit <=
while
." The "
dup 1 .r
." th element of the Klarner-Rado sequence is "
dup kr @ 1 .r cr
10 *
repeat
drop
;
 
main
bye
</syntaxhighlight>
 
{{out}}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000th element of the Klarner-Rado sequence is 8487
The 10000th element of the Klarner-Rado sequence is 157653
The 100000th element of the Klarner-Rado sequence is 2911581
The 1000000th element of the Klarner-Rado sequence is 54381285
</pre>
 
Line 732 ⟶ 964:
(1e6-1){kr7e7
54381285</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
public final class KlarnerRadoSequence {
 
public static void main(String[] args) {
final int limit = 1_000_000;
int[] klarnerRado = initialiseKlarnerRadoSequence(limit);
System.out.println("The first 100 elements of the Klarner-Rado sequence:");
for ( int i = 1; i <= 100; i++ ) {
System.out.print(String.format("%3d%s", klarnerRado[i], ( i % 10 == 0 ? "\n" : " " )));
}
System.out.println();
 
int index = 1_000;
while ( index <= limit ) {
System.out.println("The " + index + "th element of Klarner-Rado sequence is " + klarnerRado[index]);
index *= 10;
}
}
private static int[] initialiseKlarnerRadoSequence(int limit) {
int[] result = new int[limit + 1];
int i2 = 1, i3 = 1;
int m2 = 1, m3 = 1;
for ( int i = 1; i <= limit; i++ ) {
int minimum = Math.min(m2, m3);
result[i] = minimum;;
if ( m2 == minimum ) {
m2 = result[i2] * 2 + 1;
i2 += 1;
}
if ( m3 == minimum ) {
m3 = result[i3] * 3 + 1;
i3 += 1;
}
}
return result;
}
 
}
</syntaxhighlight>
{{ out }}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000th element of Klarner-Rado sequence is 8487
The 10000th element of Klarner-Rado sequence is 157653
The 100000th element of Klarner-Rado sequence is 2911581
The 1000000th element of Klarner-Rado sequence is 54381285
</pre>
 
=={{header|jq}}==
Line 906 ⟶ 1,200:
2911581
54381285</pre>
 
=={{header|Nim}}==
{{trans|C}}
Actually, this is not a direct translation, but an adaptation which uses the very efficient algorithm of the C solution. To find the 10_000_000 first elements, the program takes less than 80 ms on an Intel Core i5-8250U 1.60GHz.
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
 
const Elements = 10_000_000
type KlarnerRado = array[1..Elements, int]
 
proc initKlarnerRado(): KlarnerRado =
var i2, i3 = 1
var m2, m3 = 1
for i in 1..result.high:
let m = min(m2, m3)
result[i] = m
if m2 == m:
m2 = result[i2].int shl 1 or 1
inc i2
if m3 == m:
m3 = result[i3].int * 3 + 1
inc i3
 
let klarnerRado = initKlarnerRado()
 
echo "First 100 elements of the Klarner-Rado sequence:"
for i in 1..100:
stdout.write &"{klarnerRado[i]:>3}"
stdout.write if i mod 10 == 0: '\n' else: ' '
echo()
 
var i = 1000
while i <= Elements:
echo &"The {insertSep($i)}th element of Klarner-Rado sequence is {insertSep($klarnerRado[i])}"
i *= 10
</syntaxhighlight>
 
{{out}}
<pre>First 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1_000th element of Klarner-Rado sequence is 8_487
The 10_000th element of Klarner-Rado sequence is 157_653
The 100_000th element of Klarner-Rado sequence is 2_911_581
The 1_000_000th element of Klarner-Rado sequence is 54_381_285
The 10_000_000th element of Klarner-Rado sequence is 1_031_926_801
</pre>
 
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
KlamerRado(N) = {
my(kr = vector(100 * N), ret = [], idx = 1);
kr[1] = 1;
while (idx <= #kr / 3,
if (kr[idx],
if (2 * idx + 1 <= #kr, kr[2 * idx + 1] = 1);
if (3 * idx + 1 <= #kr, kr[3 * idx + 1] = 1);
);
idx++;
);
for (n = 1, #kr,
if (kr[n], ret = concat(ret, n));
);
ret
}
 
default(parisize, "1024M");
 
{
kr1m = KlamerRado(1000000);
 
print("First 100 Klarner-Rado numbers:");
for (i = 1, 100,
print1(kr1m[i], " ");
);
print();
 
print("The 1,000th Klarner-Rado number is ", kr1m[1000]);
print("The 10,000th Klarner-Rado number is ", kr1m[10000]);
print("The 100,000th Klarner-Rado number is ", kr1m[100000]);
print("The 1000,000th Klarner-Rado number is ", kr1m[1000000]);
}
</syntaxhighlight>
{{out}}
<pre>
First 100 Klarner-Rado numbers:
1 3 4 7 9 10 13 15 19 21 22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87 91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172 175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262 271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375 379 381 382 387 388 391 405 406 409 418
The 1,000th Klarner-Rado number is 8487
The 10,000th Klarner-Rado number is 157653
The 100,000th Klarner-Rado number is 2911581
The 1,000,000th Klarner-Rado number is 54381285
</pre>
 
 
=={{header|Perl}}==
Line 1,230 ⟶ 1,630:
54381285
1031926801</pre>
 
=={{header|Quackery}}==
 
<code>bsearchwith</code> is defined at [[Binary search#Quackery]].
 
<syntaxhighlight lang="Quackery"> [ over [] = iff
[ 2drop 0 0 ] done
over size 0 swap 2swap
bsearchwith < ] is search ( [ n --> n b )
 
[ [] ' [ 1 ]
rot times
[ 1 split dip join
over -1 peek
2 * 1+
2dup search iff
2drop
else
[ dip swap stuff ]
over -1 peek
3 * 1+
2dup search iff
2drop
else
[ dip swap stuff ] ]
drop ] is klarner-rado ( n --> [ )
 
10000 klarner-rado
say "First 100 Klarner-Rado numbers:" cr
dup 100 split drop
[] swap witheach
[ number$ nested join ]
80 wrap$
cr cr
say "1000th Klarner-Rado number: "
dup 999 peek echo
cr cr
say "10000th Klarner-Rado number: "
9999 peek echo</syntaxhighlight>
 
{{out}}
 
<pre>First 100 Klarner-Rado numbers:
 
1 3 4 7 9 10 13 15 19 21 22 27 28 31 39 40 43 45 46 55 57 58 63 64 67 79 81 82
85 87 91 93 94 111 115 117 118 121 127 129 130 135 136 139 159 163 165 166 171
172 175 183 187 189 190 193 202 223 231 235 237 238 243 244 247 255 256 259 261
262 271 273 274 279 280 283 319 327 331 333 334 343 345 346 351 352 355 364 367
375 379 381 382 387 388 391 405 406 409 418
 
1000th Klarner-Rado number: 8487
 
10000th Klarner-Rado number: 157653</pre>
 
=={{header|Raku}}==
Line 1,276 ⟶ 1,729:
One hundred thousandth element: 2,911,581
One millionth element: 54,381,285</pre>
 
=={{header|Refal}}==
<syntaxhighlight lang="Refal">$ENTRY Go {
, <KlarnerRado 10000>: e.K
= <Prout 'First 100 Klarner-Rado sequence numbers:'>
<Table (10 5) <Take 100 e.K>>
<Prout 'The 1,000th Klarner-Rado number is: ' <Item 1000 e.K>>
<Prout 'The 10,000th Klarner-Rado number is: ' <Item 10000 e.K>>;
};
 
KlarnerRado {
s.N = <KlarnerRado <- s.N 1> () 1>;
0 (e.X) e.Y = e.X e.Y;
s.N (e.X) s.I e.Y,
<+ 1 <* 2 s.I>>: s.J,
<+ 1 <* 3 s.I>>: s.K
= <KlarnerRado <- s.N 1> (e.X s.I)
<Insert s.J <Insert s.K e.Y>>>;
};
 
Insert {
s.N = s.N;
s.N s.N e.R = s.N e.R;
s.N s.M e.R, <Compare s.N s.M>: {
'-' = s.N s.M e.R;
s.X = s.M <Insert s.N e.R>;
};
};
 
Take {
0 e.X = ;
s.N s.I e.X = s.I <Take <- s.N 1> e.X>;
};
 
Item {
1 s.I e.X = s.I;
s.N s.I e.X = <Item <- s.N 1> e.X>;
};
 
Repeat {
0 s.C = ;
s.N s.C = s.C <Repeat <- s.N 1> s.C>;
};
 
Cell {
s.CW s.N, <Repeat s.CW ' '> <Symb s.N>: e.C,
<Last s.CW e.C>: (e.X) e.CI = e.CI;
};
 
Table {
(s.LW s.CW) e.X = <Table (s.LW s.CW s.LW) e.X>;
(s.LW s.CW 0 e.L) e.X = <Prout e.L> <Table (s.LW s.CW s.LW) e.X>;
(s.LW s.CW s.N e.L), e.L: { = ; e.L = <Prout e.L>; };
(s.LW s.CW s.N e.L) s.I e.X =
<Table (s.LW s.CW <- s.N 1> e.L <Cell s.CW s.I>) e.X>;
};</syntaxhighlight>
{{out}}
<pre>First 100 Klarner-Rado sequence numbers:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
The 1,000th Klarner-Rado number is: 8487
The 10,000th Klarner-Rado number is: 157653</pre>
 
=={{header|Rust}}==
{{trans|Java}}
<syntaxhighlight lang="Rust">
fn main() {
let limit = 1_000_000;
let klarner_rado = initialise_klarner_rado_sequence(limit);
 
println!("The first 100 elements of the Klarner-Rado sequence:");
for i in 1..=100 {
print!("{:3}", klarner_rado[i]);
if i % 10 == 0 {
println!();
} else {
print!(" ");
}
}
println!();
 
let mut index = 1_000;
while index <= limit {
println!("The {}th element of Klarner-Rado sequence is {}", index, klarner_rado[index]);
index *= 10;
}
}
 
fn initialise_klarner_rado_sequence(limit: usize) -> Vec<usize> {
let mut result = vec![0; limit + 1];
let mut i2 = 1;
let mut i3 = 1;
let mut m2 = 1;
let mut m3 = 1;
 
for i in 1..=limit {
let minimum = std::cmp::min(m2, m3);
result[i] = minimum;
if m2 == minimum {
m2 = result[i2] * 2 + 1;
i2 += 1;
}
if m3 == minimum {
m3 = result[i3] * 3 + 1;
i3 += 1;
}
}
result
}
</syntaxhighlight>
{{out}}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000th element of Klarner-Rado sequence is 8487
The 10000th element of Klarner-Rado sequence is 157653
The 100000th element of Klarner-Rado sequence is 2911581
The 1000000th element of Klarner-Rado sequence is 54381285
</pre>
 
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
object KlarnerRadoSequence extends App {
val limit = 1_000_000
val klarnerRado = initialiseKlarnerRadoSequence(limit)
 
println("The first 100 elements of the Klarner-Rado sequence:")
for (i <- 1 to 100) {
print(f"${klarnerRado(i)}%3d")
if (i % 10 == 0) println() else print(" ")
}
println()
 
var index = 1_000
while (index <= limit) {
println(s"The $index th element of Klarner-Rado sequence is ${klarnerRado(index)}")
index *= 10
}
 
def initialiseKlarnerRadoSequence(limit: Int): Array[Int] = {
val result = new Array[Int](limit + 1)
var i2 = 1
var i3 = 1
var m2 = 1
var m3 = 1
for (i <- 1 to limit) {
val minimum = math.min(m2, m3)
result(i) = minimum
if (m2 == minimum) {
m2 = result(i2) * 2 + 1
i2 += 1
}
if (m3 == minimum) {
m3 = result(i3) * 3 + 1
i3 += 1
}
}
result
}
}
</syntaxhighlight>
{{out}}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000 th element of Klarner-Rado sequence is 8487
The 10000 th element of Klarner-Rado sequence is 157653
The 100000 th element of Klarner-Rado sequence is 2911581
The 1000000 th element of Klarner-Rado sequence is 54381285
</pre>
 
=={{header|SETL}}==
{{works with|GNU SETL}}
 
Abusing the set mechanism makes this very straightforward, without incurring a terrible performance hit: finding a million items takes 5 seconds on a 2.6GHz Core 2 Duo.
 
<syntaxhighlight lang="setl">program Klarner_Rado_sequence;
init K := kr(10**6);
 
print('First 100 Klarner-Rado sequence numbers:');
loop for n in K(1..100) do
nprint(lpad(str n, 5));
if (c +:= 1) mod 10 = 0 then
print;
end if;
end loop;
 
loop for p in [3..6] do
n := 10**p;
print('The ' + str n + 'th Klarner-Rado number is '
+ str K(n) + '.');
end loop;
 
proc kr(amt);
seq := [];
prc := {1};
loop while #seq < amt do
n from prc;
seq with:= n;
prc with:= 2*n + 1;
prc with:= 3*n + 1;
end loop;
return seq;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>
First 100 Klarner-Rado sequence numbers:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
The 1000th Klarner-Rado number is 8487.
The 10000th Klarner-Rado number is 157653.
The 100000th Klarner-Rado number is 2911581.
The 1000000th Klarner-Rado number is 54381285.</pre>
 
=={{header|Swift}}==
{{trans|Rust}}
<syntaxhighlight lang="swift">
import Foundation
 
func initKlarnerRadoSequence(limit: Int) -> [Int] {
var result = Array(repeating: 0, count: limit + 1)
var i2 = 1
var i3 = 1
var m2 = 1
var m3 = 1
for i in 1...limit {
let minimum = min(m2, m3)
result[i] = minimum
if m2 == minimum {
m2 = result[i2] * 2 + 1
i2 += 1
}
if m3 == minimum {
m3 = result[i3] * 3 + 1
i3 += 1
}
}
return result
}
 
let limit = 1000000
let klarnerRado = initKlarnerRadoSequence(limit: limit)
 
print("The first 100 elements of the Klarner-Rado sequence:")
for i in 1...100 {
print(String(format: "%3d", klarnerRado[i]), terminator: "")
if i % 10 == 0 {
print()
} else {
print(" ", terminator: "")
}
}
print()
 
var index = 1000
while index <= limit {
print("The \(index)th element of Klarner-Rado sequence is \(klarnerRado[index])")
index *= 10
}</syntaxhighlight>
 
{{out}}
<pre>
The first 100 elements of the Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21
22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87
91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172
175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262
271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375
379 381 382 387 388 391 405 406 409 418
 
The 1000th element of Klarner-Rado sequence is 8487
The 10000th element of Klarner-Rado sequence is 157653
The 100000th element of Klarner-Rado sequence is 2911581
The 1000000th element of Klarner-Rado sequence is 54381285
</pre>
 
=={{header|Visual Basic .NET}}==
Line 1,399 ⟶ 2,170:
{{libheader|Wren-fmt}}
There's no actual sorting here. The Find class (and its binary search methods) just happen to be in Wren-sort.
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Find
import "./fmt" for Fmt
 
Line 1,457 ⟶ 2,228:
 
Although not shown here, if the size of the BitArray is increased to 1.1 billion and 'max' to 1e7, then the 10 millionth element (1,031,926,801) will eventually be found but takes 4 minutes 50 seconds to do so.
<syntaxhighlight lang="ecmascriptwren">import "./array" for BitArray
import "./fmt" for Fmt
 
Line 1,512 ⟶ 2,283:
{{trans|C}}
Astonishingly fast algorithm compared to the first two versions. Finds the 10 millionth element in a little over 1 second.
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var klarnerRado = Fn.new { |n|
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340846...363353"