Re: sum{k>=m} floor(n/k) = n

Jake <sunny8tzu@xxxxxxxxx> wrote:

On Nov 2, 11:27 am, Leroy Quet <qqq...@xxxxxxxxxxxxxx> wrote:
I posted this on sci.math, but no one responded.

Consider the sequence A145265 of the On-Line Encyclopedia Of Integer
Sequences.

A positive integer n is included if there exists a positive integer m
such that sum{k>=0} floor(n/(m+k)) = n.

(Terms calculated by Stefan Steinerberger :
1, 4, 5, 8, 15, 18, 19, 22, 23, 26, 33, 36, 37, 40, 41, 44, 51, 54,
55, 58, 59, 62, 69, 72, 73, 76, 77, 80, 87, 90, 91, 94, 95, 98, 105,
108, 109, 112, 113, 116, 123, 126, 127, 130, 131, 134, 141, 144, 145,
148, 149, 152, 159, 162, 163, 166, 167, 170, 177, 180, 181, 184,...)

Does this sequence contain all of those, and only those, positive
integers that are congruent to 0, 1, 4, 5, 8, 15 (mod 18)?

It's true. It's helpful to look at the sum in the reverse order, in
which case we want to know whether there is a p such that

(*) n = sum{n>=l>=p} floor(n/l)

The number of 1's in the sequence {floor(n/l) : n>=l>=1} is ceil(n/2);
the number of 2's is ceil(2n/3) - ceil(n/2); the number of 3's is
ceil(3n/4) - ceil(2n/3); and so on. If we add up just the terms equal
to 1 or 2, we get roughly n/2 + 2(2n/3 - n/2) = 5n/6, but if we add up
all the terms equal to 1, 2 or 3, we get roughly n/2 + 2(2n/3 - n/2) +
3(3n/4 - 2n/3) = 13n/12. This means that if n is sufficiently large
and satisfies (*), then the sum will be of 1's and 2's and some number
of 3's. Therefore, to check whether it's possible for n to satisfy
(*), we need only see whether n is congruent to ceil(n/2) + 2(ceil(2n/
3) - ceil(n/2)) modulo 3. For n = 18q + r, this is true exactly when r
= 0, 1, 4, 5, 8 or 15. (The equality can be checked by hand for
"insufficiently large" n.)

Well spotted. I rate your post infinitely more useful than Insanator's.
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Moderator: polyforms group (polyforms-subscribe@xxxxxxxxxxx)
.

Relevant Pages

  • General Sum-Counting Result
    ... "In One Sequence Or Another " ... Let r be a positive integer. ... monotonically increasing function. ... and we sum over all r-tuples of positive integers ...
    (sci.math)
  • Re: Do any integers occur in both sequences?
    ... term for term you end up with a pattern progression. ... Where each even negation progresses by one followed ... sequence to generate the smaller ...
    (sci.math)
  • Re: sum{k>=m} floor(n/k) = n
    ... Consider the sequence A145265 of the On-Line Encyclopedia Of Integer ... A positive integer n is included if there exists a positive integer m ... then the sum will be of 1's and 2's and some number ...
    (rec.puzzles)
  • Fibonacci connection between Huffman codes and Wythoff array
    ... Given a sequence of n positive weights P=. ... The Wythoff array is shown below, to the right of the vertical colon line. ... A sequence Pmin of n positive integer weights is called ... A minimizing absolutely ordered sequence of the maximum height Huffman tree T ...
    (sci.math)
  • Pi Day Question
    ... sequence A001203 in Sloane's On-Line Encyclopedia Of Integer ... The comment at the related On-LIne Encyclopedia Of Integer Sequences ... positive integer occurs in the simple continued fraction of pi. ...
    (sci.math)