Klarner-Rado sequence: Difference between revisions

=={{header|ALGOL 68}}==

Generates the sequence in order. Note that to run this with ALGOL 68G under Windows (and probably Linux), a large heap size must be specified on the command line, e.g.: <code>-heap 1024M</code>.

# - if n is an element, so are 2n + 1 and 3n + 1 #

INT max element = 100 000 000;

FI

OD

{{out}}

<pre>

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 0. It makes finding the elements in order simple, but takes about five and a half minutes to get to the millionth one.

-- Fully recursive:

(* on isKlarnerRado(n)

end task

{{output}}

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

10,000th element: 157653

100,000th element: 2911581

Another way is to produce a list with Klarner-Rado elements in the slots indexed by those numbers and 'missing values' in the other slots. If a number being tested is exactly divisible by 2 or by 3, and the slot whose index is the result of the division contains a number instead of 'missing value', the tested number plus 1 is a Klarner-Rado element and should go into the slot it indexes. The list will contain vastly more 'missing values' than Klarner-Rado elements and it — or portions of it — ideally need to exist before the sequence elements are inserted. So while an overabundance and sorting of sequence elements isn't needed, an overabundance of 'missing values' is! The script below carries out the task in about 75 seconds on my current machine and produces the same output as above.

-- To find a million KR numbers with this method nominally needs a list with at least 54,381,285

-- slots. But the number isn't known in advance, "growing" a list to the required length would

end task

=={{header|F_Sharp|F#}}==

// Klarner-Rado sequence. Nigel Galloway: August 19th., 20

let kr()=Seq.unfold(fun(n,g)->Some(g|>Seq.filter((>)n)|>Seq.sort,(n*2L+1L,seq[for n in g do yield n; yield n*2L+1L; yield n*3L+1L]|>Seq.filter((<=)n)|>Seq.distinct)))(3L,seq[1L])|>Seq.concat

let n=kr()|>Seq.take 1000000|>Array.ofSeq in n|>Array.take 100|>Array.iter(printf "%d "); printfn "\nkr[999] is %d\nkr[9999] is %d\nkr[99999] is %d\nkr[999999] is %d" n.[999] n.[9999] n.[99999] n.[999999]

{{out}}

<pre>

=={{header|FreeBASIC}}==

{{trans|Phix}}

Dim As Integer limit = 1e8

End If

Next i

{{out}}

<pre>Same as Phix entry.</pre>

=={{header|J}}==

for_i. i.<.-:#b=. (1+y){.0 1 do.

if. i{b do. b=. 1 ((#~ y&>)1+2 3*i)} b end.

end.

I.b

1215307

100{.kr7e7

2911581

(1e6-1){kr7e7

=={{header|Julia}}==

function KlarnerRado(N)

foreach(n -> println("The ", format(n, commas=true), "th Klarner-Rado number is ",

format(kr1m[n], commas=true)), [1000, 10000, 100000, 1000000])

<pre>

First 100 Klarner-Rado numbers:

=== Faster version ===

Probably does get an overabundance, but no sorting. `falses()` is implemented as a bit vector, so huge arrays are not needed. From ALGOL.

function KlamerRado(N)

foreach(n -> println("The ", format(n, commas=true), "th Klarner-Rado number is ",

format(kr1m[n], commas=true)), [1000, 10000, 100000, 1000000])

=={{header|Phix}}==

{{trans|ALGOL_68}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">10_000_000</span><span style="color: #0000FF;">:</span><span style="color: #000000;">100_000_000</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

<br>

As PL/M only handles unsigned 8 and 16 bit integers, this only finds the first 1000 elements. This is based on the Algol 68 sample, but as with the VB.NET sample, uses a "bit vector" (here an array of bytes) - as suggested by the Julia sample.

/* - IF N IS AN ELEMENT, SO ARE 2N+1 AND 3N+!, 1 IS AN ELEMENT */

END;

{{out}}

<pre>

=={{header|Python}}==

K = [1]

for i in range(N):

for n in [1000, 10_000, 100_000]:

print(f'The {n :,}th Klarner-Rado number is {kr1m[n-1] :,}')

<pre>

First 100 Klarner-Rado sequence numbers:

=== faster version ===

def KlarnerRado(N):

for n in [1000, 10_000, 100_000, 1_000_000]:

print(f'The {n :,}th Klarner-Rado number is {kr1m[n-1] :,}')

=={{header|Raku}}==

my @klarner-rado = 1;

my @next = x2, x3;

put '';

put (($_».Int».&ordinal».tc »~» ' element: ').List Z~ |(List.new: (Klarner-Rado ($_ »-» 1))».&comma)

{{out}}

<pre>First 100 elements of Klarner-Rado sequence:

=={{header|Visual Basic .NET}}==

Based on the ALGOL 68 sample, but using a "bit vector" (array of integers), as suggested by the Julia sample. Simplifies printing "the powers of ten" elements, as in the Phix sample.

Option Explicit On

End Sub

{{out}}

<pre>

{{libheader|Wren-fmt}}

There's no actual sorting here. The Find class (and its binary search methods) just happen to be in Wren-sort.

import "./fmt" for Fmt

for (limit in limits) {

Fmt.print("The $,r element: $,d", limit, kr[limit-1])

{{out}}

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.

import "./fmt" for Fmt

Fmt.print("The $,r element: $,d", limit, pow10[limit])

limit = 10 * limit

{{out}}