Klarner-Rado sequence

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

• OEIS:A002977 - Klarner-Rado sequence: a(1) = 1; subsequent terms are defined by the rule that if m is present so are 2m+1 and 3m+1

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 firstadd > K[pos] and firstadd < K[pos + 1]:
                   K.insert(pos + 1, firstadd)
       elif firstadd > K[-1]:
           K.append(firstadd)
       if secondadd < K[-1]:
           for pos in range(len(K)-1, 1, -1):
               if secondadd > K[pos] and secondadd < K[pos + 1]:
                   K.insert(pos + 1, secondadd)
       elif secondadd > K[-1]:
           K.append(secondadd)
           
   return K

kr1m = KlarnerRado(100_000)

print('First 100 Klarner-Rado sequence numbers:') for i, v in enumerate(kr1m[:100]):

   print(f'{v: 4}', end='\n' if (i + 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