Message Boards Message Boards

0
|
4869 Views
|
4 Replies
|
5 Total Likes
View groups...
Share
Share this post:

Is a number would be part of a series generated by LinearRecurrence?

Posted 3 years ago

Is there anyway to see if a number would be part of a series generated by a linearrecurrence?

Lets say the series is generated by

LinearRecurrence[{1, 0, 0, 0, 0, 0, 1, -1}, {3, 4, 5, 8, 11, 12, 13, 
  19}, {1, 20}]

and I want to determine if say 132858836366993 would be part of that series

POSTED BY: Paul Cleary
4 Replies

It can be done but it's not so easy.

First is to cast as a recurrence. If I did the translation correctly, it will be this one.

rs = RSolve[
  Flatten@{f[n] == f[n - 1] + f[n - 7] - f[n - 8], 
    Thread[Array[f, 8, 0] == {3, 4, 5, 8, 11, 12, 13, 19}]}, f[n], n]

Unfortunately the behavior of this is less than adequate. It gives some warning and hangs.

During evaluation of In[6]:= N::meprec: Internal precision limit $MaxExtraPrecision = 50.` reached while evaluating Log[Cos[(3 \[Pi])/14]^2+Sin[(3 \[Pi])/14]^2].

During evaluation of In[6]:= N::meprec: Internal precision limit $MaxExtraPrecision = 50.` reached while evaluating Log[Cos[(3 \[Pi])/14]^2+Sin[(3 \[Pi])/14]^2].

During evaluation of In[6]:= N::meprec: Internal precision limit $MaxExtraPrecision = 50.` reached while evaluating Log[Cos[(3 \[Pi])/14]^2+Sin[(3 \[Pi])/14]^2].

During evaluation of In[6]:= General::stop: Further output of N::meprec will be suppressed during this calculation.

Out[6]= $Aborted

For this I have filed a bug report to the effect that RSolve needs to be properly spanked.

So onto plan B. We recast the recurrence as a matrix power. Again assuming I did the translation correctly, it will be this one.

mat = {{0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 
    1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 
    0}, {0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {-1, 1, 0,
     0, 0, 0, 0, 1}};
ivec = {3, 4, 5, 8, 11, 12, 13, 19};
mexp = MatrixPower[mat, n, ivec];
simpmexp = Simplify[mexp];

Some sanity checks suggest this is the correct result. For example, simpmext[[-1]] for n->2 should give the second-next value in the sequence, 21. Likewise simpmexp[[1]] but now displaced to the n=9th next value.

In[59]:= simpmexp[[-1]] /. n -> 2.

    Out[59]= 21. + 1.19214*10^-14 I

    In[60]:= simpmexp[[1]] /. n -> 9.

    Out[60]= 21. + 6.41919*10^-15 I

So we can now work with any element of the matrix-power-times-initial-vector to see if there is an integer for n that gives the desired target value. Well, that's just root-finding. He said.

target = 132858836366993;
root = FindRoot[v1 == target, {n, 1000}, WorkingPrecision -> 2000, 
   PrecisionGoal -> 40, AccuracyGoal -> 40, MaxIterations -> 400];
root // N

During evaluation of In[91]:= FindRoot::lstol: The line search decreased the step size to within tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the merit function. You may need more than 2000.` digits of working precision to meet these tolerances.

Out[93]= {n -> 1000.}

So that failed miserably. Exit plan B stage right, plan C enters from a trapdoor in the floor. We do this in stages. (I wrote that last line before realizing it is something of a pun. Really.)

firsttry = 
  FindRoot[v1 == target/10^6, {n, 1000}, WorkingPrecision -> 2000, 
   PrecisionGoal -> 40, AccuracyGoal -> 40, MaxIterations -> 400];
secondtry = 
  FindRoot[v1 == target/10^3, {n, n /. firsttry}, 
   WorkingPrecision -> 2000, PrecisionGoal -> 40, AccuracyGoal -> 40, 
   MaxIterations -> 400];
thirdtry = 
  FindRoot[v1 == target, {n, n /. secondtry}, 
   WorkingPrecision -> 2000, PrecisionGoal -> 40, AccuracyGoal -> 40, 
   MaxIterations -> 400];

This actually succeeded. We'll take a look at what we have.

In[85]:= N[thirdtry, 30]

(* Out[85]= {n -> 5.81257409105516491553382616250*10^13} *)

Is it the correct value? Seems to be so.

In[95]:= N[v1 /. thirdtry, 40]

(* Out[95]= 1.3285883636699300000000000000000000000000*10^14 + 
 0.*10^-27 I *)

So we try rounding the root to an integer and then retrying the substitution to see if it gives the same. Not surprisingly, it does not, and that shows this target is not in the sequence.

In[87]:= guess = Round[n /. thirdtry]

(* Out[87]= 58125740910552 *)

In[89]:= N[v1 /. n -> guess, 200] // Round

(* Out[89]= 132858836366995 *)

This one is too big (could Goldilocks have said it any better?) Lets see what lies just beneath.

In[90]:= N[v1 /. n -> guess - 1, 200] // Round

(* Out[90]= 132858836366989 *)

Too small. So we bracketed the target by the two closest above and below values that actually do lie in the sequence.

POSTED BY: Daniel Lichtblau
Posted 3 years ago

Daniel,

Thank you for your reply, and maybe in some future update a function would be available to do this, or even an extension to the existing function, just a thought.

POSTED BY: Paul Cleary

Paul,

Yes, I guess there is a way, but my approach is empirical - but mathematically non-rigorous.

You can construct a matrix mat

ker = {1, 0, 0, 0, 0, 0, 1, -1};
init = {3, 4, 5, 8, 11, 12, 13, 19};
mat = DiagonalMatrix[{1, 1, 1, 1, 1, 1, 1}, 1];
mat[[8]] = Reverse@ker;
mat // MatrixForm

enter image description here

which propagates your series for one term:

mat.init
(*  Out:  {4,5,8,11,12,13,19,20}  *)

Consequently the power of this matrix propagates for e.g. 10 terms:

mp = MatrixPower[mat, 10];
mp . init
(*  Out:  {24,27,28,29,35,36,37,40}  *)

The last line of this matrix gives the respective next term, and depending on the power this line shows a certain pattern:

Last /@ Table[MatrixPower[mat, n], {n, 1, 24}] // TableForm

enter image description here

From this it is easy to deduce a simple function to check if a number is an element of the series:

seriesMemberQ[z_] := MemberQ[(z - #)/16 & /@ Rest@init, _Integer]

So, lets check numbers in the neighbourhood of your number in question:

{#, seriesMemberQ[#]} & /@ Range[132858836366990, 132858836366999] // TableForm

enter image description here

The immediate answer is: No, your number 132858836366993 is not element of the series, sorry!

POSTED BY: Henrik Schachner
Posted 3 years ago

Henrik,

Thank you for your reply, it certainly solved my problem.

POSTED BY: Paul Cleary
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract