# Calculate the Viswanath's constant (Random Fibonacci sequences)

How Can I calculate first few digits of Viswanath's constant?

Viswanath’s constant ≈ 1.1319882487943 is a real number whose nth power approximates the absolute value of the nth term of some random Fibonacci sequences.

a[0] = 0;
a[1] = 1;
a[n_] := a[n] = RandomChoice[{-1, 1}]*a[n - 1] + RandomChoice[{-1, 1}]*a[n - 2]


I have MMA 12.1 with high-end PC but there is no answer even for $$n=50000$$

by definition Viswanath’s constant is a $$n$$ th root of $$a[n]$$

Block[{\$RecursionLimit = Infinity}, N[a[50000]^(1/50000), 10]]

• Viswanath's original paper gives an algorithm for evaluating his constant. Feb 16, 2021 at 22:04
• One of the links in the Wikipedia article is to OEIS sequence A078416 for the decimal digits which has several links including one to the original paper. Feb 17, 2021 at 2:59
• @J.M.'sennui Can I use "Cuda cores" for this recursion?
– vito
Feb 17, 2021 at 11:28
• I don't know; you should do an experiment to see. Feb 17, 2021 at 11:40

I think the problem arises because of the depth of recursion. If you evaluate smaller values first, the depth of recursion is much less.

For example, using your definition of a, the following evaluates in under a second

Block[{n = 100 i}, Table[a[n], {i, 1, 500}]];


memoizing the value for a[50000]

Maybe even a better solution is not to memoize the values at all:

Timing[a0 = 0; a1 = 1; n = 10^5;
Do[{a0, a1} = {a1, a1 + RandomChoice[{-1, 1}]*a0}, {n - 1}];
N[Abs[a1]^(1/n), 10]]
(*Out: {0.103201, 1.134360272}*)


But the convergence is slow.