Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Constructing the "analytical" formula for tetration.
#9
Well, here goes... this is LONG! I'm going to also give an explanation of the derivation, since you were asking for more "insight" into the problem.

OK, so you have the recurrence I gave.


.

If we expand a few terms, we get





...

Looking at this, we see that the number of products in each is 1, 1, 2, 4, 8, ... , or for . It is possible to prove this by considering how the above process works: each sum adds together the previous terms, which are themselves sums, thus the number of products in that sum should equal the sum of the numbers of products in the previous terms. That is,




Taking the forward difference of that last equation gives

.

This kind of difference equation has as solutions . We see that for the given initial conditions, i.e. and , for .

Now, we move on to consider the number of factors in each product. Counting them, we see that

n = 1: 1
n = 2: 2
n = 3: 2, 3
n = 4: 2, 3, 3, 4
n = 5: 2, 3, 3, 4, 3, 4, 4, 5
...

Looking at the formula, we see the nth term should be the concatenation (due to the sum) of the previous terms with their elements each incremented by 1 (due to the multiplication of a new factor.). That is,

.

(where the "+" are actually string concatenations. Formally, .)

We can "refactor" this process by noting that the "increment" "distributes" over the concatenation, so

.

Now, we know that the previous term is also an "incremented concatenation" of the terms before it, thus if we decremented that term and then concatenated itself to that, we would have the concatenation of all terms before , and thus



i.e. the sequence can be formed by taking the previous term, incrementing all its elements, and then concatenating it to the unincremented version, which is also easily observable from the pattern, but this gives a kind of "proof".

Anyway, by looking at the dictionary of integer sequences at oeis.org, I found that these strings appear within the sequence of "binary weights of n", the number of 1 bits in an integer. Looking at it, it appears element j (first is j = 1) of is given by the number of 1 bits in . This can be written explicitly. Note that is a "lossy right shift" of (i.e. shift right k bits, knock off everything past the binary point, like the ">>" operation in the C programming language.). Then, we can get the kth bit (0th is the LSB) of as . The second term is a lossy right shift by k+1 bits followed by a left shift by 1 bit, which is like the right shift by k bits but with its LSB cleared. So we can add up all the bits in (thus giving the number of 1 bits) by . Taking and noting that the first and last bit are always 1 (by virtue of and note also that this is always odd as is even and is odd, and even + odd = odd), we get .

These connections to binary made me wonder about whether or not this whole thing could be interpreted in terms of binary. I noticed that the are present at most only once in a product, i.e. there are no higher-degree factors. And the indices, for the nth term of our original sequence, range from 1 to n. So I thought that each product could be represented as a binary nxn matrix with 1-bit elements, and we could look for patterns there. This led me to see part of, but not all of, the pattern.

However, the most fruitful way of viewing it, I found, was to arrange the terms and factors like this:

Code:
r11

r21
r11

r31 r32
    r21
r11 r11

r41 r42 r43 r43
        r31 r32
    r21     r21
r11 r11 r11 r11


r51 r52 r53 r53 r54 r54 r54 r54
                r41 r42 r43 r43
        r31 r32         r31 r32
    r21     r21     r21     r21
r11 r11 r11 r11 r11 r11 r11 r11

where the value of each term can be found by multiplying the columns' elements together and then adding up the results.

We can now see an interesting alternating pattern... which looks like binary counting! We see that the factors appear and disappear as the bits of , which also explains the "number of 1 bits of " observation.

The left indices of the in a product, then, are generated by acquiring the position of each one bit in , with the LSB counted as position 1, and putting them in numerical order for convenience.

That is,

.

Now for the right indices. If we look at them, they look like (here, for the 5th term)

Code:
11
211
311
3211
411
4211
4311
43211

The same "bit index" interpretation works here as well. Ignoring the last "1", these terms give the positions of 1 bits in . So, we have

.

Then, the not-quite-symbolic but still "explicit" and "non-recursive" formula is

.
Reply


Messages In This Thread
RE: Constructing the "analytical" formula for tetration. - by mike3 - 01/28/2011, 09:12 PM

Possibly Related Threads...
Thread Author Replies Views Last Post
  Constructing real tetration solutions Daniel 4 929 12/24/2019, 12:10 AM
Last Post: sheldonison
  Recursive formula generating bounded hyper-operators JmsNxn 0 1,711 01/17/2017, 05:10 AM
Last Post: JmsNxn
  Extrapolated Faá Di Bruno's Formula Xorter 1 2,408 11/19/2016, 02:37 PM
Last Post: Xorter
  on constructing hyper operations for bases > eta JmsNxn 1 3,006 04/08/2015, 09:18 PM
Last Post: marraco
  Explicit formula for the tetration to base [tex]e^{1/e}[/tex]? mike3 1 3,259 02/13/2015, 02:26 PM
Last Post: Gottfried
  Number theoretic formula for hyper operators (-oo, 2] at prime numbers JmsNxn 2 4,356 07/17/2012, 02:12 AM
Last Post: JmsNxn
  fractional iteration by schröder and by binomial-formula Gottfried 0 2,776 11/23/2011, 04:45 PM
Last Post: Gottfried
  simple base conversion formula for tetration JmsNxn 0 3,481 09/22/2011, 07:41 PM
Last Post: JmsNxn
  Change of base formula using logarithmic semi operators JmsNxn 4 8,532 07/08/2011, 08:28 PM
Last Post: JmsNxn
  Breaking New Ground In The Quest For The "Analytical" Formula For Tetration. mike3 5 9,128 05/09/2011, 05:08 AM
Last Post: mike3



Users browsing this thread: 1 Guest(s)