Klarner-Rado sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|ALGOL 68}}: Use a binary search (as in the Wren sample) added the 100 000th element)
(→‎{{header|ALGOL 68}}: Generate the seuence in order - previous version incorrectly orderd the elements)
Line 32: Line 32:


=={{header|ALGOL 68}}==
=={{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>.
As suggested by the Wren sample, using a binary search (from the ALGOL 68 sample in the Binary search task) to determine the insertion point.
<lang algol68>BEGIN # find elements of the Klarner-Rado sequence #
<lang algol68>BEGIN # find elements of the Klarner-Rado sequence #
# - if n is an element, so are 2n + 1 and 3n + 1 #
# - if n is an element, so are 2n + 1 and 3n + 1 #
INT max element = 100 000;
INT max element = 100 000 000;
[ 1 : max element ]INT kr; FOR i TO UPB kr DO kr[ i ] := 0 OD;
[ 0 : max element ]BOOL kr; FOR i FROM LWB kr TO UPB kr DO kr[ i ] := FALSE OD;
⚫
INT n21 := 3;
# modified Iterative binary search routine from the binary search task #
⚫
INT n31 := 4;
PROC iterative binary search = ([]INT hay stack, INT needle, INT last)INT:
⚫
INT p2 := 1;
(
INT low := LWB hay stack, high := last;
INT p3 := 1;
WHILE low < high DO
kr[ 1 ] := TRUE;
INT mid := (low+high) OVER 2;
INT kr count := 0;
INT max count = 1 000 000;
IF hay stack[mid] > needle THEN high := mid-1
FOR i WHILE kr count < max count DO
⚫
ELIF hay stack[mid] < needle THEN low := mid+1
ELSE low:= mid; high := low - 1
IF i = n21 THEN
⚫
IF kr[ p2 ] THEN
⚫
kr[ i ] := TRUE
⚫
FI;
⚫
p2 +:= 1;
⚫
n21 +:= 2
⚫
FI;
⚫
IF i = n31 THEN
⚫
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;
FI
low
OD
⚫
);
# end code from the binary search task #
# inserts element into seq, updating last as appropriate #
PROC insert element = ( REF[]INT seq, INT element, REF INT last )VOID:
⚫
IF element > seq[ last ] THEN
# have the new highest element #
⚫
IF last < UPB seq THEN
⚫
seq[ last +:= 1 ] := element
⚫
FI
⚫
ELIF element < seq[ last ] THEN
# need to insert the number at an earlier point #
# find the position to insert at #
INT pos = iterative binary search( seq, element, last );
⚫
IF seq[ pos ] /= element THEN
# the element isn't currently present - insert it #
FOR move FROM IF last = UPB seq THEN last - 1 ELSE last FI BY -1 TO pos + 1 DO
seq[ move + 1 ] := seq[ move ]
⚫
OD;
⚫
IF pos < UPB seq THEN
⚫
seq[ pos + 1 ] := element;
IF last < UPB seq THEN last +:= 1 FI
⚫
FI
⚫
FI
⚫
FI # insert element # ;
⚫
INT last := 1;
⚫
kr[ 1 ] := 1;
FOR i TO UPB kr DO
insert element( kr, ( 2 * kr[ i ] ) + 1, last );
insert element( kr, ( 3 * kr[ i ] ) + 1, last )
OD;
FOR i TO 100 DO
⚫
print( ( " ", whole( kr[ i ], -3 ) ) );
⚫
IF i MOD 20 = 0 THEN print( ( newline ) ) FI
OD;
⚫
print( ( "The thousandth element is ", whole( kr[ 1 000 ], -8 ), newline ) );
⚫
print( ( "The ten thousandth element is ", whole( kr[ 10 000 ], -8 ), newline ) );
⚫
print( ( "The 100-thousandth element is ", whole( kr[ 100 000 ], -8 ), newline ) )
END</lang>
END</lang>
{{out}}
{{out}}
Line 96: Line 85:
The thousandth element is 8487
The thousandth element is 8487
The ten thousandth element is 157653
The ten thousandth element is 157653
The 100-thousandth element is 2908413
The 100-thousandth element is 2911581
The millionth element is 54381285
</pre>
</pre>


Revision as of 15:21, 18 August 2022

Klarner-Rado sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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


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 1024M. <lang algol68>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;
   INT n31      := 4;
   INT p2       := 1;
   INT p3       := 1;
   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
           IF kr[ p2 ] THEN
               kr[ i ] := TRUE
           FI;
           p2  +:= 1;
           n21 +:= 2
       FI;
       IF i = n31 THEN
           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</lang>

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

Julia

<lang 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])

</lang>

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

Python

<lang 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] :,}')

</lang>

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

Raku

<lang perl6>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";</lang>
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

Wren

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. <lang ecmascript>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])

} </lang>

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
Retrieved from "https://rosettacode.org/wiki/Klarner-Rado_sequence?oldid=322137"