A curious connection

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

A curious connection

I was considering the number of consecutive terms of the integer reciprocal sequence (1/1, 1/2, 1/3...) which could be summed without exceeding 1, starting from the nth reciprocal. If we call this number of consecutive terms s(n) then, for example, s(2) = 2 because 1/2 + 1/3 < 1 but 1/2 + 1/3 + 1/4 > 1. The sequence begins:

1, 2, 4, 6, 7, 9, 11, 12, 14, 16, 18, 19, 21, 23, 24, 26, 28, 30, 31, 33...

A quick search on OEIS found that it formed the first column of this table which, as the page says, is a permutation of of the natural numbers. I'm not clear where the "x" in the given formula comes from, but anyway...

I also looked at the sequence t(n) = s(n) + n - 1:

1, 3, 6, 9, 11, 14, 17, 19, 22, 25, 28, 30, 33, 36, 38, 41, 44, 47, 49, 52...

My reason for doing this is best explained with an example: starting with 1/5, s(5)=7 consecutive integer reciprocals can be summed without exceeding 1. The last of these reciprocals is 1/t(5)=1/11.

Searching OEIS found this, which has a simple formula and moreover is precisely the set of "numbers n [not to be confused with the index, n, of the terms of the sequence] such that the first digit in ternary expansion on 2^n is 2" and also "appears in connection with the 3x+1 problem". I found this highly curious, as I can see no particular reason why the first digit of a power of two in ternary or, indeed, the 3x+1 problem should have anything to do with the index of the last reciprocal in a sum. Can anyone shed any light on this?
Robin S

Posts: 3557
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK

Because maths is awsome, and I must applaud you, thats super awsome.

I know I have something to look at for the next few hours.
"The best times in life are the ones when you can genuinely add a "Bwa" to your "ha""- Chris Hastings

3.14159265...
Irrational (?)

Posts: 2413
Joined: Thu Jan 18, 2007 12:05 am UTC

Re: A curious connection

That is curious. Are you positive that the sequence you've generated is identical to the one on OEIS? I encourage you to check another twenty or thirty terms to see. Coincidences happen a lot in sequences. t(n), for instance, agrees in all but three of the displayed terms with u(n) = ceiling(n*e). Clearly it's not that, but the point is that initial terms can be deceiving.
Buttons

Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Alas, they do appear to be different. The first difference is at t(32)=85, whereas the 32nd term of the OEIS sequence is 84. However, the sequences seem to diverge rather slowly: the last identical term appears to be t(118)=318, after which the OEIS sequence is always at least 1 less. t(146)=395 is the first to be underpredicted by 2. So perhaps there is still some sort of connection... In particular, it seems that if we call the OEIS sequence a(n), then a(y) = t(y) + k implies that

either

a(x) <= t(x) + k and a(z) >= t(z) + k - 1

or

a(x) <= t(x) + k+1 and a(z) >= t(z) + k

for all x<y<z.

In other words, the amount by which t(n) is underestimated by a(n) appears to be a rounded approximation of a strictly-(and slowly)-increasing function.

Edit: ironic discovery. Approximating 1/n + 1/(n+1) + ... + 1/(t(n)) as the integral from n to t(n) of 1/n, we obtain 1 - 1/(t(n)+1) < ln(t(n)) - ln(n) < 1 [using the bounds already defined]. Taking exponentials both sides, e^LHS < t(n) / n < e. Since the integral is an approximation which improves for large n, it is fair to say that t(n) approximately equals n*e for large n.

More accurately, it is easy to show that

ln(n+1) < 1/1 + 1/2 + ... + 1/n < 1+ln(n).

Therefore,

ln(t(n)+1) - (1+ln(n-1)) < 1/n + 1/(n+1) + ... + 1/(t(n)) < 1+ln(t(n)) - ln(n)

1 - 1/(t(n)+1) < 1/n + 1/(n+1) + ... + 1/(t(n)) < 1

Therefore,

ln(t(n)+1) - (1+ln(n-1)) < 1 and 1 - 1/(t(n)+1) < 1+ln(t(n)) - ln(n)

ln(t(n)+1) - ln(n-1) < 2 and -1/(t(n)+1) < ln(t(n)) - ln(n)

ln( (t(n)+1) / (n-1) ) < 2 and -1/(t(n)+1) < ln( t(n) / n )

t(n)+1 < (n-1)e^2 and t(n) > n / e^(1/(t(n)+1)

The second statement tells us nothing that wasn't obvious, but the first statement sets an upper bound on t(n) of (n-2)e^2, and the approximation above suggests that in fact t(n) stays close to n*e.
Robin S

Posts: 3557
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK

Re: A curious connection

OEIS A083088 gives explicit formula for this sequence
a(n) = floor(n/sqrt(2)) + n + 1
ARP

Posts: 4
Joined: Thu Apr 26, 2012 6:49 pm UTC

Re: A curious connection

Holy "five years late" batman!
Yesila

Posts: 222
Joined: Sun Dec 16, 2007 11:38 am UTC