A372727 Triangle read by rows: T(n, k) = n if k = 0, otherwise n - k*floor(n/k). The binary modulo operation.

0, 1, 0, 2, 0, 0, 3, 0, 1, 0, 4, 0, 0, 1, 0, 5, 0, 1, 2, 1, 0, 6, 0, 0, 0, 2, 1, 0, 7, 0, 1, 1, 3, 2, 1, 0, 8, 0, 0, 2, 0, 3, 2, 1, 0, 9, 0, 1, 0, 1, 4, 3, 2, 1, 0, 10, 0, 0, 1, 2, 0, 4, 3, 2, 1, 0, 11, 0, 1, 2, 3, 1, 5, 4, 3, 2, 1, 0, 12, 0, 0, 0, 0, 2, 0, 5, 4, 3, 2, 1, 0

Offset: 0

Author

Peter Luschny, May 13 2024

Keywords

• nonn
• tabl

Comments

The binary operation 'mod' as defined here is discussed in 'Concrete Mathematics' by Graham et. al. on p. 82 and the connection with the congruence relation '(mod)' on p. 123. See also Bach & Shallit, p. 21, and Apostol, p. 14.

This definition is implemented in Sage, but not in Python. For example, Sage answers 0.mod(0) = 0, whereas in Python 0 % 0 leads to a 'ZeroDivisionError'. What is often misunderstood is that the operation 'mod' gives answers to divisibility, not to division. Apostol shows that n|0 (every integer divides zero), but 0|n implies n = 0 (zero divides only zero), and thus confirms the result given by Sage.

Examples

			Triangle begins:
  [ 0]  0;
  [ 1]  1, 0;
  [ 2]  2, 0, 0;
  [ 3]  3, 0, 1, 0;
  [ 4]  4, 0, 0, 1, 0;
  [ 5]  5, 0, 1, 2, 1, 0;
  [ 6]  6, 0, 0, 0, 2, 1, 0;
  [ 7]  7, 0, 1, 1, 3, 2, 1, 0;
  [ 8]  8, 0, 0, 2, 0, 3, 2, 1, 0;
  [ 9]  9, 0, 1, 0, 1, 4, 3, 2, 1, 0;
  [10] 10, 0, 0, 1, 2, 0, 4, 3, 2, 1, 0;
  [11] 11, 0, 1, 2, 3, 1, 5, 4, 3, 2, 1, 0;
.
The triangle shows the modulo operation in the range 0 <= k <= n. Test your
computer implementation in the range R X R where R = [-6, ..., 0, ..., 6].
According to Graham et al. it should look like this:
   0, -1, -2,  0,  0, 0, -6, 0, 0, 0, 2, 4, 0
  -5,  0, -1, -2, -1, 0, -5, 0, 1, 1, 3, 0, 1
  -4, -4,  0, -1,  0, 0, -4, 0, 0, 2, 0, 1, 2
  -3, -3, -3,  0, -1, 0, -3, 0, 1, 0, 1, 2, 3
  -2, -2, -2, -2,  0, 0, -2, 0, 0, 1, 2, 3, 4
  -1, -1, -1, -1, -1, 0, -1, 0, 1, 2, 3, 4, 5
   0,  0,  0,  0,  0, 0,  0, 0, 0, 0, 0, 0, 0
  -5, -4, -3, -2, -1, 0,  1, 0, 1, 1, 1, 1, 1
  -4, -3, -2, -1,  0, 0,  2, 0, 0, 2, 2, 2, 2
  -3, -2, -1,  0, -1, 0,  3, 0, 1, 0, 3, 3, 3
  -2, -1,  0, -2,  0, 0,  4, 0, 0, 1, 0, 4, 4
  -1,  0, -3, -1, -1, 0,  5, 0, 1, 2, 1, 0, 5
   0, -4, -2,  0,  0, 0,  6, 0, 0, 0, 2, 1, 0
		

References

• Tom Apostol, Introduction to analytic number theory, 1976, Springer, page 14.
• Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, 1997, p. 21.
• Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994, 34th printing 2022, p. 81f.

Crossrefs

Cf. A111490 (row sums).

Cf. A048158.

Programs

Maple

MOD := (n, k) -> ifelse(k = 0, n, n - k * iquo(n, k)):
seq( seq(MOD(n, k), k = 0..n), n = 0..12);

Python

def T(n, k): return n if k == 0 else n - k * (n // k)
for n in range(12): print([T(n, k) for k in range(n + 1)])

Python

def A372727_T(n, k): return n % k if k else n # Chai Wah Wu, May 14 2024

SageMath

def T(n, k): return n.mod(k)
for n in srange(12): print([T(n, k) for k in range(n + 1)])