Yes – for every positive integer k the two quantities coincide.
We first re-write the definition of T(k) a little more systematically and then
show that the set that is being counted in T(k) can be split up into
β(n,k) distinct elements for every n ≤ k!.
Because S(k) is the sum of these β(n,k)’s, the two numbers are equal.
Throughout let
k ≥ 1, N := k ! .
Every integer m with 1 ≤ m ≤ k N (= k·k!) can be written uniquely as
m = r + s N with 1 ≤ r ≤ N, 0 ≤ s ≤ k–1. (1)
We call r the “remainder’’ and s the “block number’’ of m.
Recall
β(r,k) = largest divisor of r that does not exceed k.
Claim.
With the notation in (1) an integer m belongs to T(k) ⟺ s < β(r,k).
Proof.
(⇒) Assume s < β(r,k) and put d := β(r,k).
Then d divides r and s+1 ≤ d ≤ k. Write m as
m = r + s N = d·(r/d) + (s+1) N – N.
Because d | N (N = k! is divisible by every integer ≤ k) we have
N = d·M for some integer M. Hence
m = d·( r/d + s M ).
Set i := d (so 1 ≤ i ≤ k) and j := r/d + s M. Because r ≤ N we have r/d ≤ M, and since s ≤ d – 1 we get
j = r/d + s M ≤ M + (d–1) M = d M = N.
Thus 1 ≤ j ≤ N = k!, and m = i·j with 1 ≤ i ≤ k, 1 ≤ j ≤ k!.
So m ∈ T(k).
(⇐) Conversely, suppose m ∈ T(k). Then m = i·j with
1 ≤ i ≤ k , 1 ≤ j ≤ N .
Write m in the form (1), m = r + s N. Because i divides m we have i | (r + s N). Since i | N, this implies i | r whenever i > s. But if i ≤ s then
j = m / i ≥ (s N + 1) / i ≥ N + 1 ,
contradicting j ≤ N. Hence some divisor of r that is > s (and therefore ≥ s+1) is ≤ k; the greatest such divisor is β(r,k). Consequently s < β(r,k).
Therefore m ∈ T(k) exactly when s < β(r,k).
Fix a remainder r (1 ≤ r ≤ N).
By the claim, for this r the admissible block numbers are
s = 0,1,…,β(r,k) – 1, (2)
i.e. exactly β(r,k) different values of s.
Because adding N moves us from one block to the next,
the k different blocks are disjoint, so the numbers of the
form r + s N with s in (2) are distinct elements of T(k).
Hence for each r there are β(r,k) distinct members of T(k), and every element of T(k) arises in exactly one such way. Therefore
|T(k)| = ∑_{r=1}^{N} β(r,k) = S(k).
For every positive integer k
S(k) = ∑_{n=1}^{k!} β(n,k) = T(k) = #{ i·j : 1 ≤ i ≤ k , 1 ≤ j ≤ k! }.
So the conjectured identity is true.
(Exactly the same proof works whenever k! is replaced by any multiple of every integer up to k; in particular, by k!, but not by the primorial ∏_{p≤k} p, which lacks that property.)
Was this answer helpful?
version: o3-2025-04-16
Status: UQ Validated
Validated: 8 months ago
Status: Needs Human Verification
Loading model reviews...
Loading reviews...