Jump to content

Klarner-Rado sequence

From Rosetta Code
Task
Klarner-Rado sequence
You are encouraged to solve this task according to the task description, using any language you may know.

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

The most well known is defined as the thinnest strictly ascending sequence K which starts 1, then, for each element n, it will also contain somewhere in the sequence, 2 × n + 1 and 3 × n + 1.


So, the sequence K starts with 1.

Set n equal to the first element 1; the sequence will also contain 2 × n + 1 and 3 × n + 1, or 3 and 4.

Set n equal to the next element: 3, somewhere in the sequence it will contain 2 × n + 1 and 3 × n + 1, or 7 and 10.

Continue setting n equal to each element in turn to add to the sequence.


Task
  • Find and display the first one hundred elements of the sequence.
  • Find and display the one thousandth and ten thousandth elements of the sequence.

Preferably without needing to find an over abundance and sorting.


Stretch
  • Find and display the one hundred thousandth and one millionth elements of the sequence.


See also


11l

Translation of: Python
F klarner_rado(n)
   V K = [1]
   L(i) 0 .< n
      V j = K[i]
      V (firstadd, secondadd) = (2 * j + 1, 3 * j + 1)
      I firstadd < K.last
         L(pos) (K.len - 1 .< 1).step(-1)
            I K[pos] < firstadd & firstadd < K[pos + 1]
               K.insert(pos + 1, firstadd)
               L.break
      E I firstadd > K.last
         K.append(firstadd)
      I secondadd < K.last
         L(pos) (K.len - 1 .< 1).step(-1)
            I K[pos] < secondadd & secondadd < K[pos + 1]
               K.insert(pos + 1, secondadd)
               L.break
      E I secondadd > K.last
         K.append(secondadd)

   R K

V kr1m = klarner_rado(100'000)

print(‘First 100 Klarner-Rado sequence numbers:’)
L(v) kr1m[0.<100]
   print(f:‘ {v:3}’, end' I (L.index + 1) % 20 == 0 {"\n"} E ‘’)
L(n) [1000, 10'000, 100'000]
   print(f:‘The {commatize(n)}th Klarner-Rado number is {commatize(kr1m[n - 1])}’)
Output:
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 8,487
The 10,000th Klarner-Rado number is 157,653
The 100,000th Klarner-Rado number is 2,911,581

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.: -heap 1536M.

BEGIN # find elements of the Klarner-Rado sequence                           #
      #    - if n is an element, so are 2n + 1 and 3n + 1                    #
    INT max element = 100 000 000;
    [ 0 : max element ]BOOL kr; FOR i FROM LWB kr TO UPB kr DO kr[ i ] := FALSE OD;
    INT n21      := 3;                    # next 2n+1 value                  #
    INT n31      := 4;                    # next 3n+1 value                  #
    INT p2       := 1;                    # the n for the next 2n+1 value    #
    INT p3       := 1;                    # the n for the next 3n+1 value    #
    kr[ 1 ]      := TRUE;
    INT kr count := 0;
    INT max count = 1 000 000;
    FOR i WHILE kr count < max count DO
        IF i = n21 THEN                   # found the next 2n+1 value        #
            IF kr[ p2 ] THEN
                kr[ i ] := TRUE
            FI;
            p2  +:= 1;
            n21 +:= 2
        FI;
        IF i = n31 THEN                   # found the next 3n+1 value        #
            IF kr[ p3 ] THEN
                kr[ i ] := TRUE
            FI;
            p3  +:= 1;
            n31 +:= 3
        FI;
        IF kr[ i ] THEN
            kr count +:= 1;
            IF   kr count <= 100 THEN
                print( ( " ", whole( i, -3 ) ) );
                IF kr count MOD 20 = 0 THEN print( ( newline ) ) FI
            ELIF kr count =     1 000 THEN
                print( ( "The     thousandth element is ", whole( i, -8 ), newline ) )
            ELIF kr count =    10 000 THEN
                print( ( "The ten thousandth element is ", whole( i, -8 ), newline ) )
            ELIF kr count =   100 000 THEN
                print( ( "The 100-thousandth element is ", whole( i, -8 ), newline ) )
            ELIF kr count = 1 000 000 THEN
                print( ( "The      millionth element is ", whole( i, -8 ), newline ) )
            FI
        FI
    OD
END
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
 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     thousandth element is     8487
The ten thousandth element is   157653
The 100-thousandth element is  2911581
The      millionth element is 54381285

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 1. It makes finding the elements in order simple, but takes nearly six minutes to get a million of them.

-- Is n in the Klarner-Rado sequence?
-- Fully recursive:
(*
on isKlarnerRado(n)
    return ((n = 1) or ((n mod 3 = 1) and (isKlarnerRado(n div 3))) or ¬
        ((n mod 2 = 1) and (isKlarnerRado(n div 2))))
end isKlarnerRado
*)

-- With tail call elimination. About a minute 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)
    repeat
        if ((n = 1) or ((n mod 3 = 1) and (isKlarnerRado(n div 3)))) then
            return true
        else if (n mod 2 < 1) then
            return false
        else
            set n to n div 2
        end if
    end repeat
end isKlarnerRado

on join(lst, delim)
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to delim
    set txt to lst as text
    set AppleScript's text item delimiters to astid
    return txt
end join

on task()
    set output to {"First 100 elements:"}
    set n to 0
    set |count| to 0
    set K to {}
    repeat until (|count| = 100)
        set n to n + 1
        if (isKlarnerRado(n)) then
            set K's end to n
            set |count| to |count| + 1
        end if
    end repeat
    repeat with i from 1 to 100 by 20
        set output's end to join(K's items i thru (i + 19), "  ")
    end repeat
    
    repeat with this in {{1000, "1,000th element: "}, {10000, "10,000th element: "}, {100000, "100,000th element: "}, ¬
        {1000000, "1,000,000th element: "}}
        set {target, spiel} to this
        repeat until (|count| = target)
            set n to n + 1
            if (isKlarnerRado(n)) then set |count| to |count| + 1
        end repeat
        set output's end to spiel & n
    end repeat
    
    return join(output, linefeed)
end task

task()
Output:
"First 100 elements:
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
1,000th element: 8487
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.

on KlarnerRadoSequence(target)
    -- 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
    -- take forever, and accessing its individual items could also take a while. Instead, K will
    -- here contain reasonably sized and quickly produced sublists which are added as needed.
    -- The 1-based referencing calculations will be ((index - 1) div sublistLen + 1) for the sublist
    -- and ((index - 1) mod sublistLen + 1) for the slot within it.
    set sublistLen to 10000
    script o
        property spare : makeList(sublistLen, missing value)
        property K : {spare's items}
    end script
    
    -- Insert the initial 1, start the KR counter at 1, start the number-to-test variable at 2.
    set {o's K's beginning's 1st item, |count|, n} to {1, 1, 2}
    -- Test the first, second, third, and fifth of every six consecutive numbers starting at 2.
    -- These are known to be divisible by 2 or by 3 and the fourth and sixth known not to be.
    -- If the item at index (n div 2) or index (n div 3) isn't 'missing value', it's a number,
    -- so insert (n + 1) at index (n + 1).
    if (|count| < target) then ¬
        repeat -- Per increase of n by 6.
            -- The first of the six numbers in this range is divisible by 2.
            -- Precalculate (index - 1) for index (n div 2) to reduce code clutter and halve calculation time.
            set pre to n div 2 - 1
            if (o's K's item (pre div sublistLen + 1)'s item (pre mod sublistLen + 1) is missing value) then
            else
                -- Insert (n + 1) at index (n + 1). The 'n's in the reference calculations are for ((n + 1) - 1)!
                set o's K's item (n div sublistLen + 1)'s item (n mod sublistLen + 1) to n + 1
                set |count| to |count| + 1
                if (|count| = target) then exit repeat
            end if
            -- The second number of the six is divisible by 3.
            set n to n + 1
            set pre to n div 3 - 1
            if (o's K's item (pre div sublistLen + 1)'s item (pre mod sublistLen + 1) is missing value) then
            else
                set o's K's item (n div sublistLen + 1)'s item (n mod sublistLen + 1) to n + 1
                set |count| to |count| + 1
                if (|count| = target) then exit repeat
            end if
            -- The third is divisible by 2.
            set n to n + 1
            set pre to n div 2 - 1
            if (o's K's item (pre div sublistLen + 1)'s item (pre mod sublistLen + 1) is missing value) then
            else
                set o's K's item (n div sublistLen + 1)'s item (n mod sublistLen + 1) to n + 1
                set |count| to |count| + 1
                if (|count| = target) then exit repeat
            end if
            -- The fifth is divisible by both 2 and 3.
            set n to n + 2
            set pre2 to n div 2 - 1
            set pre3 to n div 3 - 1
            if ((o's K's item (pre2 div sublistLen + 1)'s item (pre2 mod sublistLen + 1) is missing value) and ¬
                (o's K's item (pre3 div sublistLen + 1)'s item (pre3 mod sublistLen + 1) is missing value)) then
            else
                set o's K's item (n div sublistLen + 1)'s item (n mod sublistLen + 1) to n + 1
                set |count| to |count| + 1
                if (|count| = target) then exit repeat
            end if
            
            -- Advance to the first number of the next six.
            set n to n + 2
            -- If another sublist is about to be needed, append one to the end of K.
            if ((n + 6) mod sublistLen < 6) then copy o's spare to o's K's end
        end repeat
    
    -- Once the target's reached, replace the sublists with lists containing just the numbers.
    set sublistCount to (count o's K)
    repeat with i from 1 to sublistCount
        set o's K's item i to o's K's item i's numbers
    end repeat
    -- Concatenate the number lists to leave K as a single list of numbers.
    repeat while (sublistCount > 1)
        set o's spare to o's K
        set o's K to {}
        repeat with i from 2 to sublistCount by 2
            set end of o's K to o's spare's item (i - 1) & o's spare's item i
        end repeat
        if (i < sublistCount) then set o's K's last item to o's K's end & o's spare's end
        set sublistCount to sublistCount div 2
    end repeat
    set o's K to o's K's beginning
    
    return o's K
end KlarnerRadoSequence

on makeList(len, content)
    script o
        property lst : {}
    end script
    if (len > 0) then
        set o's lst's end to content
        set |count| to 1
        repeat until (|count| + |count| > len)
            set o's lst to o's lst & o's lst
            set |count| to |count| + |count|
        end repeat
        if (|count| < len) then set o's lst to o's lst & o's lst's items 1 thru (len - |count|)
    end if
    
    return o's lst
end makeList

on join(lst, delim)
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to delim
    set txt to lst as text
    set AppleScript's text item delimiters to astid
    return txt
end join

on task()
    script o
        property K : KlarnerRadoSequence(1000000)
    end script
    set output to {"First 100 elements:"}
    repeat with i from 1 to 100 by 20
        set output's end to join(o's K's items i thru (i + 19), "  ")
    end repeat
    set output's end to "1,000th element: " & o's K's item 1000
    set output's end to "10,000th element: " & o's K's item 10000
    set output's end to "100,000th element: " & o's K's item 100000
    set output's end to "1,000,000th element: " & o's K's item 1000000
    
    return join(output, linefeed)
end task

task()

AWK

BEGIN {
    for (m2 = m3 = o = 1; o <= 1000000; ++o) {
        klarner_rado[o] = m = m2 < m3 ? m2 : m3
        if (m2 == m) m2 = klarner_rado[++i2] * 2 + 1
        if (m3 == m) m3 = klarner_rado[++i3] * 3 + 1
    }

    for (i = 1; i < 100; ++i)
        printf "%u ", klarner_rado[i]
    for (i = 100; i < o; i *= 10)
        print klarner_rado[i]
}
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 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
8487
157653
2911581
54381285

bc

POSIX requires support for 2048 array elements only, so getting up to the 10.000th value might not work with all bc implementations.

for (a = b = 1; o != 10000; ++o) {
    if (m = a > b) m = b
    q[o] = m
    if (a == m) a = q[i++] * 2 + 1
    if (b == m) b = q[j++] * 3 + 1
}

for (i = 0; i != 100; ++i) q[i]
"1000th: "
q[999]
"10000th: "
q[9999]
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
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: 8487
10000th: 157653

C

#include <stdio.h>

#define ELEMENTS 10000000U

void make_klarner_rado(unsigned int *dst, unsigned int n) {
    unsigned int i, i2 = 0, i3 = 0;
    unsigned int m, m2 = 1, m3 = 1;

    for (i = 0; i < n; ++i) {
        dst[i] = m = m2 < m3 ? m2 : m3;
        if (m2 == m) m2 = dst[i2++] << 1 | 1;
        if (m3 == m) m3 = dst[i3++] * 3 + 1;
    }
}

int main(void) {
    static unsigned int klarner_rado[ELEMENTS];
    unsigned int i;

    make_klarner_rado(klarner_rado, ELEMENTS);

    for (i = 0; i < 99; ++i)
        printf("%u ", klarner_rado[i]);
    for (i = 100; i <= ELEMENTS; i *= 10)
        printf("%u\n", klarner_rado[i - 1]);

    return 0;
}
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 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
8487
157653
2911581
54381285
1031926801


C#

Translation of: Java
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;
    }
}
Output:
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

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;
	}
}
Output:
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

Delphi

Works with: Delphi version 6.0


function SortCompare(Item1, Item2: Pointer): Integer;
{Custom compare to order the list}
begin
Result:=Integer(Item1)-Integer(Item2);
end;

procedure KlarnerRadoSeq(Memo: TMemo);
{Display Klarner-Rado sequence}
var LS: TList;
var I,N: integer;
var S: string;

	procedure AddItem(N: integer);
	{Add item to list avoiding duplicates}
	begin
	if LS.IndexOf(Pointer(N))>=0 then exit;
	LS.Add(Pointer(N));
	end;

	function FormatInx(Inx: integer): string;
	{Specify an index into the array}
	{Returns a formated number}
	var D: double;
	begin
	D:=Integer(LS[Inx]);
	Result:=Format('%11.0n',[D]);
	end;

begin
LS:=TList.Create;
try
{Add string value}
LS.Add(Pointer(1));
{Add two new items to the list}
for I:=0 to high(integer) do
	begin
	N:=Integer(LS[I]);
	AddItem(2 * N + 1);
	AddItem(3 * N + 1);
	if LS.Count>=100001 then break;
	end;
{Put the data in numerical order}
LS.Sort(SortCompare);
{Display data}
S:='[';
for I:=0 to 99 do
	begin
	if I<>0 then S:=S+' ';
	S:=S+Format('%4d',[Integer(LS[I])]);
	if (I mod 10)=9 then
		begin
		if I=99 then S:=S+']';
		S:=S+#$0D#$0A;
		end;
	end;
Memo.Lines.Add(S);
Memo.Lines.Add('The   1,000th '+FormatInx(1000));
Memo.Lines.Add('The  10,000th '+FormatInx(10000));
Memo.Lines.Add('The 100,000th '+FormatInx(100000));
finally LS.Free; end;
end;
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
  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       8,488
The  10,000th     157,654
The 100,000th  50,221,174


EasyLang

Translation of: AWK
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
.

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]
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 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
kr[999] is 8487
kr[9999] is 157653
kr[99999] is 2911581
kr[999999] is 54381285

Forth

Works with: Gforth
Translation of: C++
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
Output:
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

FreeBASIC

Translation of: Phix
#include "string.bi"

Dim As Integer limit = 1e8
Dim As Boolean kr(limit)
kr(1) = True
Dim As Integer n21 = 3, n31 = 4, p2 = 1, p3 = 1, count = 0, np10 = 1000
Print "First 100 Klarner-Rado sequence numbers:"
For i As Integer = 1 To limit
    If i = n21 Then
        If kr(p2) Then kr(i) = True
        p2  += 1
        n21 += 2
    End If
    If i = n31 Then
        If kr(p3) Then kr(i) = True
        p3  += 1
        n31 += 3
    End If
    If kr(i) Then
        count += 1
        If count <= 100 Then
            Print Using "####"; i;
            If(count Mod 20) = 0 Then Print
        Elseif count = np10 Then
            Print "The "; Format(count, "#,###,###"); "th Klarner-Rado number is "; Format(i, "#,###,###")
            np10 *= 10
        End If
    End If
Next i
Sleep
Output:
Same as Phix entry.

Haskell

import Data.List (intercalate)
import Data.List.Ordered (union)
import Data.List.Split (chunksOf)
import Text.Printf (printf)

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

klarnerRado :: [Integer]
klarnerRado =
  1 : 
  union 
    (succ . (2 *) <$> klarnerRado) 
    (succ . (3 *) <$> klarnerRado)


--------------------------- TEST -------------------------
main :: IO ()
main = do
  putStrLn "First one hundred elements of the sequence:\n"
  mapM_
    putStrLn
    (intercalate "  " <$> chunksOf 10 
      (printf "%3d" <$> take 100 klarnerRado))
      
  putStrLn "\nKth and 10Kth elements of the sequence:\n"
  mapM_
    (putStrLn .
      (<*>) (flip (printf "%7dth %s %8d") " ->") 
      ((klarnerRado !!) . pred)) $
        (10 ^) <$> [3 .. 6]
Output:
First one hundred elements of the 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

Kth and 10Kth elements of the sequence:

   1000th  ->     8487
  10000th  ->   157653
 100000th  ->  2911581
1000000th  -> 54381285

J

Implementation:

krsieve=: {{ 
  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):

   #kr7e7=: krsieve 7e7
1215307
   100{.kr7e7
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
   (1e3-1){kr7e7
8487
   (1e4-1){kr7e7
157653
   (1e5-1){kr7e7
2911581
   (1e6-1){kr7e7
54381285

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;
	}

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

jq

The following program is a straightforward specification-based implementation that simply keeps track of the 2*i+1 and 3*i+1 values in an array. Binary search is used to avoid sorting.

To show how rapidly the array grows, its length is included in the output for the second task.

Apart from the use of jq's builtin `bsearch` for binary search, the implementation is possibly of some interest in that it illustrates how jq's `foreach` function can be used.

Generic Utility

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

Klarner-Rado Sequence

# $count  should be an integer or `infinite`, 
#         where 0 and `infinite` induce the same behavior,
# Output: if $count is greater than 0, then a stream of that many
#         values of the Klarner-Rado sequence is emitted;
#         otherwise [i, value, length] is printed for every i that is a power of 10,
#         where value is the i-th value (counting from 1), and length is the
#         length of the array of pending values.
def klarnerRado($count):

  # insert into a sorted array
  def insert($x):
    if .[-1] < $x then . + [$x]
    else bsearch($x) as $ix
    | if $ix > -1 then . else .[:-1-$ix] + [$x] + .[-1-$ix:] end
    end ;

  ($count | isfinite and . > 0) as $all
  | foreach range(1; if $count == 0 then infinite else $count + 1 end) as $i (
      {array:[1]};
      
      .i = $i
      | .emit = .array[0]
      | (.emit * 2 + 1) as $two
      | (.emit * 3 + 1) as $three
      | .array |= (.[1:] | insert($two) | insert($three) ) ;

      if $all then .emit
      elif ($i | tostring | test("^10*$"))
      then [.i, .emit, (.array|length)]
      else empty
      end );

([klarnerRado(100)] | _nwise(10) | map(lpad(3)) | join(" ")),
"",

"# [i, value, length]",
limit(7; klarnerRado(infinite))

Invocation

jq -ncrf klarner-rado.jq
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
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

# [i, value, length]
[1,1,2]
[10,21,10]
[100,418,99]
[1000,8487,992]
[10000,157653,9959]
[100000,2911581,99823]
[1000000,54381285,999212]

Julia

using Formatting

function KlarnerRado(N)
    K = [1]
    for i in 1:N
        j = K[i]
        firstadd, secondadd = 2j + 1, 3j + 1
        if firstadd < K[end]
            pos = findlast(<(firstadd), K) + 1
            K[pos] != firstadd && insert!(K, pos, firstadd)
        elseif K[end] != firstadd
            push!(K, firstadd)
        end
        if secondadd < K[end]
            pos = findlast(<(secondadd), K) + 1
            K[pos] != secondadd && insert!(K, pos, secondadd)
        elseif K[end] != secondadd
            push!(K, secondadd)
        end
    end
    return K
end

kr1m = KlarnerRado(1_000_000)

println("First 100 Klarner-Rado numbers:")
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(kr1m[1:100]))
foreach(n -> println("The ", format(n, commas=true), "th Klarner-Rado number is ",
   format(kr1m[n], commas=true)), [1000, 10000, 100000, 1000000])
Output:
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 8,487
The 10,000th Klarner-Rado number is 157,653
The 100,000th Klarner-Rado number is 2,911,581
The 1,000,000th Klarner-Rado number is 54,381,285

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.

using Formatting

function KlamerRado(N)
    kr = falses(100 * N)
    kr[1] = true
    for i in 1:30N
        if kr[i]
            kr[2i + 1] = true
            kr[3i + 1] = true
        end
    end
    return [i for i in eachindex(kr) if kr[i]]
end

kr1m = KlamerRado(1000000)

println("First 100 Klarner-Rado numbers:")
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(kr1m[1:100]))
foreach(n -> println("The ", format(n, commas=true), "th Klarner-Rado number is ",
   format(kr1m[n], commas=true)), [1000, 10000, 100000, 1000000])
Output:

same as above version.

Ksh

Works with: ksh93
typeset -i klarner_rado i m i2=0 i3=0 m2=1 m3=1

for ((i = 0; i < 1000000; ++i))
do
    ((klarner_rado[i] = m = m2 < m3 ? m2 : m3))
    ((m2 == m && (m2 = klarner_rado[i2++] << 1 | 1)))
    ((m3 == m && (m3 = klarner_rado[i3++] * 3 + 1)))
done

print -r -- "${klarner_rado[0..99]}"
for ((i = 1000; i <= ${#klarner_rado[@]}; i *= 10))
do
    print -r -- "${klarner_rado[i - 1]}"
done
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 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
8487
157653
2911581
54381285

Nim

Translation of: 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.

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

PARI/GP

Translation of: Julia
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]);
}
Output:
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


Perl

Translation of: Raku
use v5.36;
use List::Util <max min>;

sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub table ($c, @V) { my $t = $c * (my $w = 2 + length max @V); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }

# generate terms up to 'n', as needed
sub Klarner_Rado ($n) {
    state @klarner_rado = 1;
    state @next = ( x2(), x3() );

    return @klarner_rado if +@klarner_rado >= $n; # no additional terms required

    until (@klarner_rado == $n) {
        push @klarner_rado, my $min = min @next;
        $next[0] = x2() if $next[0] == $min;
        $next[1] = x3() if $next[1] == $min;
    }

    sub x2 { state $i = 0; $klarner_rado[$i++] * 2 + 1 }
    sub x3 { state $i = 0; $klarner_rado[$i++] * 3 + 1 }

    @klarner_rado
}

say "First 100 elements of Klarner-Rado sequence:";
say table 10, Klarner_Rado(100);
say 'Terms by powers of 10:';
printf "%10s = %s\n", comma($_), comma( (Klarner_Rado $_)[$_-1] ) for map { 10**$_ } 0..6;
Output:
First 100 elements of 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

Terms by powers of 10:
         1 = 1
        10 = 21
       100 = 418
     1,000 = 8,487
    10,000 = 157,653
   100,000 = 2,911,581
 1,000,000 = 54,381,285

Phix

Translation of: ALGOL_68
with javascript_semantics
constant limit = iff(platform()=JS?10_000_000:100_000_000)
sequence kr = repeat(false,limit); kr[1] = true
integer n21 = 3, n31 = 4, p2 = 1, p3 = 1, count = 0, np10 = 1_000
for i=1 to limit do
    if i = n21 then
        if kr[p2] then
            kr[i] := true
        end if
        p2  += 1
        n21 += 2
    end if
    if i = n31 then
        if kr[p3] then
            kr[i] := true
        end if
        p3  += 1
        n31 += 3
    end if
    if kr[i] then
        count += 1
        if count <= 100 then
            printf(1,"%4d%s",{i,iff(mod(count,20)=0?"\n":"")})
        elsif count = np10 then
            printf(1,"The %,d%s Klarner-Rado number is %,d\n",{count,ord(count),i})
            np10 *= 10
        end if
    end if
end for
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
 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 8,487
The 10,000th Klarner-Rado number is 157,653
The 100,000th Klarner-Rado number is 2,911,581
The 1,000,000th Klarner-Rado number is 54,381,285

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.

much faster

Translation of: Wren

slightly faster to 1e7 than the above is to 1e6.

with javascript_semantics
function klarnerRado(integer n)
    sequence dst = repeat(0,n)
    integer i2 = 1, i3 = 1
    atom m2 = 1, m3 = 1
    for i=1 to n do
        atom m = min(m2,m3)
        dst[i] = m
        if m2 == m then
            m2 = dst[i2]*2+1
            i2 += 1
        end if
        if m3 == m then
            m3 = dst[i3]*3+1
            i3 += 1
        end if
    end for
    return dst
end function

atom t0 = time()
constant kr = klarnerRado(1e7)
printf(1,"First 100 elements of Klarner-Rado sequence:\n%s\n",
         join_by(kr[1..100],1,20,"",fmt:="%4d"))
for p=3 to 7 do
    integer lim = power(10,p)
    printf(1,"The %,d%s Klarner-Rado number is %,d\n", {lim,ord(lim),kr[lim]})
end for
?elapsed(time()-t0)
Output:
First 100 elements of 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 Klarner-Rado number is 8,487
The 10,000th Klarner-Rado number is 157,653
The 100,000th Klarner-Rado number is 2,911,581
The 1,000,000th Klarner-Rado number is 54,381,285
The 10,000,000th Klarner-Rado number is 1,031,926,801
"1.1s"

PL/M

Works with: 8080 PL/M Compiler

... under CP/M (or an emulator)


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.

100H: /* EIND ELEMENTS OF THE KLARNER-RADO SEQUENCE                         */
      /*    - IF N IS AN ELEMENT, SO ARE 2N+1 AND 3N+!, 1 IS AN ELEMENT     */

   /* CP/M SYSTEM CALL AND I/O ROUTINES                                     */
   BDOS:      PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
   PR$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C );  END;
   PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S );  END;
   PR$NL:     PROCEDURE;   CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
   PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
      DECLARE N ADDRESS;
      DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
      V = N;
      W = LAST( N$STR );
      N$STR( W ) = '$';
      N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      DO WHILE( ( V := V / 10 ) > 0 );
         N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      END;
      CALL PR$STRING( .N$STR( W ) );
   END PR$NUMBER;

   /* TASK                                                                  */

   DECLARE MAX$COUNT LITERALLY '1$000';

   DECLARE BIT ( 8 )BYTE INITIAL( 128, 1, 2, 4, 8, 16, 32, 64 );

   DECLARE ( N21, N31, P2, P3, KR$COUNT, I, I$3 ) ADDRESS;
   DECLARE KR ( 1251 )BYTE; DO I = 0 TO LAST( KR ); KR( I ) = 0; END;
   KR( 0 ) = BIT( 1 );

   KR$COUNT = 0; N21 = 3; N31 = 4; P2, P3 = 1;
   I = 0;
   DO WHILE( KR$COUNT < MAX$COUNT );
      I = I + 1;
      I$3 = SHR( I, 3 );
      IF I = N21 THEN DO;                         /* I IS 2N+1 WHERE N = P2 */
         IF ( KR( SHR( P2, 3 ) ) AND BIT( P2 AND 7 ) ) <> 0 THEN DO;
            KR( I$3 ) = KR( I$3 ) OR BIT( I AND 7 );
         END;
         P2  = P2  + 1;
         N21 = N21 + 2;
      END;
      IF I = N31 THEN DO;                         /* I IS 3N+1 WHERE N = P3 */
         IF ( KR( SHR( P3, 3 ) ) AND BIT( P3 AND 7 ) ) <> 0 THEN DO;
            KR( I$3 ) = KR( I$3 ) OR BIT( I AND 7 );
         END;
         P3  = P3  + 1;
         N31 = N31 + 3;
      END;
      IF ( KR( I$3 ) AND BIT( I AND 7 ) ) <> 0 THEN DO;
         KR$COUNT = KR$COUNT + 1;
         IF KR$COUNT <= 100 THEN DO;
            CALL PR$CHAR( ' ' );
            IF I <  10 THEN CALL PR$CHAR( ' ' );
            IF I < 100 THEN CALL PR$CHAR( ' ' );
            CALL PR$NUMBER( I );
            IF KR$COUNT MOD 20 = 0 THEN CALL PR$NL;
            END;
         ELSE IF KR$COUNT = MAX$COUNT THEN DO;
            CALL PR$STRING( .'ELEMENT $' );
            CALL PR$NUMBER( MAX$COUNT );
            CALL PR$STRING( .' IS: $' );
            CALL PR$NUMBER( I );
         END;
      END;
   END;

EOF
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
 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
ELEMENT 1000 IS: 8487

Python

def KlarnerRado(N):
    K = [1]
    for i in range(N):
        j = K[i]
        firstadd, secondadd = 2 * j + 1, 3 * j + 1
        if firstadd < K[-1]:
            for pos in range(len(K)-1, 1, -1):
                if K[pos] < firstadd < K[pos + 1]:
                    K.insert(pos + 1, firstadd)
                    break
        elif firstadd > K[-1]:
            K.append(firstadd)
        if secondadd < K[-1]:
            for pos in range(len(K)-1, 1, -1):
                if K[pos] < secondadd < K[pos + 1]:
                    K.insert(pos + 1, secondadd)
                    break
        elif secondadd > K[-1]:
            K.append(secondadd)

    return K

kr1m = KlarnerRado(100_000)

print('First 100 Klarner-Rado sequence numbers:')
for idx, v in enumerate(kr1m[:100]):
    print(f'{v: 4}', end='\n' if (idx + 1) % 20 == 0 else '')
for n in [1000, 10_000, 100_000]:
    print(f'The {n :,}th Klarner-Rado number is {kr1m[n-1] :,}')
Output:
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 8,487
The 10,000th Klarner-Rado number is 157,653
The 100,000th Klarner-Rado number is 2,911,581

faster version

from numpy import ndarray

def KlarnerRado(N):
    kr = ndarray(100 * N, dtype=bool)
    kr[1] = True
    for i in range(30 * N):
        if kr[i]:
            kr[2 * i + 1] = True
            kr[3 * i + 1] = True

    return [i for i in range(100 * N) if kr[i]]
 
kr1m = KlarnerRado(1_000_000)
 
print('First 100 Klarner-Rado sequence numbers:')
for idx, v in enumerate(kr1m[:100]):
    print(f'{v: 4}', end='\n' if (idx + 1) % 20 == 0 else '')
for n in [1000, 10_000, 100_000, 1_000_000]:
    print(f'The {n :,}th Klarner-Rado number is {kr1m[n-1] :,}')
Output:

Same as previous version.

fast unbounded generator

from itertools import islice, tee

def klarner_rado():
    def gen():
        m2 = m3 = 1
        while True:
            m = min(m2, m3)
            yield m
            if m2 == m: m2 = next(g2) << 1 | 1
            if m3 == m: m3 = next(g3) * 3 + 1
    g, g2, g3 = tee(gen(), 3)
    return g

kr = klarner_rado()
print(*islice(kr, 100))
for n in 900, 9000, 90000, 900000, 9000000:
    print(*islice(kr, n - 1, n))

Generates ten million members of the sequence in less than 7 seconds (with Python 3.11).

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 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
8487
157653
2911581
54381285
1031926801

Quackery

bsearchwith is defined at Binary search#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
Output:
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

Raku

sub Klarner-Rado ($n) {
    my @klarner-rado = 1;
    my @next = x2, x3;

    loop {
        @klarner-rado.push: my $min = @next.min;
        @next[0] = x2 if @next[0] == $min;
        @next[1] = x3 if @next[1] == $min;
        last if +@klarner-rado > $n.max;
    }

    sub x2 { state $i = 0; @klarner-rado[$i++] × 2 + 1 }
    sub x3 { state $i = 0; @klarner-rado[$i++] × 3 + 1 }

    @klarner-rado[|$n]
}

use Lingua::EN::Numbers;

put "First 100 elements of Klarner-Rado sequence:";
put Klarner-Rado(^100).batch(10)».fmt("%3g").join: "\n";
put '';
put (($_».Int».&ordinal».tc »~» ' element: ').List Z~ |(List.new: (Klarner-Rado ($_ »-» 1))».&comma)
    given $(1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6)).join: "\n";
Output:
First 100 elements of 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

First element: 1
Tenth element: 21
One hundredth element: 418
One thousandth element: 8,487
Ten thousandth element: 157,653
One hundred thousandth element: 2,911,581
One millionth element: 54,381,285

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>;
};
Output:
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

Rust

Translation of: Java
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
}
Output:
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

Scala

Translation of: Java
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
  }
}
Output:
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

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.

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;
Output:
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.

Swift

Translation of: Rust
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
}
Output:
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

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 Strict On
Option Explicit On

