Inventory sequence
To build the inventory sequence, first take inventory of what numbers are already in the sequence, then, starting with 0 add the count of each number in turn to the end of the sequence. When you reach a number that has a count of 0, stop, add the 0 to the end of the sequence, and then restart the inventory from 0.
You are encouraged to solve this task according to the task description, using any language you may know.
- E.G.
- Start taking inventory; how many 0s are there? 0. Add a 0 to the end of the sequence and restart the inventory. (0)
- How many 0s are there? 1. Add a 1 to the end of the sequence. How many 1s are there? 1. Add a 1 to the end of the sequence. How many 2s are there? 0. Add a 0 to the end of the sequence and restart the inventory. (0 1 1 0)
- and so on.
- Task
- Find and display the first 100 elements of the sequence.
- Find and display the position and value of the first element greater than or equal to 1000.
- Stretch
- Find and display the position and value of the first element greater than or equal to 2000, 3000 ... 10,000.
- Plot a graph of the first 10,000 elements of the sequence.
- See also
PRINT equ 9 ; CP/M call to print a string
org 100h
lxi h,tally ; Zero out the array
lxi d,11000 * 2 ; Two bytes each
mvi b,0
zero: mov m,b
inx h
dcx d
mov a,d
ora e
jnz zero
restrt: lxi b,0 ; BC = current number
takinv: mov d,b ; Look up count of current number
mov e,c
call talidx
mov e,m ; DE = current element
inx h
mov d,m
lxi h,tabct ; Any items left to print for the table?
mov a,m
ora a
jz cktrsh
dcr m ; In any case there's now one less
call atoi
lxi h,numbuf ; Print the current number
call prstr
lxi h,tabcol ; Done with the row yet?
dcr m
jnz cktrsh
mvi m,10 ; Yes, reset counter and print a newline
lxi h,nl
call prstr
cktrsh: lhld trshld ; Has the threshold been reached?
call cdehl
jc increm
xchg ; Yes, fill in the numbers
call atoi ; Threshold (from HL)
xchg
push d ; And add 1000 to it while we've got it here
lxi d,1000
dad d
pop d
shld trshld
lxi h,trsout
call numat
call atoi ; Our current element
lxi h,numout
call numat
lxi h,trsfmt ; Print the element and its index
call prstr
increm: call talidx ; HL = address of count of element
call inxm ; Increment count
call incidx ; Increment index
inx b ; Increment the search number
mov a,d ; Reached zero?
ora e
jnz takinv ; If not, keep going
lhld trshld ; Once we've done enough, stop
lxi d,-10001
dad d
jnc restrt
ret
tabcol: db 10 ; Column counter for table
tabct: db 100 ; First 100 items are to be printed
trshld: dw 1000 ; Initial threshold
; 16-bit compare DE and HL
cdehl: mov a,d
cmp h
rnz
mov a,e
cmp l
ret
; 16-bit increment of [HL]
inxm: inr m
rnz
inx h
inr m
ret
; Get HL = &tally[DE]
talidx: push d
xchg
dad h
lxi d,tally
dad d
pop d
ret
; print string at HL
prstr: push h
push d
push b
xchg
mvi c,PRINT
call 5
pop b
pop d
pop h
ret
; copy number buffer to HL
numat: push d
push b
lxi d,numbuf
mvi b,5
numcpy: ldax d
mov m,a
inx d
inx h
dcr b
jnz numcpy
pop b
pop d
ret
; set numbuf to DE as decimal number
atoi: push h
push d
push b
mvi a,5 ; Space out the buffer
lxi h,nbufe ; End of number buffer
push h ; Keep it on the stack
aspc: dcx h
mvi m,' '
dcr a
jnz aspc
lxi b,-10
adgt: xchg ; Number in HL
lxi d,-1
adgtlp: inx d ; Extract digit
dad b
jc adgtlp
mvi a,'0'+10 ; ASCII digit in A
add l
pop h ; Get buffer pointer back
dcx h
mov m,a
push h
mov a,d ; Any digits left?
ora e
jnz adgt ; If so, next digits
pop b ; Otherwise we're done
pop b
pop d
pop h
ret
numbuf: db '*****'
nbufe: db '$'
; Format to print first number above threshold, ends in index
trsfmt: db 'First > '
trsout: db '*****: '
numout: db '***** at '
; Index counter, kept as ASCII decimal so we don't need 32-bit math
idx: db ' 0'
nl: db 13,10,'$' ; Newline string which also ends index
; Increment index
incidx: lxi h,nl-1
inclp: mov a,m
cpi ' ' ; Space should be set to 1
jz one
inr m
cpi '9'
rnz
mvi m,'0'
dcx h
jmp inclp
one: mvi m,'1'
ret
tally equ $ ; Array stored at the end of the program
- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
cpu 8086
org 100h
section .text
xor ax,ax ; Zero out the array
mov di,tally
mov cx,11000
rep stosw
mov bp,1000 ; BP = next threshold
mov cx,640Ah ; CH = table counter, CL = column counter
restrt: xor bx,bx ; BX = current number
takinv: shl bx,1
mov si,[tally+bx] ; SI = current element
shr bx,1
test ch,ch ; Any items left to print for the table?
jz cktrsh ; If not check threshold
dec ch
mov di,format.cell ; Print cell
mov dx,di
mov ax,si
call atoi
mov ah,9
int 21h
dec cl ; Row done?
jnz cktrsh
mov dx,format.nl
mov cl,10
int 21h
cktrsh: cmp si,bp ; Has the threshold been reached?
jna increm
mov ax,bp ; Yes, fill in the numbers
mov di,format.trs
call atoi
mov ax,si
mov di,format.num
call atoi
mov dx,format ; Print the string
mov ah,9
int 21h
add bp,1000 ; Next threshold
increm: mov di,si ; Increment count of current element
shl di,1
inc word [tally+di]
call incidx ; Increment current index
inc bx ; Increment search number
test si,si ; Reached zero?
jnz takinv ; If not, keep going
cmp bp,10000 ; Last threshold reached?
jna restrt ; If not, start over
int 20h ; Otherwise we're done
; Convert AX to decimal and store at DI (must be 5-char buffer)
atoi: push ax
push bx
push cx
push dx
mov cx,5
add di,cx
mov bx,10
.digit: xor dx,dx
div bx
add dl,'0'
dec di
dec cx
mov [di],dl
test ax,ax
jnz .digit
jcxz .out
mov al,' '
dec di
std
rep stosb
cld
.out: pop dx
pop cx
pop bx
pop ax
ret
; Increment index as ASCII in place
incidx: mov di,format.nl-1
.loop: cmp byte [di],' ' ; Space -> 1
je .one
inc byte [di]
cmp byte [di],'9'
ja .carry
ret
.carry: mov byte [di],'0'
dec di
jmp .loop
.one: mov byte [di],'1'
ret
; Format to print first number above threshold
format: db "First > "
.trs: db "*****: "
.num: db "***** at "
.idx: db " 0"
.nl: db 13,10,'$'
.cell: db "*****$" ; cell placeholder
section .bss
align 2
tally: resw 11000
- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
Calculates the sequence elements without storing them, though it does store how many times each number appears.
BEGIN # find elements of the inventory sequence #
INT next to show := 1 000; # next value to show first element > #
INT max to show = 10 000; # last value to show first element > #
INT max number = max to show + 1 000; # max. element value to consider #
[ 0 : max number ]INT occurs; # number of times each number occurs #
FOR i FROM LWB occurs TO UPB occurs DO occurs[ i ] := 0 OD;
INT seq pos := 0; # current end of the sequence #
WHILE next to show <= max to show DO
INT element := 1; # any non-zero value will do #
FOR n FROM 0 WHILE next to show <= max to show AND element /= 0 DO
element := occurs[ n ];
seq pos +:= 1;
IF seq pos <= 100 THEN
print( ( " ", whole( element, -4 ) ) );
IF seq pos MOD 10 = 0 THEN print( ( newline ) ) FI
ELIF element > next to show THEN
print( ( "Element ", whole( seq pos, -8 )
, " (", whole( element, -8 )
, ") is first > ", whole( next to show, -6 )
, newline
)
);
next to show +:= 1 000
FI;
IF element < max number THEN
occurs[ element ] +:= 1
FI
OD
OD
END- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
Element 24256 ( 1001) is first > 1000
Element 43302 ( 2009) is first > 2000
Element 61709 ( 3001) is first > 3000
Element 81457 ( 4003) is first > 4000
Element 98705 ( 5021) is first > 5000
Element 121343 ( 6009) is first > 6000
Element 151757 ( 7035) is first > 7000
Element 168805 ( 8036) is first > 8000
Element 184429 ( 9014) is first > 9000
Element 201789 ( 10007) is first > 10000
begin % find elements of the inventory sequence %
integer maxToShow % last value to show first element > %
, maxNumber % max. element value to consider %
;
maxToShow := 10000;
maxNumber := maxToShow + 1000;
begin
integer array occurs( 0 :: maxNumber ); % times each number occurs %
integer nextToShow, seqPos, element, n;
for i := 0 until maxNumber do occurs( i ) := 0;
seqPos := 0; % current end of the sequence %
nextToShow := 1000; % first value to show first element > %
while nextToShow <= maxToShow do begin
element := 1; % any non-zero value will do %
n := -1;
while nextToShow <= maxToShow and element not = 0 do begin
n := n + 1;
element := occurs( n );
seqPos := seqPos + 1;
if seqPos <= 100 then begin
writeon( i_w := 4, s_w := 0, " ", element );
if seqPos rem 10 = 0 then write()
end else if element > nextToShow then begin
write( i_w := 8, s_w := 0
, "Element ", seqPos, " (", element, ") is first > ", i_w := 6, nextToShow
);
nextToShow := nextToShow + 1000
end;
if element < maxNumber then occurs( element ) := occurs( element ) + 1
end
end
end
end.- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
Element 24256 ( 1001) is first > 1000
Element 43302 ( 2009) is first > 2000
Element 61709 ( 3001) is first > 3000
Element 81457 ( 4003) is first > 4000
Element 98705 ( 5021) is first > 5000
Element 121343 ( 6009) is first > 6000
Element 151757 ( 7035) is first > 7000
Element 168805 ( 8036) is first > 8000
Element 184429 ( 9014) is first > 9000
Element 201789 ( 10007) is first > 10000
invseq←{
t←1000×⍳10
seq←0{
(⍺+1)∇⍣(n>0)⊢⍵,n←+/⍺=⍵
}⍣{
⍵∨.>⊃⌽t
}⊢⍬
⎕←'First 100 elements:'
⎕←10 10⍴seq
loc←{⊃⍸seq>⍵}¨t
⎕←'⊂First > ⊃,I5,⊂: ⊃,I5,⊂ at ⊃,I6'⎕FMT t,seq[loc],[1.5]loc
}
- Output:
Note that APL arrays are 1-indexed by default.
First 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First > 1000: 1001 at 24256 First > 2000: 2009 at 43302 First > 3000: 3001 at 61709 First > 4000: 4003 at 81457 First > 5000: 5021 at 98705 First > 6000: 6009 at 121343 First > 7000: 7035 at 151757 First > 8000: 8036 at 168805 First > 9000: 9014 at 184429 First > 10000: 10007 at 201789
10 DEFINT A-Z
20 DIM I(11000)
30 T=1000
40 N=0
50 E=I(N)
60 IF S#<100 THEN PRINT USING "####";E;
70 IF E>T THEN PRINT USING "First > #####: ##### at ######";T;E;S#: T=T+1000
80 S#=S#+1
90 I(E)=I(E)+1
100 N=N+1
110 IF E>0 THEN 50
120 IF T<=10000 THEN 40
- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First > 1000: 1001 at 24255 First > 2000: 2009 at 43301 First > 3000: 3001 at 61708 First > 4000: 4003 at 81456 First > 5000: 5021 at 98704 First > 6000: 6009 at 121342 First > 7000: 7035 at 151756 First > 8000: 8036 at 168804 First > 9000: 9014 at 184428 First > 10000: 10007 at 201788
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
std::vector<uint32_t> inventory_sequence(uint32_t max_term) {
uint32_t term = 0;
std::vector<uint32_t> result = { term };
std::map<uint32_t, uint32_t> inventory = { { term, 1 } };
while ( result.back() < max_term ) {
inventory.insert({ term, 0 });
const uint32_t count = inventory[term];
term = ( count == 0 ) ? 0 : term + 1;
if ( inventory.find(count) == inventory.end() ) {
inventory.emplace(count, 1);
} else {
inventory[count]++;
}
result.emplace_back(count);
}
return result;
}
int main() {
std::vector<uint32_t> sequence = inventory_sequence(10'000);
uint32_t thousands = 1'000;
std::cout << "The first 100 numbers of the inventory sequence:" << "\n";
for ( uint64_t i = 0; i < sequence.size(); ++i ) {
const uint32_t number = sequence[i];
if ( i < 100 ) {
std::cout << std::setw(2) << number << ( i % 20 == 19 ? "\n" : " " );
} else if ( i == 100 ) {
std::cout << "\n";
} else if ( number >= thousands ) {
std::cout << "The first element ≥ " << std::setw(5) << thousands << " is "
<< std::setw(5) << number << " which occurs at index " << std::setw(6) << i << "\n";
thousands += 1'000;
}
}
}
- Output:
The first 100 numbers of the inventory sequence: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 The first element ≥ 1000 is 1001 which occurs at index 24255 The first element ≥ 2000 is 2009 which occurs at index 43301 The first element ≥ 3000 is 3001 which occurs at index 61708 The first element ≥ 4000 is 4003 which occurs at index 81456 The first element ≥ 5000 is 5021 which occurs at index 98704 The first element ≥ 6000 is 6009 which occurs at index 121342 The first element ≥ 7000 is 7035 which occurs at index 151756 The first element ≥ 8000 is 8036 which occurs at index 168804 The first element ≥ 9000 is 9014 which occurs at index 184428 The first element ≥ 10000 is 10007 which occurs at index 201788
grow = proc (arr: array[int], n: int)
while array[int]$high(arr) < n do
array[int]$addh(arr, 0)
end
end grow
invseq = iter () yields (int)
tally: array[int] := array[int]$[0:0]
num: int := 0
while true do
grow(tally, num)
el: int := tally[num]
yield(el)
grow(tally, el)
tally[el] := tally[el] + 1
if el=0
then num := 0
else num := num+1
end
end
end invseq
start_up = proc ()
po: stream := stream$primary_output()
index: int := 0
threshold: int := 1000
for n: int in invseq() do
if index<100 then
stream$putright(po, int$unparse(n), 5)
if index // 10 = 9 then stream$putl(po, "") end
end
if n > threshold then
stream$puts(po, "First > ")
stream$putright(po, int$unparse(threshold), 5)
stream$puts(po, ": ")
stream$putright(po, int$unparse(n), 5)
stream$puts(po, " at ")
stream$putright(po, int$unparse(index), 6)
stream$putl(po, "")
threshold := threshold + 1000
end
index := index + 1
if threshold > 10000 then break end
end
end start_up- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
include "cowgol.coh";
sub len(num: uint32): (length: uint8) is
length := 1;
while num>=10 loop
length := length + 1;
num := num / 10;
end loop;
end sub;
sub printtab32(num: uint32, size: uint8) is
var spaces := size - len(num);
while spaces > 0 loop
print_char(' ');
spaces := spaces - 1;
end loop;
print_i32(num);
end sub;
sub printtab16(num: uint16, size: uint8) is
printtab32(num as uint32, size);
end sub;
var tally: uint16[11000];
var threshold: uint16 := 1000;
var index: uint32 := 0;
MemZero(&tally[0] as [uint8], @bytesof tally);
while threshold <= 10000 loop
var number: uint16 := 0;
loop
var element := tally[number];
if index < 100 then
printtab16(element, 5);
if index % 10 == 9 then
print_nl();
end if;
end if;
if element > threshold then
print("First > ");
printtab16(threshold, 5);
print(": ");
printtab16(element, 5);
print(" at ");
printtab32(index, 6);
print_nl();
threshold := threshold + 1000;
end if;
index := index + 1;
number := number + 1;
tally[element] := tally[element] + 1;
if element == 0 then
break;
end if;
end loop;
end loop;- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
def inventory
i = 0
counts = Hash(Int32, Int32).new(0)
Iterator.of {
count = counts[i]
i = count.zero? ? 0 : i + 1
counts[count] += 1
count
}
end
puts "Inventory sequence, first 100 elements:",
inventory.first(100)
.map {|n| " %2d" % n }.each_slice(20).map(&.join).join("\n")
puts
limits = (1000..10_000).step(1000).each
limit = limits.next
inventory.with_index do |n, i|
break if limit.is_a? Iterator::Stop
if n >= limit
puts "First element >= %5d is %5d at index %d" % {limit, n, i}
limit = limits.next
end
end
- Output:
Inventory sequence, first 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000 is 1001 at index 24255 First element >= 2000 is 2009 at index 43301 First element >= 3000 is 3001 at index 61708 First element >= 4000 is 4003 at index 81456 First element >= 5000 is 5021 at index 98704 First element >= 6000 is 6009 at index 121342 First element >= 7000 is 7035 at index 151756 First element >= 8000 is 8036 at index 168804 First element >= 9000 is 9014 at index 184428 First element >= 10000 is 10007 at index 201788
proc main() void:
[11000]word tally;
word threshold, number, element;
ulong index;
for number from 0 upto 10999 do tally[number] := 0 od;
index := 0;
threshold := 1000;
while threshold <= 10000 do
number := 0;
while
element := tally[number];
if index < 100 then
write(element:5);
if index % 10 = 9 then writeln() fi
fi;
if element > threshold then
writeln("First > ",threshold:5,": ",element:5," at ",index:6);
threshold := threshold + 1000
fi;
index := index + 1;
number := number + 1;
tally[element] := tally[element] + 1;
element /= 0
do od
od
corp- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
repeat
i += 1
cnts[] &= 0
n = cnts[i]
cnts[n + 1] += 1
if len cnts[] <= 100 : write n & " "
if n = 0 : i = 0
until n > 1000
.
print ""
print len cnts[] - 1 & " " & n- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 24255 1001
Dim As Integer max = 10000
Dim As Integer inv()
Dim As Integer counts(max + 100)
counts(0) = 1
Dim As Integer lower = 100
Dim As Integer upper = 1000
Dim As Boolean done = False
Dim As Integer ix = 0
While Not done
Dim As Integer i = 0, c = 0
Do
Dim As Integer j = counts(i)
If Ubound(inv) < max Then
Redim Preserve inv(ix+1)
inv(ix+1) = j
End If
counts(j) += 1
ix += 1
If Ubound(inv) >= lower Then
Print "Inventory sequence, first 100 elements:"
For c = 0 To 99
Print Using "###"; inv(c);
If (c+1) Mod 20 = 0 Then Print
Next
lower = max + 1
End If
If j = 0 Then Exit Do
If j >= upper Then
Print Using !"\nFirst element >= ##,### is ##,### at index ###,###"; upper; j; ix;
If j >= max Then done = True: Exit Do
upper += 1000
End If
i += 1
Loop
Wend
Sleep
Fast version is
import Text.Printf
import qualified Data.IntMap.Lazy as IntMap
-- Naïve version that computes series like in the instructions.
-- Programm takes > 15 minutes to complete this way.
inventory_slow :: [Int]
inventory_slow = go []
where
go start =
let cur = countFreqs start
in cur ++ go (start ++ cur)
-- Counts the fequencies of each number in a list.
-- Returns result as a list where the first entry is frequency of zeros,
-- the second entry the frequencies of ones, and so on.
-- Stops on the first number that has a frequency of zero, that zero is appened to the list.
countFreqs :: [Int] -> [Int]
countFreqs ints = go 0 ints
where
go num list =
let cur = countNum num list
in case cur of
0 -> [0]
_ -> cur : go (succ num) (list ++ [cur])
countNum num list = length $ filter (== num) list
-- Fast version using hash table.
-- Programm completes in few seconds.
inventory :: [Int]
inventory = go IntMap.empty 0
where
-- im: map from numbers to frequencies
-- n: current number to check
go :: IntMap.IntMap Int -> Int -> [Int]
go im n =
let c = IntMap.findWithDefault 0 n im
next_im = IntMap.insertWith (+) c 1 im
next_n = if c == 0 then 0 else n + 1
in c : go next_im next_n
main = printFirst100 >> printPosGT1000
where printFirst100 = goByLine inventory 0
goByLine next counter = if counter >= 100 then return ()
else (putStr . unwords . map (printf "%4d") . take 10) next
>> putStr "\n" >> goByLine (drop 10 next) (counter + 10)
printPosGT1000 = goEach1000 inventory 1000 0
goEach1000 cont limit counter = let (cur, next) = span (<limit) cont
counter' = counter + length cur
val = head next
newLimit = limit + 1000
in (printf "First element ≥ %d : %d index %d\n" limit val counter' :: IO ())
>> if newLimit > 10000 then return () else goEach1000 next newLimit counter'
- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element ≥ 1000 : 1001 index 24255 First element ≥ 2000 : 2009 index 43301 First element ≥ 3000 : 3001 index 61708 First element ≥ 4000 : 4003 index 81456 First element ≥ 5000 : 5021 index 98704 First element ≥ 6000 : 6009 index 121342 First element ≥ 7000 : 7035 index 151756 First element ≥ 8000 : 8036 index 168804 First element ≥ 9000 : 9014 index 184428 First element ≥ 10000 : 10007 index 201788
nextinv=: ((*@] * 1+{.@[), }.@[ , ]) +/@({. = }.)
10 10$}.nextinv^:100]0 NB. first 100 elements of inventory sequence
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
({:,_2+#)nextinv^:(1000>{:)^:_]0 NB. first value of at least 1000 and its index
1001 24255
The inventory sequence has a "hidden value" which is the number that we are searching for, and counting. So, here, we include it as the first element of the representation of an inventory subsequence. And nextinv calculates both the next "hidden value" as well as the corresponding subsequence which incorporates a count of how many times the current "hidden value" appeared.
For the task, we iterate inductively from the initial state (either a 100 times or until we find a value which is greater than 1000).
It would be more efficient to maintain counts of each integer so far encountered, but that efficiency is not necessary for this task (and would require more code).
That said, here's a faster implementation:
invseq=: {{
cnt=. 0, seq=. i. nxt=. 0
while. -. u seq do.
k=. nxt{cnt
nxt=. (*k)*nxt+1
cnt=. (1+k{cnt) k} cnt=. cnt {.~ (2+k)>.#cnt
seq=. seq, k
end.
}}
stretch=: }.nextinv^:(10000>{:)^:_]0 NB. or
stretch=: (1e4<:{:) invseq NB. equivalent, faster approach
(,~ {&stretch) {.I.2000<stretch NB. first value greater than 2000 and its index
2009 43301
(,~ {&stretch) {.I.3000<stretch
3001 61708
(,~ {&stretch) {.I.4000<stretch
4003 81456
(,~ {&stretch) {.I.5000<stretch
5021 98704
(,~ {&stretch) {.I.6000<stretch
6009 121342
(,~ {&stretch) {.I.7000<stretch
7035 151756
(,~ {&stretch) {.I.8000<stretch
8036 168804
(,~ {&stretch) {.I.9000<stretch
9014 184428
(,~ {&stretch) {.I.10000<stretch
10007 201788
require'plot'
plot 1e4{.stretch
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public final class InventorySequence {
public static void main(String[] args) {
List<Integer> inventorySequence = inventorySequence(10_000);
int thousands = 1_000;
System.out.println("The first 100 numbers of the inventory sequence:");
for ( int i = 0; i < inventorySequence.size(); i++ ) {
final int number = inventorySequence.get(i);
if ( i < 100 ) {
System.out.print(String.format("%2d%s", number, ( i % 20 == 19 ? "\n" : " " )));
} else if ( i == 100 ) {
System.out.println();
} else if ( number >= thousands ) {
System.out.println(String.format("%s%5d%s%5d%s%6d",
"The first element ≥ ", thousands, " is ", number, " which occurs at index ", i));
thousands += 1_000;
}
}
}
private static List<Integer> inventorySequence(int maxTerm) {
int term = 0;
List<Integer> result = new ArrayList<Integer>(List.of(term ));
Map<Integer, Integer> inventory = new HashMap<Integer, Integer>(Map.of( 0, 1 ));
while ( result.getLast() < maxTerm ) {
final int count = inventory.computeIfAbsent(term, n -> 0 );
term = ( count == 0 ) ? 0 : term + 1;
inventory.merge(count, 1, Integer::sum);
result.addLast(count);
}
return result;
}
}
- Output:
The first 100 numbers of the inventory sequence: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 The first element ≥ 1000 is 1001 which occurs at index 24255 The first element ≥ 2000 is 2009 which occurs at index 43301 The first element ≥ 3000 is 3001 which occurs at index 61708 The first element ≥ 4000 is 4003 which occurs at index 81456 The first element ≥ 5000 is 5021 which occurs at index 98704 The first element ≥ 6000 is 6009 which occurs at index 121342 The first element ≥ 7000 is 7035 which occurs at index 151756 The first element ≥ 8000 is 8036 which occurs at index 168804 The first element ≥ 9000 is 9014 which occurs at index 184428 The first element ≥ 10000 is 10007 which occurs at index 201788
function inventorySequence(maxTerm) {
let term = 0;
const result = [term];
const inventory = { 0: 1 };
while (result[result.length - 1] < maxTerm) {
const count = inventory[term] ?? 0;
term = (count === 0) ? 0 : term + 1;
inventory[count] = (inventory[count] || 0) + 1;
result.push(count);
}
return result;
}
function main() {
const inventorySequenceList = inventorySequence(10_000);
let thousands = 1_000;
console.log("The first 100 numbers of the inventory sequence:");
for (let i = 0; i < inventorySequenceList.length; i++) {
const number = inventorySequenceList[i];
if (i < 100) {
// Mimics String.format("%2d", number) with padding
const formattedNum = number.toString().padStart(2, ' ');
process.stdout.write(formattedNum + (i % 20 === 19 ? "\n" : " "));
} else if (i === 100) {
console.log();
} else if (number >= thousands) {
console.log(`The first element ≥ ${thousands} is ${number} which occurs at index ${i}`);
thousands += 1_000;
}
}
}
main();
- Output:
The first 100 numbers of the inventory sequence: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 The first element ≥ 1000 is 1001 which occurs at index 24255 The first element ≥ 2000 is 2009 which occurs at index 43301 The first element ≥ 3000 is 3001 which occurs at index 61708 The first element ≥ 4000 is 4003 which occurs at index 81456 The first element ≥ 5000 is 5021 which occurs at index 98704 The first element ≥ 6000 is 6009 which occurs at index 121342 The first element ≥ 7000 is 7035 which occurs at index 151756 The first element ≥ 8000 is 8036 which occurs at index 168804 The first element ≥ 9000 is 9014 which occurs at index 184428 The first element ≥ 10000 is 10007 which occurs at index 201788
Works with both jq and gojq, the C and Go implementations of jq
... but note that gojq takes about 5 times longer (and requires much more memory) to complete the task.
With minor modifications, the program below also works quite snappily with jaq, the Rust implementation of jq.
The definition of `_nwise` can be omitted if using the C implementation of jq.
def _nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
# Emit the inventory sequence ad infinitum
def inventory_sequence:
{num: 0,
emit: 0,
inventory: {} }
| foreach range(0; infinite) as $n (.;
.emit = (.inventory[.num|tostring] // 0)
| if .emit == 0 then .num = 0 else .num += 1 end
| .inventory[.emit|tostring] += 1 )
| .emit ;
# Report on the progress of an arbitrary sequence, indefinitely
# Emit [.next, $x, .n]
def probe(s; $gap):
foreach s as $x ({n: 0, next: $gap};
.n += 1
| if $x >= .next then .emit = {next, $x, n} | .next += $gap
else .emit = null
end)
| select(.emit).emit;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def task($n):
[limit($n; inventory_sequence)] | _nwise(10) | map(lpad(3)) | join(" ");
task(100),
"",
(limit(10; probe(inventory_sequence; 1000))
| "First element >= \(.next) is \(.x) at index \(.n - 1)")- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000 is 1001 at index 24255 First element >= 2000 is 2009 at index 43301 First element >= 3000 is 3001 at index 61708 First element >= 4000 is 4003 at index 81456 First element >= 5000 is 5021 at index 98704 First element >= 6000 is 6009 at index 121342 First element >= 7000 is 7035 at index 151756 First element >= 8000 is 8036 at index 168804 First element >= 9000 is 9014 at index 184428 First element >= 10000 is 10007 at index 201788
""" rosettacode.org/wiki/Inventory_sequence """
using Printf
using Counters
using Plots
struct InventorySequence
inventory::Counter{Int}
InventorySequence() = new(counter([0]))
end
function Base.iterate(i::InventorySequence, num = 0)
nextval = i.inventory[num]
num = nextval == 0 ? 0 : num + 1
i.inventory[nextval] += 1
return nextval, num
end
const thresholds = [1000 * j for j in 1:10]
const toplot = Int[]
for (i, n) in enumerate(InventorySequence())
if i <= 100
print(rpad(n, 4), i % 20 == 0 ? "\n" : "")
elseif n >= thresholds[begin]
@printf("First element >= %d5: %d5 in position %d.\n", popfirst!(thresholds), n, i)
length(thresholds) == 0 && break
end
length(toplot) < 10000 && push!(toplot, n)
end
plot(toplot)
- Output:
Similar to Python output.
.svg.svg){kind=link}
FORM 100, 48 ' SCREEN RESOLUTION 100 CHARACTERS x 48 LINES
MODULE Inventory_sequence{
10 LONG S
20 STRING F="First > {0::-5}: {1::-5} at {2::-6}", A="{0::-5}"
30 INTEGER N, E, T=1000
40 DIM I(11000) AS INTEGER
50 N=0
60 E=I(N)
70 IF S<100 THEN ? FORMAT$("{0::-5}", E), ELSE.IF E>T THEN ?: ? FORMAT$(F,T,E,S);:T+=1000
80 S++:I(E)++:N++
90 IF E>0 THEN 60
100 IF T<=10000 THEN 50
110 PRINT
}
PROFILER
Inventory_sequence
PRINT TIMECOUNT
MODULE Inventory_sequence{
LONG S
STRING F="First > {0::-5}: {1::-5} at {2::-6}", A="{0::-5}"
INTEGER N, E, T=1000
DIM I(11000) AS INTEGER
DO N=0
DO E=I(N)
IF S<100 THEN ? FORMAT$(A, E), ELSE.IF E>T THEN ?: ? FORMAT$(F,T,E,S);:T+=1000
S++:I(E)++:N++
WHEN E>0
WHEN T<=10000
PRINT
}
PROFILER
Inventory_sequence
PRINT TIMECOUNT ' 9% FASTER
- Output:
Similar to Assembly output.
NORMAL MODE IS INTEGER
DIMENSION TALLY(11000)
DIMENSION ROW(10)
VECTOR VALUES ROWF = $10(I5)*$
VECTOR VALUES TRSHF = $8HFIRST > ,I5,2H: ,I5,S1,3HAT ,I6*$
RWIX = 0
INTERNAL FUNCTION(X)
ENTRY TO TBLOUT.
ROW(RWIX) = X
RWIX = RWIX + 1
WHENEVER RWIX.L.10, FUNCTION RETURN 0
PRINT FORMAT ROWF,ROW(0),ROW(1),ROW(2),ROW(3),ROW(4),
0 ROW(5),ROW(6),ROW(7),ROW(8),ROW(9)
RWIX = 0
END OF FUNCTION
TRSHLD = 1000
IDX = 0
RESTRT NUM = 0
TAKINV ELEM = TALLY(NUM)
WHENEVER IDX.L.100, TBLOUT.(ELEM)
WHENEVER ELEM.G.TRSHLD
PRINT FORMAT TRSHF,TRSHLD,ELEM,IDX
TRSHLD = TRSHLD + 1000
END OF CONDITIONAL
IDX = IDX+1
NUM = NUM+1
TALLY(ELEM) = TALLY(ELEM)+1
WHENEVER ELEM.G.0, TRANSFER TO TAKINV
WHENEVER TRSHLD.LE.10000, TRANSFER TO RESTRT
END OF PROGRAM- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
FIRST > 1000: 1001 AT 24255
FIRST > 2000: 2009 AT 43301
FIRST > 3000: 3001 AT 61708
FIRST > 4000: 4003 AT 81456
FIRST > 5000: 5021 AT 98704
FIRST > 6000: 6009 AT 121342
FIRST > 7000: 7035 AT 151756
FIRST > 8000: 8036 AT 168804
FIRST > 9000: 9014 AT 184428
FIRST > 10000: 10007 AT 201788
(*Function to generate the inventory sequence*)
InventorySequence[terms_] :=
Module[{num = 0, alst = {0}, inventory, c}, inventory = <|0 -> 1|>;
Table[c = Lookup[inventory, num, 0];
num = If[c == 0, 0, num + 1];
alst = Append[alst, c];
inventory[c] = Lookup[inventory, c, 0] + 1;, {n, 2, terms}];
alst]
(*Generate the inventory sequence*)
biglist = InventorySequence[201790];
(*Print first 100 elements of the sequence*)
partitioned = Partition[Take[biglist, 100], 10];
Do[Print[Row[partitioned[[i]], " "]], {i, Length[partitioned]}]
(*Find and print the first occurrences of elements>=thresholds*)
thresholds = 1000 Range[1, 10];
firstOccurrences =
Reap[Do[If[biglist[[i]] >= thresholds[[1]],
Sow[{thresholds[[1]], biglist[[i]], i}];
thresholds = Rest[thresholds];
If[Length[thresholds] == 0, Break[]];], {i, Length[biglist]}]][[
2, 1]];
(*Print the formatted results*)
Do[Print["First element \[GreaterEqual] ", firstOccurrence[[1]],
" is ", firstOccurrence[[2]], " at index ",
firstOccurrence[[3]]], {firstOccurrence, firstOccurrences}]
(*Plot the first 10,000 elements of the sequence*)
ListPlot[biglist[[1 ;; 10000]], Joined -> True,
PlotStyle -> {Thin, Blue}, PlotRange -> Full]
- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000 is 1001 at index 24256 First element >= 2000 is 2009 at index 43302 First element >= 3000 is 3001 at index 61709 First element >= 4000 is 4003 at index 81457 First element >= 5000 is 5021 at index 98705 First element >= 6000 is 6009 at index 121343 First element >= 7000 is 7035 at index 151757 First element >= 8000 is 8036 at index 168805 First element >= 9000 is 9014 at index 184429 First element >= 10000 is 10007 at index 201789
main :: [sys_message]
main = [Stdout "First 100 elements:\n",
Stdout (table 10 5 (take 100 invseq)),
Stdout (lay (map disp (zip2 thresholds firsts)))
]
where thresholds = [1000, 2000..10000]
firsts = first [(>x) | x <- thresholds] invseq
disp (t,(i,x)) = concat ["First > ",
rjustify 5 (shownum t),
": ",
rjustify 5 (shownum x),
" at ",
rjustify 6 (shownum i)]
table :: num->num->[num]->[char]
table w cw nums = lay [ concat (map (rjustify cw . show) row)
| row <- group w nums]
group :: num->[*]->[[*]]
group sz [] = []
group sz ls = take sz ls : group sz (drop sz ls)
invseq :: [num]
invseq = f [] 0
where f acc i = el : f (inc el acc) i'
where el = get i acc
i' = 0, if el=0
i' = i+1
get :: num->[(num,num)]->num
get n [] = 0
get n ((n,x):ns) = x
get n (m:ns) = get n ns
inc :: num->[(num,num)]->[(num,num)]
inc n [] = [(n, 1)]
inc n ((n,x):ns) = (n,x+1):ns
inc n (m:ns) = m:inc n ns
first :: [(*->bool)]->[*]->[(num,*)]
first ps = f ps 0
where f [] n xs = []
f (p:ps) n (x:xs) = (n, x) : f ps (n+1) xs, if p x
f (p:ps) n (x:xs) = f (p:ps) (n+1) xs- Output:
First 100 elements:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
import std/[strformat, tables]
import gnuplot
iterator inventorySequence(): (int, int) =
var counts: CountTable[int]
var idx = -1
while true:
var i = 0
while true:
let n = counts[i]
inc idx
counts.inc(n)
yield (idx, n)
if n == 0: break
inc i
echo "First 100 elements:"
var x, y: seq[int]
var lim = 1000
for idx, n in inventorySequence():
if idx < 10000:
x.add idx
y.add n
if idx <= 100:
stdout.write &"{n:>2}"
stdout.write if idx mod 10 == 0: '\n' else: ' '
if idx == 100: echo()
elif n >= lim:
echo &"First element ⩾ {lim:>5} is {n:>5} at index {idx:>6}"
lim += 1000
if lim > 10000: break
withGnuPlot:
plot(x, y, "Inventory sequence", "with impulses lw 0.5")
png("inventory_sequence.png")
- Output:
First 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 8 First element ⩾ 1000 is 1001 at index 24255 First element ⩾ 2000 is 2009 at index 43301 First element ⩾ 3000 is 3001 at index 61708 First element ⩾ 4000 is 4003 at index 81456 First element ⩾ 5000 is 5021 at index 98704 First element ⩾ 6000 is 6009 at index 121342 First element ⩾ 7000 is 7035 at index 151756 First element ⩾ 8000 is 8036 at index 168804 First element ⩾ 9000 is 9014 at index 184428 First element ⩾ 10000 is 10007 at index 201788
.png){kind=link}
MODULE InventorySequence; (* find elements of the inventory sequence *)
IMPORT Out;
CONST maxToShow = 10000; (* last value to show first element > *)
maxNumber = maxToShow + 1000; (* max. element value to consider *)
VAR occurs (* number of times each number occurs *)
: ARRAY maxNumber + 1 OF INTEGER;
nextToShow, seqPos, element, i, n : INTEGER;
BEGIN
FOR i := 0 TO maxNumber DO occurs[ i ] := 0 END;
seqPos := 0; (* current end of the sequence *)
nextToShow := 1000; (* first value to show first element > *)
WHILE nextToShow <= maxToShow DO
element := 1; (* any non-zero value will do *)
n := -1;
WHILE ( nextToShow <= maxToShow ) & ( element # 0 ) DO
INC( n );
element := occurs[ n ];
INC( seqPos );
IF seqPos <= 100 THEN
Out.String( " " );Out.Int( element, 4 );
IF seqPos MOD 10 = 0 THEN Out.Ln END
ELSIF element > nextToShow THEN
Out.String( "Element " );Out.Int( seqPos, 8 );
Out.String( " (" );Out.Int( element, 8 );
Out.String( ") is first > " );Out.Int( nextToShow, 6 );Out.Ln;
INC( nextToShow, 1000 )
END;
IF element < maxNumber THEN
INC( occurs[ element ] )
END
END
END
END InventorySequence.
- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
Element 24256 ( 1001) is first > 1000
Element 43302 ( 2009) is first > 2000
Element 61709 ( 3001) is first > 3000
Element 81457 ( 4003) is first > 4000
Element 98705 ( 5021) is first > 5000
Element 121343 ( 6009) is first > 6000
Element 151757 ( 7035) is first > 7000
Element 168805 ( 8036) is first > 8000
Element 184429 ( 9014) is first > 9000
Element 201789 ( 10007) is first > 10000
uses PlotWPF;
function inventorySequence(): sequence of integer;
begin
var counts := new Dictionary<integer, integer>;
while true do
begin
var i := 0;
while true do
begin
var n := counts.Get(i);
counts[n] := counts.Get(n) + 1;
yield n;
if n = 0 then break;
i += 1;
end;
end;
end;
begin
foreach var element in inventorysequence.Take(100) index i do
write(element:3, if i mod 20 = 19 then #10 else '');
println;
for var n := 1 to 10 do
begin
var element := inventorysequence.Select((x, i) -> (i, x)).first(x -> x[1] > n * 1000);
writeln('First element >= ', n * 1000, ' is ', element[1], ' at index ', element[0]);
end;
var x := arrgen(10_000, x -> real(x));
var y := inventorysequence.Take(10_000).Select(x -> real(x));
var plot := new MarkerGraphWPF(x, y, Colors.Black, MarkerType.Circle, 3);
end.
- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000 is 1001 at index 24255 First element >= 2000 is 2009 at index 43301 First element >= 3000 is 3001 at index 61708 First element >= 4000 is 4003 at index 81456 First element >= 5000 is 5021 at index 98704 First element >= 6000 is 6009 at index 121342 First element >= 7000 is 7035 at index 151756 First element >= 8000 is 8036 at index 168804 First element >= 9000 is 9014 at index 184428 First element >= 10000 is 10007 at index 201788
use strict;
use warnings;
use feature 'say';
use List::AllUtils <max firstidx>;
use GD::Graph::bars;
sub comma { reverse ((reverse shift) =~ s/.{3}\K/,/gr) =~ s/^,//r }
sub table { my $t = 20 * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }
my($i, @inventory, %i) = 0;
do {
my $count = $i{$i} // 0;
$i = $count ? $i+1 : 0;
++$i{$count};
push @inventory, $count
} until $inventory[-1] > 10_000;
say "Inventory sequence, first 100 elements:\n" . table @inventory[0..99]; say '';
for my $n (map { $_ * 1000 } 1..10) {
my $i = firstidx { $_ >= $n } @inventory;
printf "First element >= %6s is %6s in position: %s\n", comma($n), comma($inventory[$i]), comma $i;
}
# graph
my @data = ( [0..5000], [@inventory[0..5000]] );
my $graph = GD::Graph::bars->new(800, 600);
$graph->set(
title => 'Inventory sequence',
y_max_value => 250,
x_tick_number => 5,
r_margin => 10,
dclrs => [ 'blue' ],
) or die $graph->error;
my $gd = $graph->plot(\@data) or die $graph->error;
open my $fh, '>', 'Perl-inventory-sequence.png';
binmode $fh;
print $fh $gd->png();
close $fh;
- Output:
Inventory sequence, first 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1,000 is 1,001 in position: 24,255 First element >= 2,000 is 2,009 in position: 43,301 First element >= 3,000 is 3,001 in position: 61,708 First element >= 4,000 is 4,003 in position: 81,456 First element >= 5,000 is 5,021 in position: 98,704 First element >= 6,000 is 6,009 in position: 121,342 First element >= 7,000 is 7,035 in position: 151,756 First element >= 8,000 is 8,036 in position: 168,804 First element >= 9,000 is 9,014 in position: 184,428 First element >= 10,000 is 10,007 in position: 201,788
-- demo\rosetta\Inventory_sequence.exw with javascript_semantics function inventory(integer limit) sequence inv = {0}, counts = {1} integer ix = 0, thousands = 1000 while true do integer i = 0 while true do integer j = iff(i>=length(counts)?0:counts[i+1]) inv &= j while j>=length(counts) do counts &= 0 end while counts[j+1] += 1 ix += 1 if length(inv)=100 then printf(1,"Inventory sequence, first 100 elements:\n%s\n", {join_by(inv,1,20,"",fmt:="%3d")}) end if if j=0 then exit end if if j>=thousands then printf(1,"First element >= %,6d is %,6d at index %,7d\n", {thousands, j, ix}) if j>=limit then return inv[1..limit] end if thousands += 1000 end if i += 1 end while end while end function constant lim = 1e4 sequence x = tagset(lim), y = inventory(lim) include pGUI.e include IupGraph.e function get_data(Ihandle graph) integer {w,h} = IupGetIntInt(graph,"SIZE") IupSetInt(graph,"XTICK",iff(w<500?iff(w<350?iff(w<250?5000:2500):2000):1000)) IupSetInt(graph,"YTICK",iff(h<350?iff(h<200?iff(h<150? 200: 100): 80): 40)) return {{x,y,CD_BLUE}} end function IupOpen() Ihandle graph = IupGraph(get_data,"XMIN=0,XMAX=10000,YMIN=0,YMAX=400"), dlg = IupDialog(graph,`TITLE=gGraph,SIZE=320x240,MINSIZE=240x140`) IupShow(dlg) if platform()!=JS then IupMainLoop() end if
- Output:
Inventory sequence, first 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1,000 is 1,001 at index 24,255 First element >= 2,000 is 2,009 at index 43,301 First element >= 3,000 is 3,001 at index 61,708 First element >= 4,000 is 4,003 at index 81,456 First element >= 5,000 is 5,021 at index 98,704 First element >= 6,000 is 6,009 at index 121,342 First element >= 7,000 is 7,035 at index 151,756 First element >= 8,000 is 8,036 at index 168,804 First element >= 9,000 is 9,014 at index 184,428 First element >= 10,000 is 10,007 at index 201,788
100H:
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PRINT: PROCEDURE (STR); DECLARE STR ADDRESS; CALL BDOS(9, STR); END PRINT;
PRINT$NUM: PROCEDURE (N, W);
DECLARE BUF (6) BYTE INITIAL ('.....$');
DECLARE N ADDRESS, (I, W) BYTE;
DO I=0 TO 4; BUF(I) = ' '; END;
I = 5;
DIGIT:
BUF(I := I-1) = '0' + N MOD 10;
IF (N := N/10) > 0 THEN GO TO DIGIT;
CALL PRINT(.BUF(5-W));
END PRINT$NUM;
DECLARE INV$SEQ (24500) ADDRESS;
CALC$SEQ: PROCEDURE;
DECLARE (ITEM, SEARCH$IDX, SEARCH$NUM) ADDRESS;
INV$SEQ(0) = 0;
SEARCH$NUM = 0;
DO ITEM = 1 TO LAST(INV$SEQ);
CALL PRINT$NUM(ITEM, 5);
CALL PRINT(.(13,'$'));
INV$SEQ(ITEM) = 0;
DO SEARCH$IDX = 0 TO ITEM-1;
IF INV$SEQ(SEARCH$IDX) = SEARCH$NUM THEN
INV$SEQ(ITEM) = INV$SEQ(ITEM) + 1;
END;
IF INV$SEQ(ITEM) = 0
THEN SEARCH$NUM = 0;
ELSE SEARCH$NUM = SEARCH$NUM + 1;
END;
END CALC$SEQ;
FIND$FIRST: PROCEDURE (N) ADDRESS;
DECLARE (N, I) ADDRESS;
DO I = 0 TO LAST(INV$SEQ);
IF INV$SEQ(I) >= N THEN RETURN I;
END;
END FIND$FIRST;
CALL CALC$SEQ;
DECLARE I ADDRESS;
CALL PRINT(.('FIRST 100 ITEMS OF INVENTORY SEQUENCE:',13,10,'$'));
DO I=0 TO 99;
CALL PRINT$NUM(INV$SEQ(I), 4);
IF I MOD 10 = 9 THEN CALL PRINT(.(13,10,'$'));
END;
CALL PRINT(.'FIRST ELEMENT >= 1000: $');
CALL PRINT$NUM(INV$SEQ(I := FIND$FIRST(1000)), 5);
CALL PRINT(.' AT $');
CALL PRINT$NUM(I, 5);
CALL EXIT;
EOF- Output:
FIRST 100 ITEMS OF INVENTORY SEQUENCE: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 FIRST ELEMENT >= 1000: 1001 AT 24255
Output similar to Wren example except that the indices are one more because Pluto normally uses 1-based indexing.
require "bitmap"
require "table2"
local fmt = require "fmt"
local max = 10000
local inv = {0}
local counts = table.rep(max + 100, 0) -- say
counts[1] = 1
local lower = 100
local upper = 1000
local done = false
local ix = 1
while !done do
local i = 1
while true do
local j = counts[i]
if #inv < max then inv:insert(j) end
++counts[j + 1]
++ix
if #inv >= lower then
print("Inventory sequence, first 100 elements:")
fmt.tprint("%2d", inv:slice(1, 100), 20)
print()
lower = max + 1
end
if j == 0 then break end
if j >= upper then
fmt.print("First element >= %6s is %6s at index %7s", fmt.int(upper), fmt.int(j), fmt.int(ix))
if j >= max then
done = true
break
end
upper += 1000
end
++i
end
end
-- Generate points for the plot.
local pts = range(1, max):map(|i| -> {i, inv[i]})
local bmp = bitmap.of(1000, 600, color.white, "Inventory_sequence_-_first_10000_elements")
local ch = chart.of(bmp, 100, 500, 800, 400, range(0, 10000), range(0, 450))
ch:axes(color.black, 2)
local xmarks = range(0, 10000, 500)
local ymarks = range(0, 400, 50)
ch:mark(xmarks, ymarks, color.black, 2)
local xmarks2 = range(0, 10000, 1000)
local ymarks2 = range(0, 400, 100)
ch:label(xmarks2, ymarks2, color.black, 2, color.black)
ch:lineGraph(pts, pico.blue, 2)
bmp:view()
- Output:
Terminal output:
Inventory sequence, first 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1,000 is 1,001 at index 24,256 First element >= 2,000 is 2,009 at index 43,302 First element >= 3,000 is 3,001 at index 61,709 First element >= 4,000 is 4,003 at index 81,457 First element >= 5,000 is 5,021 at index 98,705 First element >= 6,000 is 6,009 at index 121,343 First element >= 7,000 is 7,035 at index 151,757 First element >= 8,000 is 8,036 at index 168,805 First element >= 9,000 is 9,014 at index 184,429 First element >= 10,000 is 10,007 at index 201,789
''' rosettacode.org/wiki/Inventory_sequence '''
from collections import Counter
from matplotlib.pyplot import plot
def inventory_sequence(terms):
''' From the code by Branicky at oeis.org/A342585 '''
num, alst, inventory = 0, [0], Counter([0])
for n in range(2, terms+1):
c = inventory[num]
num = 0 if c == 0 else num + 1
alst.append(c)
inventory.update([c])
return alst
biglist = inventory_sequence(201_790)
thresholds = [1000 * j for j in range(1, 11)]
for i, k in enumerate(biglist):
if i < 100:
print(f'{k:<4}', end='\n' if (i + 1) % 20 == 0 else '')
elif k >= thresholds[0]:
print(f'\nFirst element >= {thresholds.pop(0):5}: {k:5} in position {i:6}')
if len(thresholds) == 0:
break
plot(biglist[:10_000], linewidth=0.3)
plt.show()
- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000: 1001 in position 24255 First element >= 2000: 2009 in position 43301 First element >= 3000: 3001 in position 61708 First element >= 4000: 4003 in position 81456 First element >= 5000: 5021 in position 98704 First element >= 6000: 6009 in position 121342 First element >= 7000: 7035 in position 151756 First element >= 8000: 8036 in position 168804 First element >= 9000: 9014 in position 184428 First element >= 10000: 10007 in position 201788
[ 0 unrot witheach
[ over =
rot + swap ]
drop ] is occurs ( n [ --> n )
[ 2dup occurs
tuck join
dip [ 0 != tuck * + ] ] is additem ( n [ --> n [ )
0 [] 100 times additem
witheach
[ dup 10 < if sp
echo sp
i^ 10 mod 9 = if cr ]
drop
cr
0 []
[ additem
dup -1 peek 999 >
until ]
say "Element #"
dup size 1 - echo
say " is "
-1 peek echo
say "." cr
drop- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 Element #24255 is 1001.
Don't execute the main function without any arguments or it'll run forever. As usual for R, indexing starts at 1. The code handles the stretch task quite slowly, but that's to be expected when you're dealing with vectors that have more than 100,000 elements.
inv_sequence <- function(lim_length=Inf, lim_value=Inf){
counter <- iseq <- 0
repeat{
if(counter==0){
if(length(iseq)==lim_length) return(iseq)
iseq <- c(iseq, sum(iseq==0))
if(sum(iseq==0)>=lim_value) return(iseq)
counter <- 1
}
while(counter>0){
if(length(iseq)==lim_length) return(iseq)
next_inv <- sum(iseq==counter)
iseq <- c(iseq, next_inv)
if(next_inv==0){
counter <- 0
break
}
if(next_inv>=lim_value) return(iseq)
counter <- counter+1
}
}
}
inv_sequence(lim_length=100)
bigseqs <- lapply(1000*(1:10), function(n) inv_sequence(lim_value=n))
lens <- sapply(bigseqs, length)
elements <- sapply(bigseqs, function(v) v[length(v)])
paste("First element >=", 1000*(1:10), "is", elements, "at index", lens) |> writeLines()
png(filename="InventorySequence-R.png", width=1920, height=1080)
plot(1:10000, inv_sequence(lim_length = 10000), type="l", xlab=NA, ylab=NA)
dev.off()
- Output:
[1] 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 [26] 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 [51] 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 [76] 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000 is 1001 at index 24256 First element >= 2000 is 2009 at index 43302 First element >= 3000 is 3001 at index 61709 First element >= 4000 is 4003 at index 81457 First element >= 5000 is 5021 at index 98705 First element >= 6000 is 6009 at index 121343 First element >= 7000 is 7035 at index 151757 First element >= 8000 is 8036 at index 168805 First element >= 9000 is 9014 at index 184429 First element >= 10000 is 10007 at index 201789
use Lingua::EN::Numbers;
my ($i, %i) = 0;
my @inventory = (^∞).map: {
my $count = %i{$i} // 0;
$i = $count ?? $i+1 !! 0;
++%i{$count};
$count
}
say "Inventory sequence, first 100 elements:\n" ~
@inventory[^100].batch(20)».fmt("%2d").join: "\n";
say '';
for (1..10).map: * × 1000 {
my $k = @inventory.first: * >= $_, :k;
printf "First element >= %6s is %6s in position: %s\n",
.&comma, @inventory[$k].&comma, comma $k;
}
use SVG;
use SVG::Plot;
my @x = ^10000;
'Inventory-raku.svg'.IO.spurt:
SVG.serialize: SVG::Plot.new(
background => 'white',
width => 1000,
height => 600,
plot-width => 950,
plot-height => 550,
x => @x,
values => [@inventory[@x],],
title => "Inventory Sequence - First {+@x} values (zero indexed)",
).plot: :lines;
- Output:
Inventory sequence, first 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1,000 is 1,001 in position: 24,255 First element >= 2,000 is 2,009 in position: 43,301 First element >= 3,000 is 3,001 in position: 61,708 First element >= 4,000 is 4,003 in position: 81,456 First element >= 5,000 is 5,021 in position: 98,704 First element >= 6,000 is 6,009 in position: 121,342 First element >= 7,000 is 7,035 in position: 151,756 First element >= 8,000 is 8,036 in position: 168,804 First element >= 9,000 is 9,014 in position: 184,428 First element >= 10,000 is 10,007 in position: 201,788
converted to a .png to reduce size for display here:
$ENTRY Go {
, <InvSeqTo 210000>: e.Inv
, <First 100 e.Inv>: (e.100) e.1
, <Each (Mul 1000) <Iota 1 10>>: e.Ts
= <Prout 'First 100 elements:'>
<Tbl 10 5 e.100>
<Each (DispFind (e.Inv)) e.Ts>;
};
Iota {
s.E s.E = s.E;
s.S s.E = s.S <Iota <+ 1 s.S> s.E>;
};
DispFind {
t.L s.T, <Find t.L s.T>: s.X s.N =
<Prout 'First > ' <Fmt 5 s.T> ': '
<Fmt 5 s.X> ' at ' <Fmt 6 s.N>>;
};
Find {
(s.X e.Y) s.T = <Find (s.X e.Y) 0 s.T>;
(s.X e.Y) s.N s.T, <Compare s.X s.T>: {
'+' = s.X s.N;
s.1 = <Find (e.Y) <+ 1 s.N> s.T>;
};
};
Tbl {
s.W s.CW = ;
s.W s.CW e.X, <First s.W e.X>: (e.R) e.Y =
<Prout <Each (Fmt s.CW) e.R>>
<Tbl s.W s.CW e.Y>;
};
Fmt {
s.W s.N,
<Rep s.W ' '> <Symb s.N>: e.F,
<Last s.W e.F>: (e.1) e.2 = e.2;
};
Rep {
0 s.C = ;
s.N s.C = s.C <Rep <- s.N 1> s.C>;
};
Each {
(e.F) = ;
(e.F) t.I e.X = <Mu e.F t.I> <Each (e.F) e.X>;
};
InvSeqTo {
s.Num = <InvSeqTo () () s.Num>;
(e.X) (e.L) s.Num,
<SeqStep (e.X) (e.L) 0>: (e.X2) (e.L2),
<Lenw e.L2>: s.Len e.L2,
<Compare s.Len s.Num>: {
'-' = <InvSeqTo (e.X2) (e.L2) s.Num>;
s.1 = e.L2;
};
};
SeqStep {
(e.X) (e.L) s.N,
<GetN (e.X) s.N>: s.C,
<IncN (e.X) s.C>: e.X2,
e.L s.C: e.L2,
s.C: {
0 = (e.X2) (e.L2);
s.C = <SeqStep (e.X2) (e.L2) <+ 1 s.N>>;
};
};
GetN {
(e.X (s.N s.C) e.Y) s.N = s.C;
(e.X) s.N = 0;
};
IncN {
(e.X (s.N s.C) e.Y) s.N = e.X (s.N <+ 1 s.C>) e.Y;
(e.X) s.N = e.X (s.N 1);
};- Output:
First 100 elements:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
For efficiency reasons, two different programs are needed to generate the sequence or search for the first high value.
« → max
« { 0 1 1 0 } @ need to start with a non-null cycle to have ∑LIST work
WHILE DUP SIZE max < REPEAT
0 max FOR j
DUP 1 « j == » DOLIST ∑LIST @ count occurrences in the list
IF DUP NOT THEN max 'j' STO END
+
NEXT
END
1 max SUB
» 'INVT' STO @ ( n → { a(1)..a(n)} )
« DUP 1 + { } + 0 CON -1 → max counts j
« 2 CF 1
DO 'counts' 'j' INCR 1 +
IFERR GET THEN DROP2 0 END
IF DUP NOT THEN -1 'j' STO END
IF DUP max > THEN
"element" →TAG SWAP "position" →TAG 2 SF
ELSE
'counts' SWAP 1 + DUP2 GET 1 + PUT 1 +
END
UNTIL 2 FS? END
» » 'INVT1ST' STO @ ( n → 1st_value_>_n pos )
100 INVT 1000 INVT1ST
- Output:
3: { 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 }
2: element: 1001
1: position: 24256
Not actually counting but keeping count in a hash:
n = 0
counter = Hash.new(0)
inventory = loop.lazy.map do
c = counter[n]
counter[c] += 1
c == 0 ? n = 0 : n += 1
c
end
inventory.first(100).each_slice(10){|s| puts "%4d"*s.size % s}
puts
(1000..10000).step(1000).each do |t|
n = 0
counter.clear
puts "First element >= #{t} : %d index %d" % inventory.with_index.detect{|e,i| e > t}
end
Faster version (nearly 2x, doesn't restart counting for 1000 steps and doesn't use lazy enums)
def inv
cur_count_up = (0..).to_enum
total_counts = Hash.new(0)
loop do
c = total_counts[cur_count_up.next]
total_counts[c] += 1
yield c
cur_count_up.rewind if c.zero?
end
end
enum_for(:inv).first(100).each_slice(10){|s| puts "%4d"*s.size % s}
puts
ts = (1000..10000).step(1000)
enum_for(:inv).with_index do |e,i|
if e > ts.peek
puts "First element >= #{ts.peek} : %d index %d" % [e,i]
ts.next
end
end
- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000 : 1001 index 24255 First element >= 2000 : 2009 index 43301 First element >= 3000 : 3001 index 61708 First element >= 4000 : 4003 index 81456 First element >= 5000 : 5021 index 98704 First element >= 6000 : 6009 index 121342 First element >= 7000 : 7035 index 151756 First element >= 8000 : 8036 index 168804 First element >= 9000 : 9014 index 184428 First element >= 10000 : 10007 index 201788
program inventory_sequence;
loop init
inv := {};
next := 1000;
while next <= 10**4 do
loop init
i := 0;
until el = 0 do
el := inv(i) ? 0;
if (seq +:= 1) <= 100 then
nprint(lpad(str el, 5));
if seq mod 10 = 0 then print; end if;
elseif el > next then
print("First > " + lpad(str next, 10) + ": "
+ lpad(str el, 10) + " at" + lpad(str(seq-1), 10));
next +:= 1000;
end if;
inv(el) +:= 1;
i +:= 1;
end loop;
end loop;
end program;- Output:
0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
First > 1000: 1001 at 24255
First > 2000: 2009 at 43301
First > 3000: 3001 at 61708
First > 4000: 4003 at 81456
First > 5000: 5021 at 98704
First > 6000: 6009 at 121342
First > 7000: 7035 at 151756
First > 8000: 8036 at 168804
First > 9000: 9014 at 184428
First > 10000: 10007 at 201788
Simple, straight version, quadratic runtime (not above 1000)
\( Inventory Sequence [https://rosettacode.org/wiki/Inventory_sequence]
Simple, straighforward solution with one array and quadratic runtime.
will take several seconds on a modern CPU to find >= 1000
\)
main (p):+
\ row (integer key only) to store the elements; expands on demand
ir =: new row
\ determine first 100
while ir.Count < 100
simple cycle ir
\ show first 100 in groups of 10
for i =: from 1 upto 100
print format "%3;" ir[i] nonl
if i %% 10 = 0
print ''
\ add a cycle until value found
while true
for i =: from 1 upto ir.Last
if ir[i] >= 1000
print ir[i], i
return
\ not found, add another round
simple cycle ir
\( One round on the list (ir) of all numbers so far.
No upper limit required, does always stop.
\)
simple cycle (ir):
i =: 0
while
k =: (row ir find i all).Count
i =+ 1
ir[] =: k
if k = 0
return- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 1001 24256
Normal version without graphics
\( Inventory Sequence
see https://rosettacode.org/wiki/Inventory_sequence
Uses two rows (arrays) to store the sequence elements and the counts.
No graphic output (yet).
\)
\+ stdlib
main (p):+
seq =: new row \ sequence elements
counts =: new row \ counts
\ Fill the rows for the first 100
while seq.Count < 100
calculate cycle seq save counts
\ show in groups of 10
for i =: from 1 upto 100
print format "%3;" counts[i] nonl
if i %% 10 = 0
print ''
\ expand until max is above 10000
while seq.last < 10000
calculate cycle seq save counts
\ find the requested numbers
for i =: from 1000 upto 10000 step 1000
k =: find counts limit i
if k ~= ()
print format "%6; %6; %8;" i, counts[k], k
\ Fill the rows by one cycle
calculate cycle (seq) save (ir):
\ initial mc is void, which is ~= 0
for i =: from 0 step 1 until mc = 0
mc =: seq[i] + 0 \ zero if not yet used (void)
seq[mc] =+ 1
ir[] =: mc
\ find first cell in (seq) with value not smaller than (lim)
find (seq) limit (lim):
for k =: from 1 upto seq.Last
if seq[k] >= lim
return k- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 1000 1001 24256 2000 2009 43302 3000 3001 61709 4000 4003 81457 5000 5021 98705 6000 6009 121343 7000 7035 151757 8000 8036 168805 9000 9014 184429 10000 10007 201789
Simple brute force, so not very fast for the larger values. The plot of all these values shows some of the interesting patterns that were discussed in the Numberphile video.
Step ← ⋅⊂⍢(⟜₂(/+=)⊓+₁⊂|⋅⋅>₀)⟜₂(/+=) 0
⍥Step500 []
# Show selected values.
⊸⊃(&s≡⌟(⊂⤚⊡⊢⊚⊸>)×1000+1⇡10|&s↯∞_10↙100)
# Plot all of these values.
⊟∩(⌊×500)⊙(˜-1)⊓(˜÷⊸⇡|÷)⊸⊃⧻/↥
∧(⬚0⍜⊡⋅1)⊙(↯500_500 0)⍉⇌
- Output:
╭─
╷ 0 1 1 0 2 2 2 0 3 2
4 1 1 0 4 4 4 1 4 0
5 5 4 1 6 2 1 0 6 7
5 1 6 3 3 1 0 7 9 5
3 6 4 4 2 0 8 9 6 4
9 4 5 2 1 3 0 9 10 7
5 10 6 6 3 1 4 2 0 10
11 8 6 11 6 9 3 2 5 3
2 0 11 11 10 8 11 7 9 4
3 6 4 5 0 12 11 10 9 13
╯
╭─
╷ 1001 24255
2009 43301
3001 61708
4003 81456
5021 98704
6009 121342
7035 151756
8036 168804
9014 184428
10007 201788
╯
import "dome" for Window
import "graphics" for Canvas, Color
import "./plot" for Axes
import "./iterate" for Stepped
import "./fmt" for Fmt
var max = 10000
var inv = [0]
var counts = List.filled(max + 100, 0) // say
counts[0] = 1
var lower = 100
var upper = 1000
var done = false
var ix = 0
while (!done) {
var i = 0
while(true) {
var j = counts[i]
if (inv.count < max) inv.add(j)
counts[j] = counts[j] + 1
ix = ix + 1
if (inv.count >= lower) {
System.print("Inventory sequence, first 100 elements:")
Fmt.tprint("$2d", inv[0..99], 20)
System.print()
lower = max + 1
}
if (j == 0) break
if (j >= upper) {
Fmt.print("First element >= $,6d is $,6d at index $,7d", upper, j, ix)
if (j >= max) {
done = true
break
}
upper = upper + 1000
}
i = i + 1
}
}
// generate points for the plot
var Pts = (0...max).map { |i| [i, inv[i]] }.toList
class Main {
construct new() {
Window.title = "Inventory sequence - first 10,000 elements."
Canvas.resize(1000, 600)
Window.resize(1000, 600)
Canvas.cls(Color.white)
var axes = Axes.new(100, 500, 800, 400, 0..10000, 0..450)
axes.draw(Color.black, 2)
var xMarks = Stepped.new(0..10000, 500)
var yMarks = Stepped.new(0..400, 50)
axes.mark(xMarks, yMarks, Color.black, 2)
var xMarks2 = Stepped.new(0..10000, 1000)
var yMarks2 = Stepped.new(0..400, 100)
axes.label(xMarks2, yMarks2, Color.black, 2, Color.black)
axes.lineGraph(Pts, Color.blue, 2)
}
init() {}
update() {}
draw(alpha) {}
}
var Game = Main.new()
- Output:
Terminal output:
Inventory sequence, first 100 elements: 0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1,000 is 1,001 at index 24,255 First element >= 2,000 is 2,009 at index 43,301 First element >= 3,000 is 3,001 at index 61,708 First element >= 4,000 is 4,003 at index 81,456 First element >= 5,000 is 5,021 at index 98,704 First element >= 6,000 is 6,009 at index 121,342 First element >= 7,000 is 7,035 at index 151,756 First element >= 8,000 is 8,036 at index 168,804 First element >= 9,000 is 9,014 at index 184,428 First element >= 10,000 is 10,007 at index 201,788
include xpllib; \for Print
def Size = 201_790;
int Seq(Size), SeqEnd, Num, Count, N, Thresh;
[SeqEnd:= 0;
loop [Num:= 0;
repeat Count:= 0;
for N:= 0 to SeqEnd-1 do
if Num = Seq(N) then Count:= Count+1;
Seq(SeqEnd):= Count;
SeqEnd:= SeqEnd+1;
if SeqEnd >= Size then quit;
Num:= Num+1;
until Count = 0;
];
Thresh:= 1000;
for N:= 0 to SeqEnd-1 do
if N < 100 then
[Print("%3.0f", float(Seq(N)));
if rem(N/20) = 19 then CrLf(0);
]
else if Seq(N) >= Thresh then
[Print("First element >= %5.0f: %5.0f in position %6.0f\n",
float(Thresh), float(Seq(N)), float(N));
if Thresh >= 10000 then return;
Thresh:= Thresh + 1000;
];
]- Output:
0 1 1 0 2 2 2 0 3 2 4 1 1 0 4 4 4 1 4 0 5 5 4 1 6 2 1 0 6 7 5 1 6 3 3 1 0 7 9 5 3 6 4 4 2 0 8 9 6 4 9 4 5 2 1 3 0 9 10 7 5 10 6 6 3 1 4 2 0 10 11 8 6 11 6 9 3 2 5 3 2 0 11 11 10 8 11 7 9 4 3 6 4 5 0 12 11 10 9 13 First element >= 1000: 1001 in position 24255 First element >= 2000: 2009 in position 43301 First element >= 3000: 3001 in position 61708 First element >= 4000: 4003 in position 81456 First element >= 5000: 5021 in position 98704 First element >= 6000: 6009 in position 121342 First element >= 7000: 7035 in position 151756 First element >= 8000: 8036 in position 168804 First element >= 9000: 9014 in position 184428 First element >= 10000: 10007 in position 201788