Essays/Nonincreasing Odometer

From J Wiki
Jump to: navigation, search

Recursive Definition

A Nonincreasing Odometer is an odometer whose every index is less or equal to the index on the left.

Niod.png

The verb niod defines a nonincreasing odometer with origin 0, for x. number of indices and y.-1 highest value of the left-most index. The lowest index value is 0.

niod=: ;@:(<:@[ (] <@,. ($: >:))"0 ])`(,.@])@.(1:=[) i.

Slower explicit version for clarity:

niod1=: 4 : 0  NB. cols niod N
  if. x.=1 do. ,.i.y. return. end.
  ;(x.-1) (] <@,. (niod1 >:))"0 i.y.
)

For example, in origin 0 and 1:

   (; >:) 4 niod 3
+-------+-------+
|0 0 0 0|1 1 1 1|
|1 0 0 0|2 1 1 1|
|1 1 0 0|2 2 1 1|
|1 1 1 0|2 2 2 1|
|1 1 1 1|2 2 2 2|
|2 0 0 0|3 1 1 1|
|2 1 0 0|3 2 1 1|
|2 1 1 0|3 2 2 1|
|2 1 1 1|3 2 2 2|
|2 2 0 0|3 3 1 1|
|2 2 1 0|3 3 2 1|
|2 2 1 1|3 3 2 2|
|2 2 2 0|3 3 3 1|
|2 2 2 1|3 3 3 2|
|2 2 2 2|3 3 3 3|
+-------+-------+

The spectrum of origin 0 nonincreasing odometer demonstrates self-similar property used in the recursive verb niod.

   load 'viewmat'
   viewmat (;~ ".) '|: 8 niod 4'

Niod-recur.png

Base Representation

Nonincreasing odometer can be obtained directly from base-y. representation of the i.y.^x. sequence.

   od=: # #: i.@^~            NB. full homogeneous odometer
   ni=: #~ 2: *./@(>:/\)"1 ]  NB. nonincreasing filter

   4 (niod -: ni@od) 3
1

Size

The size of Nonincreasing Odometer is x. ([ ! <:@+) y.

   <"2|:( #@niod  ,  [ ! <:@+ )"0/~  2+i.4
+------------+------------+
| 3  4  5   6| 3  4  5   6|
| 6 10 15  21| 6 10 15  21|
|10 20 35  56|10 20 35  56|
|15 35 70 126|15 35 70 126|
+------------+------------+

Nialpdromes

The numbers obtained as y.#.x.niod y. are base-y. x.-digit nialpdromes (with 0 attached), that is their digits in the given base are in nonincreasing order.

Index plot of 4#.4 niod 4

Niod-index.png

Cumulative plot of 4#.4 niod 4

Niod-cum.png

   load 'plot'
   'stick' plot 4 (i.@^~ e. ] #. niod) 4
   'area' plot +/\ 4 (i.@^~ e. ] #. niod) 4

See Also



Contributed by Oleg Kobchenko