Imports System.IO

Module KlarnerRado

    Private Const bitsWidth As Integer = 31

    Private bitMask() As Integer = _
        New Integer(){ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 _
                     , 2048, 4096, 8192, 16384, 32768, 65536, 131072 _
                     , 262144, 524288, 1048576, 2097152, 4194304, 8388608 _
                     , 16777216, 33554432, 67108864, 134217728, 268435456 _
                     , 536870912, 1073741824 _
                     }

    Private Const maxElement As Integer = 1100000000


    Private Function BitSet(bit As Integer, v As Integer) As Boolean
        Return (v And bitMask(bit - 1)) <> 0
    End Function

    Private Function SetBit(ByVal bit As Integer, ByVal b As Integer) As Integer
        Return b Or bitMask(bit - 1)
    End Function

    Public Sub Main
        Dim  kr(maxElement \ bitsWidth) As Integer

        For i As Integer = 0 To kr.Count() - 1
            kr(i) = 0
        Next  i

        Dim krCount As Integer =  0    ' count of sequende elements
        Dim n21 As Integer = 3         ' next 2n+1 value
        Dim n31 As Integer = 4         ' next 3n+1 value
        Dim p10 As Integer = 1000      ' next power of ten to show the count/element at
        Dim iBit As Integer = 0        ' i Mod bitsWidth  - used to set the ith bit
        Dim iOverBw As Integer = 0     ' i \ bitsWidth    - used to set the ith bit
        '   p2                         ' the n for the 2n+1 value
        Dim p2Bit As Integer = 1       ' p2 Mod bitsWidth  - used to set the p2th bit
        Dim p2OverBw As Integer = 0    ' p2 \ bitsWidth    - used to set the p2th bit
        '   p3                         ' the n for the 3n+1 value
        Dim p3Bit As Integer = 1       ' p3 Mod bitsWidth  - used to set the p3th bit
        Dim p3OverBw As Integer = 0    ' p3 \ bitsWidth    - used to set the p3th bit

        kr(0) = SetBit(1, kr(0))
        Dim kri As Boolean = True
        Dim lastI As Integer = 0
        For i As Integer = 1 To  maxElement
            iBit += 1
            If iBit > bitsWidth Then
                iBit = 1
                iOverBw += 1
            End If
            If i = n21 Then            ' found the next 2n+1 value
                If BitSet(p2Bit, kr(p2OverBw)) Then
                    kri = True
                End If
                p2Bit += 1
                If p2Bit > bitsWidth Then
                    p2Bit = 1
                    p2OverBw += 1
                End If
                n21 += 2
            End If
            If i = n31 Then            ' found the next 3n+1 value
                If BitSet(p3Bit, kr(p3OverBw)) Then
                    kri = True
                End If
                p3Bit += 1
                If p3Bit > bitsWidth Then
                    p3Bit = 1
                    p3OverBw += 1
                End If
                n31 += 3
            End If
            If kri Then
                lastI = i
                kr(iOverBw) = SetBit(iBit, kr(iOverBw))
                krCount += 1
                If krCount <= 100 Then
                    Console.Out.Write(" " & i.ToString().PadLeft(3))
                    If krCount Mod 20 = 0 Then
                        Console.Out.WriteLine()
                    End If
                ElseIf krCount = p10 Then
                    Console.Out.WriteLine("Element " & p10.ToString().PadLeft(10) & " is " & i.ToString().PadLeft(10))
                    p10 *= 10
                End If
                kri = False
            End If
        Next  i
        Console.Out.WriteLine("Element " & krCount.ToString().PadLeft(10) & " is " & lastI.ToString().PadLeft(10))

    End Sub

End Module
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
 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
Element       1000 is       8487
Element      10000 is     157653
Element     100000 is    2911581
Element    1000000 is   54381285
Element   10000000 is 1031926801
Element   10543878 is 1099640002

Wren

Version 1

Library: Wren-sort
Library: Wren-fmt

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

import "./sort" for Find
import "./fmt" for Fmt

var klarnerRado = Fn.new { |limit|
    var kr = [1]
    for (i in 0...limit) {
        var n = kr[i]
        for (e in [2*n + 1, 3*n + 1]) {
            if (e > kr[-1]) {
                kr.add(e)
            } else {
                var ix = Find.nearest(kr, e)  // binary search
                if (kr[ix] != e) kr.insert(ix, e)
            }
        }
    }
    return kr[0...limit]
}

var kr = klarnerRado.call(1e6)
System.print("First 100 elements of Klarner-Rado sequence:")
Fmt.tprint("$3d ", kr[0..99], 10)
System.print()
var limits = [1, 10, 1e2, 1e3, 1e4, 1e5, 1e6]
for (limit in limits) {
    Fmt.print("The $,r element: $,d", limit, kr[limit-1])
}
Output:
First 100 elements of 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 1st element: 1
The 10th element: 21
The 100th element: 418
The 1,000th element: 8,487
The 10,000th element: 157,653
The 100,000th element: 2,911,581
The 1,000,000th element: 54,381,285

Version 2 (faster)

Translation of: ALGOL 68
Library: Wren-array

Takes around 13.8 seconds to find the millionth element compared to 48 seconds for the first version.

As in the case of some other examples, uses a bit array to save memory. However, whilst the BitArray class crams 32 bools into a 64 bit float (Wren doesn't have integers as such), it is significantly slower to index than the native List class. If the latter is used instead, the time comes down to 5.3 seconds.

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 "./array" for BitArray
import "./fmt" for Fmt

var kr = BitArray.new(1e8)
var first100 = List.filled(100, 0)
var pow10 = {}
kr[1] = true
var n21 = 3
var n31 = 4
var p2 = 1
var p3 = 1
var count = 0
var max = 1e6
var i = 1
var limit = 1
while (count < max) {
    if (i == n21) {
        if (kr[p2]) kr[i] = true
        p2 = p2 + 1
        n21 = n21 + 2
    }
    if (i == n31) {
        if (kr[p3]) kr[i] = true
        p3 = p3 + 1
        n31 = n31 + 3
    }
    if (kr[i]) {
        count = count + 1
        if (count <= 100) first100[count-1] = i
        if (count == limit) {
            pow10[count] = i
            if (limit == max) break
            limit = 10 * limit
        }
    }
    i = i + 1
}

System.print("First 100 elements of Klarner-Rado sequence:")
Fmt.tprint("$3d ", first100, 10)
System.print()
limit = 1
while (limit <= max) {
    Fmt.print("The $,r element: $,d", limit, pow10[limit])
    limit = 10 * limit
}
Output:
Same as Version 1.

Version 3 (fastest)

Translation of: C

Astonishingly fast algorithm compared to the first two versions. Finds the 10 millionth element in a little over 1 second.

import "./fmt" for Fmt

var klarnerRado = Fn.new { |n|
    var dst = List.filled(n, 0)
    var i2 = 0
    var i3 = 0
    var m = 0
    var m2 = 1
    var m3 = 1
    for (i in 0...n) {
        dst[i] = m = m2.min(m3)
        if (m2 == m) {
            m2 = dst[i2] << 1 | 1
            i2 = i2 + 1
        }
        if (m3 == m) {
            m3 = dst[i3] * 3 + 1
            i3 = i3 + 1
        }
    }
    return dst
}

var kr = klarnerRado.call(1e7)
System.print("First 100 elements of Klarner-Rado sequence:")
Fmt.tprint("$3d ", kr[0..99], 10)
System.print()
var limits = [1, 10, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7]
for (limit in limits) {
    Fmt.print("The $,r element: $,d", limit, kr[limit-1])
}
Output:

As Version 1 plus the following line.

The 10,000,000th element: 1,031,926,801

XPL0

Translation of: C

Takes about 200 miliiseconds on Pi4.

define ELEMENTS = 10_000_000;

proc Make_Klarner_Rado(Dst, N);
int  Dst, N;
int  I, I2, I3;
int  M, M2, M3;
[I2:= 0;  I3:= 0;
M2:= 1;  M3:= 1;
for I:= 0 to N-1 do
        [M:= if M2 < M3 then M2 else M3;
        Dst(I):= M;
        if M2 = M then [M2:= Dst(I2)<<1 ! 1; I2:= I2+1];
        if M3 = M then [M3:= Dst(I3)*3 + 1;  I3:= I3+1];
        ];
];

int  Klarner_Rado(ELEMENTS);
int  I;
[Make_Klarner_Rado(Klarner_Rado, ELEMENTS);
for I:= 0 to 99-1 do
        [IntOut(0, Klarner_Rado(I));  ChOut(0, ^ )];
I:= 100;
repeat  [IntOut(0, Klarner_Rado(I-1));  CrLf(0)];
        I:= I*10;
until   I > ELEMENTS;   
]
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 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
8487
157653
2911581
54381285
1031926801
Cookies help us deliver our services. By using our services, you agree to our use of cookies.