Klarner-Rado sequence: Difference between revisions

 

Klarner-Rado sequences are a class of similar sequences that were studied by the mathematicians David Klarner and Richard Rado.

 

<br>

 

=={{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>

 

=={{header|AppleScript}}==

 

-- Fully recursive:

 

on isKlarnerRado(n)

repeat

return true

return false

end if

end repeat

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>

kr[99999] is 2911581

kr[999999] is 54381285

</pre>

 

=={{header|FreeBASIC}}==

{{trans|Phix}}

 

Dim As Integer limit = 1e8

End If

Next i

{{out}}

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

 

=={{header|Haskell}}==

import Data.List.Ordered (union)

import Data.List.Split (chunksOf)

----------------------- KLARNER-RADO ---------------------

 

klarnerRado =

 

--------------------------- TEST -------------------------

mapM_

putStrLn

putStrLn "\nKth and 10Kth elements of the sequence:\n"

mapM_

{{Out}}

<pre>First one hundred elements of the sequence:

Kth and 10Kth elements of the sequence:

 

 

=={{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>

</pre>

Unfortunately JavaScript can't quite cope/runs out of memory with a 100 million element sieve, so it only goes to the 10^5th under p2js.

 

=={{header|PL/M}}==

<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:

One hundred thousandth element: 2,911,581

One millionth element: 54,381,285</pre>

 

=={{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}}

<pre>

Same as Version 1.

</pre>