Viswanath's constant

[TT(n)]

This program can calculate Viswanath's constant, continued fractions, and strings of heads/tails.

[TT(n)]

I ran the algorithm out the 30,000 bits(flips) and the value continues to converge toward 1.131988...
I was able to do this by using Jeffery Walton's Big Integer package (http://www.codeguru.com/cpp/com-tech/atl/tutorials/article.php/c10609), here at the code guru!

I decided to investigate some brute force mapping of Random Fibonacci sequences, and I found an amazing recursive definition that does not rely on random decisions. I have not found this published, or mentioned anywhere else.

All possible nth flips
n
1 0 1
2 00 01 10 11
3 000 001 010 011 100 101 110 111
4 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
After n flips, there is roughly a 1/2^n chance of all heads.

Each set of flips{n} generates a set of Viswanath numbers, that can be averaged, after taking the n-th root of each term.
But, these numbers are also self generating, so they do not actually require the entire set of flip calculations to be carried out.
To calculate the terms of n, you may subtract/add the terms of a, from the terms of b. Where a and b are, n-2 and n-1 respectively.

Random Fibonacci numbers
n
1 0 2
2 1 1 -1 3
3 -1 1 -1 1 3 1 -1 5
4 2 0 0 2 2 0 0 2 -4 2 -2 0 4 2 -2 8
5 -3 1 -1 -1 1 1 -1 3 -3 1 -1 -1 1 1 -1 3 7 -1 1 5 3 -1 1 1 -5 3 -3 1 7 3 -3 13
6 5 -1 1 3 1 -1 1 -1 -1 1 -1 1 3 1 -1 5 5 -1 1 3 1 -1 1 -1 -1 1 -1 1 3 1 -1 5 -11 3 -3 -5 1 3 -3 7 -5 1 -1 -3 -1 1 -1 1 9 -1 1 7 5 -1 1 3 -9 5 -5 1 11 5 -5 21

Recursive definition
Step 1. Copy, reverse, and append a, to make it palindromic.
a=String
Set a=gnirtS String

Step 2. In general b +/- a = c.
If n is odd, subtract terms b-a=c, to generate the first half of c, but then add b+a=c, for the remaining terms.
If n is even, add terms b+a=c, to generate the first quarter of c, but then subtract for the second and third quarter, and finally add for the remaining quarter of the terms.

Animation
http://c3.ac-images.myspacecdn.com/images02/118/l_e803fa651bc74e51a35daaae78a90e82.gif

http://c3.ac-images.myspacecdn.com/images02/120/l_c75ba6d92afb4c16a913a280e479adee.gif

Operations
n
3 - - - - + + + +
4 + + + + - - - - - - - - + + + +
5 - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + +
6 + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + +
...
confirmed n<25
All terms appear to be relatively prime pairwise, as expected.
The ancestory differs from that of a Random Fibonacci Tree.
n=3

0 2
1 1 -1 3
-1 1 -1 1 3 1 -1 5


n=4

1 1 -1 3
-1 1 -1 1 3 1 -1 5
2 0 0 2 2 0 0 2 -4 2 -2 0 4 2 -2 8

[TheGreatCthulhu]

Wow! How did you ever manage to see the connection?


confirmed n<25


I guess you mean a brute force approach (confirmed by actual calculation)? If you could find an abstract, strict mathematical proof, and if this method has truly never been published, then you really could write a scientific article about it.

Considering the nature of the problem, maybe mathematical induction is the way to go?

[TT(n)]

Hello TheGreatCthulhu,

I started with brute force mapping of all possible v-numbers, at the n-th flip.
I quickly observed that every third term was related ofcourse, and I suspected an underlying pattern.
Although, it took a couple of dreams and sleeping to work out the order.
In a dream, to answer your question. lol

So then I wrote a second routine to repeat the recursive pattern, and confirm that they both produce the same results, ie 16 million+ terms in identical order.
I can't proof it just yet. There seems to be a few ways to go about it.

Since this is really a different way to express a Random Fibonacci tree, in linear order, it should be simple to proove.
Journal Integer Sequences (http://www.emis.de/journals/JIS/VOL10/Rittaud2/rittaud11.pdf)

I am open to ideas and collaboration with programmers or mathematicians.

[TheGreatCthulhu]

I tried to familiarize myself with the topic a bit.
If I understood this well, random Fibonacci sequence is defined by the recursive formula
c_{n}=+/-c_{n-1} +/-c_{n-2}, starting with 1 and 1. --- (1)

Your app calculates a subset of these numbers, the ones that correspond to the formula
c = a +/- b, a.k.a.
c_{n}=c_{n-2} +/- c_{n-1}, or, in relation to the formula at the top,
c_{n}=+/-c_{n-1} + c_{n-2}.

I suppose that it's already established that performing the same calculations used to get the Viswanath's constant gives the same result - that is, the convergence point is the same?

This formula generates a recursion tree that is a part of the tree generated by the original formula (i didn't say a subtree, since all the (-) branches of the second choice are missing).

Now, when you add/subtract terms of the first row to/from those of the second row (b+/-a), you are actually performing operations that belong to a different part of the recursion tree generated by formula (1). (Remember that the numbers were originally calculated with a+/-b). For some reason, this gives the same results.

But, I noticed that if you also make the lover row palindromic, and then add/substract the second row terms to/from those of the first (a+/-b), then you get exactly the same numbers AND you stay within the tree that arises from c=a+/-b (or c_{n}=+/-c_{n-1} + c_{n-2}).
It then becomes a matter of the order in which the branches are chosen.

Here, you can check it. It affects the calculation algorithm a bit, though.


0 | 2
1 | 1 | -1 | 3
-1 | 1 |-1 | 1 | 3 | 1 |-1 | 5
2 0 0 2 2 0 0 2-4 2-2 0 4 2-2 8

2 0 0 2 2 0 0 2
- - - - + + + +
3 -1 1 1 1 1 -1 3
-----------------
-1 1-1 1 3 1 -1 5

[TT(n)]

Very nice, I just noticed the lower row palindrome


There does seem to be a slight ambiguity in definitions posted in different places though. It could be reduced, or a reduction itself I suppose, but just to make sure we are on the same page.

+/- Values or Operators?

If previous elements a,b may be negative or positive, and are not specified or worded otherwise, then I believe it should be silent in the definition, with only the operator (+/-) written, & chosen at random. That being the only difference from the Fibonacci recursion.

c_{n} = c_{n-1} (+/-) c_{n-2}

During calculation those operations/values would be reduced ofcourse, ie 2 - -3 = 5, is reduced to 2+3 = 5, but in the recusion the value -3 should be retained as the previous element instead of 3. This reduction seems to be where some ambiguity sets into the different formulas, since they are virutally identical, but not.

Anyhow,
...you are actually performing operations that belong to a different part of the recursion tree..

Yes I agree, that must be.
Thanks for noticing that. I will be investigating the two algorithms(Tree vs. Palindrome) tonight, and looking for matching ancestors/children in both.

I also noticed that the convergence seems to speed up if the 0's and 2's are replaced with 1's, in the averaging of the 2^nth terms. Those that appear every 3n+1, when all terms are even numbers ofcourse.

If I find anything interesting, I'll post it.

[TheGreatCthulhu]

+/- Values or Operators?


Short answer: +/- operator.

Long answer:
It seems that you associate the first +/- in the formula to the value of c_{n-1}, however, this value (positive or negative) is independent of it.
In my opinion, you should think of the first +/- as of an unary operator.

To clarify it further, consider the - operation: it is actually + in disguise.

z = x – y , is the same as
z = x + (-1)*y

Whit this in mind, the formula

c_{n} = +/-c_{n-1} +/- c_{n-2},

where the signs are picked randomly, is equivalent to

c_{n} = (-1)^rnd(N) * c_{n-1} + (-1)^rnd(N) * c_{n-2},

where N is the set of natural numbers, and rnd(N) picks one of them randomly
(with (-1)^rnd(N) = -1 if rnd(N) is odd, and (-1)^rnd(N) = 1 if rnd(N) is even).


c_{n} = c_{n-1} (+/-) c_{n-2}


In light of what I said, please note that this formula is not the one used by your app, and that it generates a similar, but different recursion tree.

Your approach uses
c_{n} = c_{n-2} +/- c_{n-1}, which is equivalent to
c_{n} = +/-c_{n-1} + c_{n-2}, again, in light of what I said (+/- being an unary operator).

Now, this is the tree generated by c_{n} = +/-c_{n-1} +/- c_{n-2}. Note that each node has 4 children, since there are 4 choices.
The order of the choices is
--, -+, +-, ++



1
1
| -2 | 0 | 0 | 2 |
| 1 | 3 | -3 | 1 | -1 | 1 | -1 | 1 | -1 | 1 | -1 | 1 | -3 | -1 | 1 | 3 |
1-3 3-1-1-5 5 1 5 1-1-5 3-1 1-3 1 1-1-1-1-1 1 1 1 1-1-1-1-1 1 1 1 1-1-1-1-1 1 1 1 1-1-1-1-1 1 1 1 5-5-1-1 3-3 1-3 1-1 3-5-1 1 5
...



The numbers that are emphasized form a tree that corresponds exactly to the one generated by the formula your application uses
c_{n} = c_{n-2} +/- c_{n-1}.

Now, a random Fibonacci sequence is the same you would get if you randomly picked a number from each level of this tree.

However - what I was thinking, and this is only a guess, is that, if you applied the same procedure used to calculate Viswanath's constant to your formula (c=a +/- b), you might get the same result (as for c=+/-a +/- b).

I can't prove it though.


When I said that you move through a different part of the recursion tree when you apply your original algorithm, I meant that this way you choose paths that are somewhere in the area not highlighted above.

But, with all this in mind, maybe the original approach is actually better, since it seems to somehow jump from one part of the tree to the other in some quasirandom fashion, perhaps making the calculation more accurate.

Also note that the tree above has some interesting properties (sort of a "symmetry"/"antisymmetry" - I'm not sure how to call it...)

[TheGreatCthulhu]

There does seem to be a slight ambiguity in definitions posted in different places though. It could be reduced, or a reduction itself I suppose[...]


P.S. You are right, there are different definitions at different places, so this encourages me to think that your method is valid - since it would indicate that someone somewhere already proved that removing +/- in front one of the terms gives a sequence that can also be considered a random Fibonacci sequence, and thus can be used to calculate Viswanath's constant.

[TT(n)]

Version 3 is now available at the top of the thread.
_____________

Nearest Random Fibonacci numbers
The sequence, or sequences of flips out of all possible 2^n,
that produce the nearest integer value, to a power of Viswanath's constant V^n.

V(n)=2 1 1 2 3 3 4 3 3 4 5 5 6 5 7 8 9 9 10 11 13 16 17 19 22 25 29 32 37 41 46 53 59 68 77 85 100 113 125 144 163 181 208 233 263 298 341 387 432 487 561 634...
n=1 Confirmed n<37, but probable for n>36

Those integers, and their related powers.
V(n) V^n
2 1.1319882487943
1 1.28139739540838
1 1.45052679363791
2 1.64197928495939
3 1.8587012553377
3 2.10402797906149
4 2.38173494743203
3 2.69609597223576
3 3.05194895819253
4 3.45477035659395
5 3.91075944594724
5 4.42693373667359
6 5.01123696810554
5 5.67266135981905
7 6.42138599870466
8 7.26893349150593
9 8.22834729365203
9 9.31439244341248
10 10.54378279060136
11 11.93543821680031
13 13.51077580562834
16 15.29403944406563
17 17.31267292727880
19 19.59774230889882
22 22.18441399657233
25 25.11249595050768
29 28.42705031386913
32 32.17908690318418
37 36.42634823133505
41 41.23419814436031
46 46.67662774787161
53 52.83739410393661
59 59.81130922256948
68 67.70569918495079
77 76.64205585376611
...

Succesive Ratios:
10/9 1.1111111111111111111111111111111
11/10 1.1
13/11 1.1818181818181818181818181818182
16/13 1.2307692307692307692307692307692
17/16 1.0625
19/17 1.1176470588235294117647058823529
22/19 1.1578947368421052631578947368421
25/22 1.1363636363636363636363636363636
29/25 1.16
32/29 1.1034482758620689655172413793103
37/32 1.15625
41/37 1.1081081081081081081081081081081
46/41 1.1219512195121951219512195121951
53/46 1.1521739130434782608695652173913
59/53 1.1132075471698113207547169811321
68/59 1.1525423728813559322033898305085
77/68 1.1323529411764705882352941176471

Self similarity
V(n)~ V(n-5) + V(n-6)
V(n)~ V(n-6) + V(n-7) + V(n-8)
V(n)~ V(n-10) + V(n-11) + V(n-12) + V(n-13)
V(n)~ V(n-11) + V(n-12) + V(n-13) + V(n-14) + V(n-15)
V(n)~ V(n-12) + V(n-13) + V(n-14) + V(n-15) + V(n-16) + V(n-17)
V(n)~ V(n-13) + V(n-14) + V(n-15) + V(n-16) + V(n-17) + V(n-18) + V(n-19)
...