Klarner-Rado sequence: Difference between revisions
lang -> syntaxhighlight
m (→{{header|Haskell}}: (zero - indexed -> one - indexed for Kth 10Kth)) |
(lang -> syntaxhighlight) |
||
Line 33:
=={{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;
Line 75:
FI
OD
END</
{{out}}
<pre>
Line 92:
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)
Line 150:
end task
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
Line 162:
10,000th element: 157653
100,000th element: 2911581
1,000,000th element: 54381285"</
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
Line 294:
end task
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]
</syntaxhighlight>
{{out}}
<pre>
Line 313:
=={{header|FreeBASIC}}==
{{trans|Phix}}
<
Dim As Integer limit = 1e8
Line 342:
End If
Next i
Sleep</
{{out}}
<pre>Same as Phix entry.</pre>
Line 401:
=={{header|J}}==
Implementation:<
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
}}</
Task examples (including stretch):<
1215307
100{.kr7e7
Line 419:
2911581
(1e6-1){kr7e7
54381285</
=={{header|Julia}}==
<
function KlarnerRado(N)
Line 451:
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:
Line 466:
=== 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)
Line 486:
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>
Line 520:
<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>
Line 539:
<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 */
Line 607:
END;
EOF</
{{out}}
<pre>
Line 619:
=={{header|Python}}==
<
K = [1]
for i in range(N):
Line 648:
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:
Line 662:
=== faster version ===
<
def KlarnerRado(N):
Line 681:
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;
Line 707:
put '';
put (($_».Int».&ordinal».tc »~» ' element: ').List Z~ |(List.new: (Klarner-Rado ($_ »-» 1))».&comma)
given $(1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6)).join: "\n";</
{{out}}
<pre>First 100 elements of Klarner-Rado sequence:
Line 731:
=={{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
Line 830:
End Sub
End Module</
{{out}}
<pre>
Line 851:
{{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
Line 877:
for (limit in limits) {
Fmt.print("The $,r element: $,d", limit, kr[limit-1])
} </
{{out}}
Line 909:
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
Line 954:
Fmt.print("The $,r element: $,d", limit, pow10[limit])
limit = 10 * limit
}</
{{out}}
|