A curious connection

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

A curious connection

Postby Robin S » Sun Jul 15, 2007 1:32 am UTC

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?

User avatar
3.14159265...
Irrational (?)
Posts: 2413
Joined: Thu Jan 18, 2007 12:05 am UTC
Location: Ajax, Canada

Postby 3.14159265... » Sun Jul 15, 2007 2:12 am UTC

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. :D
"The best times in life are the ones when you can genuinely add a "Bwa" to your "ha""- Chris Hastings

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

Re: A curious connection

Postby Buttons » Sun Jul 15, 2007 2:13 am UTC

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.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Postby Robin S » Sun Jul 15, 2007 4:02 am UTC

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)

We already know that

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.

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

Re: A curious connection

Postby ARP » Thu Apr 26, 2012 9:00 pm UTC

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

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

Re: A curious connection

Postby Yesila » Fri Apr 27, 2012 7:14 am UTC

Holy "five years late" batman!


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests