Klarner-Rado sequence: Difference between revisions
(Added Algol 68) |
|||
Line 36: | Line 36: | ||
# - 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 = 10 000; |
INT max element = 10 000; |
||
[ 1 : max element |
[ 1 : max element ]INT kr; FOR i TO UPB kr DO kr[ i ] := 0 OD; |
||
PROC insert element = ( REF[]INT seq, INT element, REF INT last )VOID: |
PROC insert element = ( REF[]INT seq, INT element, REF INT last )VOID: |
||
IF element > seq[ last ] THEN |
IF element > seq[ last ] THEN |
Revision as of 11:40, 18 August 2022
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
Spends a lot of time shuffling the sequence element array - a linked list might be better... <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 = 10 000; [ 1 : max element ]INT kr; FOR i TO UPB kr DO kr[ i ] := 0 OD; 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 := last; WHILE seq[ pos ] > element DO pos -:= 1 OD; 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; seq[ pos + 1 ] := element; IF last < UPB seq THEN last +:= 1 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 ) )
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
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
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