A359029 Integers m such that A006218(m+1)/(m+1) < A006218(m)/m.

6, 10, 12, 16, 18, 22, 24, 28, 30, 36, 40, 42, 45, 46, 48, 50, 52, 54, 56, 57, 58, 60, 61, 64, 66, 68, 70, 72, 73, 76, 78, 81, 82, 84, 85, 86, 88, 90, 92, 93, 94, 96, 100, 102, 105, 106, 108, 110, 112, 114, 117, 118, 120, 121, 122, 124, 126, 128, 130, 132, 133, 136

Offset

1,1

Comments

Equivalently: Indices m such that f(m + 1) < f(m) where f(m) = Sum_{k=1..m} d(k) / m, where d(k) is the number of divisors of k (A000005).

This sequence comes from a problem proposed by South Africa during the 47th International Mathematical Olympiad, in 2006 at Ljubljana, Slovenia, but not used for the competition (see link).

In fact, the problem asked for a proof that, for the sequence {f(m)} defined by f(m) = (1/m) * ([m/1] + [m/2] + ... + [m/m]), where [x] denotes the integer part of x,

(a) f(m + 1) > f(m) occurs infinitely often (see A359028),

(b) f(m + 1) < f(m) occurs infinitely often (this sequence).

Some results:

1. For every m, f(m) = (1/m) * ([m/1] + [m/2] + ... + [m/m]) proposed in the problem is the arithmetic mean of d(1), d(2), ..., d(m) = A006218(m)/m.

2. f(m + 1) < f(m) is equivalent to d(m + 1) < f(m).

3. Each m = p - 1, p prime >= 7 is a term, so A006093 \ {1,2,4} is a subsequence.

Proof: in this case, d(m+1) = 2 < f(6) = 7/3. Since f(6) > 2, it follows that f(m) > 2 holds for all m >= 6; so for m = p - 1, p prime >= 7, d(m+1) = 2 < f(m) because when m >= 6, f(m) is > 2.

4. As there are infinitely many primes, that also proves that f(m + 1) < f(m) occurs infinitely often, which answers IMO problem (b).

5. There exist other terms not belonging to A006093: 24, 45, 48, 50, 54, ...

Note that f(m) = f(m+1) is possible iff f(m) = tau(m+1), so f(m) must be an integer (A050226) but this is not sufficient. The only known term such that f(m) = f(m+1) is at m=4, with f(4) = 2 and f(5) = tau(5) = 2.

Links

Table of n, a(n) for n=1..62.

47th International Mathematical Olympiad, Slovenia, 2006, Problem N3, page 57, Shortlisted problems with solutions.

Index to sequences related to Olympiads.

Example

f(7) = (d(1)+d(2)+d(3)+d(4)+d(5)+d(6)+d(7)) / 7 = (1+2+2+3+2+4+2) / 7 = 16/7 < f(6) = (d(1)+d(2)+d(3)+d(4)+d(5)+d(6)) / 6 = (1+2+2+3+2+4) / 6 = 14/6 = 7/3, so 6 is a term.

Maple

with(numtheory):
for n from 1 to 150 do
m:= (1/(n+1))*sum(tau(k), k=1..n+1) - (1/n)*sum(tau(k), k=1..n);
if m<0 then print(n); else fi; od:

Mathematica

With[{m = 140}, Position[Differences[Accumulate[DivisorSigma[0, Range[m]]]/Range[m]], _?(# < 0 &)] // Flatten] (* Amiram Eldar, Dec 18 2022 *)

Prog

(PARI) f(n) = sum(k=1, n, n\k); \\ A006218
isok(m) = f(m+1)/(m+1) < f(m)/m; \\ Michel Marcus, Dec 19 2022

Crossrefs

Cf. A006093, A006218, A050226, A359028.

Sequence in context: A305188 A359201 A270364 * A315123 A315124 A370725

Adjacent sequences: A359026 A359027 A359028 * A359030 A359031 A359032

Keyword

nonn

Author

Bernard Schott, Dec 18 2022

Status

approved