Jump to content

Ruler function

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 02:25, 11 January 2022 (expand, still unsourced and drafty). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
A ruler, marked in centimeters (top), and inches (bottom). The rising and falling pattern of vertical lines on the inch scale resembles the ruler function.

In number theory, the ruler function of an integer can be either of two closely-related functions. One of these functions counts the number of times can be evenly divided by two, which for the numbers 0, 1, 2, ... is

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ... (sequence A007814 in the OEIS).

Alternatively, the ruler function can be defined as the same numbers plus one, which for the numbers 0, 1, 2, ... produces the sequence

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, ... (sequence A001511 in the OEIS).

For either definition of the ruler function, the rising and falling patterns of the values of this function resemble the lengths of marks on rulers with traditional units such as inches.

In advanced mathematics, the 0-based ruler function is the 2-adic valuation of the number.

In the Tower of Hanoi puzzle, with the disks of the puzzle numbered in order by their size, the 1-based ruler function gives the number of the disk to move at each step in an optimal solution to the puzzle.

References