• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 Constructing the "analytical" formula for tetration. mike3 Long Time Fellow Posts: 368 Threads: 44 Joined: Sep 2009 01/28/2011, 09:12 PM (This post was last modified: 01/29/2011, 12:25 AM by mike3.) 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. $a_1 = r_{1, 1}$ $a_n = \sum_{m=1}^{n-1} r_{n, m} a_m$. If we expand a few terms, we get $a_2 = r_{2, 1} r_{1, 1}$ $a_3 = r_{3, 1} r_{1, 1} + r_{3, 2} r_{2, 1} r_{1, 1}$ $a_4 = r_{4, 1} r_{1, 1} + r_{4, 2} r_{2, 1} r_{1, 1} + r_{4, 3} r_{3, 1} r_{1, 1} + r_{4, 3} r_{3, 2} r_{2, 1} r_{1, 1}$ $a_5 = r_{5, 1} r_{1, 1} + r_{5, 2} r_{2, 1} r_{1, 1} + r_{5, 3} r_{3, 1} r_{1, 1} + r_{5, 3} r_{3, 2} r_{2, 1} r_{1, 1} + r_{5, 4} r_{4, 1} r_{1, 1} + r_{5, 4} r_{4, 2} r_{2, 1} r_{1, 1} + r_{5, 4} r_{4, 3} r_{3, 1} r_{1, 1} + r_{5, 4} r_{4, 3} r_{3, 2} r_{2, 1} r_{1, 1}$ ... Looking at this, we see that the number of products in each $a_n$ is 1, 1, 2, 4, 8, ... , or $2^{n-2}$ for $n > 1$. 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, $PN_1 = 1$ $PN_n = \sum_{m=1}^{n-1} PN_m$ Taking the forward difference $\Delta$ of that last equation gives $\Delta PN_n = \sum_{m=1}^{n} PN_m - \sum_{m=1}^{n-1} PN_m = PN_n$. This kind of difference equation has as solutions $PN_n = r 2^n + s$. We see that for the given initial conditions, i.e. $PN_2 = 1$ and $PN_3 = 2$, $PN_n = 2^{n-2}$ for $n > 1$. 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 $r_{n, m}$ factor.). That is, $PFN_n = \mathrm{incr}(PFN_1) + \mathrm{incr}(PFN_2) + ... + \mathrm{incr}(PFN_{n-1}) = \sum_{m=1}^{n-1} \mathrm{incr}(PFN_m)$. (where the "+" are actually string concatenations. Formally, $PFN_n \in \mathbb{N}*$.) We can "refactor" this process by noting that the "increment" "distributes" over the concatenation, so $PFN_n = \sum_{m=1}^{n-1} \mathrm{incr}(PFN_m) = \mathrm{incr}\left(\sum_{m=1}^{n-1} PFN_m\right)$. 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 $PFN_n$, and thus $PFN_n = \mathrm{incr}(\mathrm{decr}(PFN_{n-1}) + PFN_{n-1}) = PFN_{n-1} + \mathrm{incr}(PFN_{n-1})$ 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 $PFN_n$ is given by the number of 1 bits in $2^{n-1} + 2j - 1$. This can be written explicitly. Note that $\lfloor\frac{N}{2^k}\rfloor$ is a "lossy right shift" of $N$ (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 $N$ as $\lfloor\frac{N}{2^k}\rfloor - 2\lfloor\frac{N}{2^{k+1}}\rfloor$. 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 $N$ (thus giving the number of 1 bits) by $\sum_{i=0}^{\lfloor\log_2(N)\rfloor} \lfloor\frac{N}{2^i}\rfloor - 2\lfloor\frac{N}{2^{i+1}}\rfloor$. Taking $N = 2^{n-1} + 2j - 1$ and noting that the first and last bit are always 1 (by virtue of $2^{n-1}$ and note also that this is always odd as $2^{n-1}$ is even and $2j - 1$ is odd, and even + odd = odd), we get ${(PFN_n)}_j = 2 + \sum_{i=0}^{\lfloor\log_2(j)\rfloor} \lfloor\frac{j}{2^i}\rfloor - 2\lfloor\frac{j}{2^{i+1}}\rfloor$. 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 $r_{n,m}$ are present at most only once in a product, i.e. there are no higher-degree $r_{n,m}$ 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 $2^{n-1} + 2j - 1$, which also explains the "number of 1 bits of $2^{n-1} + 2j - 1$" observation. The left indices of the $r_{n, m}$ in a product, then, are generated by acquiring the position of each one bit in $2^{n-1} + 2j - 1$, with the LSB counted as position 1, and putting them in numerical order for convenience. That is, $\mathrm{Left\ index\ of\ }k\mathrm{th\ factor\ of\ jth\ product\ in\ }n\mathrm{th\ term} = \mathrm{position\ of\ }k\mathrm{th\ 1\ bit\ in\ }2^{n-1} + 2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1}$. 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 $2j - 1$. So, we have $\mathrm{Right\ index\ of\ }k\mathrm{th\ factor\ of\ jth\ product\ in\ }n\mathrm{th\ term} = \mathrm{if\ }k-1 > 0\mathrm{,\ position\ of\ }k-1\mathrm{th\ 1\ bit\ in\ }2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1,\ otherwise\ 1}$. Then, the not-quite-symbolic but still "explicit" and "non-recursive" formula is $a_n = \sum_{j=1}^{2^{n-2}} \prod_{k=1}^{(\mathrm{number\ of\ 1\ bits\ in\ }2^{n-1} + 2j - 1)} r_{(\mathrm{position\ of\ }k\mathrm{th\ 1\ bit\ in\ }2^{n-1} + 2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1}),(\mathrm{if\ }k-1 > 0\mathrm{,\ position\ of\ }k-1\mathrm{th\ 1\ bit\ in\ }2j - 1\mathrm{,\ with\ the\ LSB\ counted\ as\ position\ 1,\ otherwise\ 1})}$. « Next Oldest | Next Newest »

 Messages In This Thread Constructing the "analytical" formula for tetration. - by mike3 - 01/17/2011, 01:05 PM RE: Constructing the "analytical" formula for tetration. - by Gottfried - 01/17/2011, 10:10 PM RE: Constructing the "analytical" formula for tetration. - by mike3 - 01/22/2011, 04:00 AM RE: Constructing the "analytical" formula for tetration. - by Gottfried - 01/24/2011, 08:56 AM RE: Constructing the "analytical" formula for tetration. - by mike3 - 01/28/2011, 03:12 AM RE: Constructing the "analytical" formula for tetration. - by Gottfried - 01/28/2011, 02:49 PM RE: Constructing the "analytical" formula for tetration. - by mike3 - 01/28/2011, 09:12 PM RE: Constructing the "analytical" formula for tetration. - by Gottfried - 01/28/2011, 10:42 PM RE: Constructing the "analytical" formula for tetration. - by mike3 - 01/29/2011, 12:10 AM RE: Constructing the "analytical" formula for tetration. - by mike3 - 02/10/2011, 04:20 AM RE: Constructing the "analytical" formula for tetration. - by sheldonison - 02/10/2011, 05:59 AM RE: Constructing the "analytical" formula for tetration. - by mike3 - 02/10/2011, 07:35 AM RE: Constructing the "analytical" formula for tetration. - by tommy1729 - 01/23/2011, 10:59 PM RE: Constructing the "analytical" formula for tetration. - by mike3 - 01/24/2011, 04:34 AM

 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 $$e^{1/e}$$? 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)