0
$\begingroup$

If a multiple of a prime, say 13, occurs in Sylvester's sequence, then Sylvester's sequence modulo that prime eventually gets stuck on a bunch of 1's, and FixedPoint would catch that: 2, 3, 7, 4, 0, 1, 1, 1, ... But with 5, which is 2, 3, over and over again, FixedPoint would get the system stuck on an infinite loop, right?

So how do you catch that first repeated term if the sequence enters a period of length greater than 1?

More info about Sylvester's sequence: https://oeis.org/A000058, https://oeis.org/A256147.

$\endgroup$
  • 1
    $\begingroup$ It suffices to keep track of what values have been hit. When computing a_n (which should really be defined here, not in a link), check whether it has been hit already. if so, you are headed for repeats. $\endgroup$ – Daniel Lichtblau Apr 4 '15 at 17:31
  • $\begingroup$ Maybe you can use four-argument form of NestWhile? $\endgroup$ – kglr Apr 4 '15 at 17:35
  • $\begingroup$ @kguler Something like NestWhile[Mod[#^2 - # + 1, Prime[n]], 2, MemberQ[#, I HAVE NO IDEA WHAT WOULD GO IN THIS SPOT], All]? $\endgroup$ – Robert Soupe Apr 5 '15 at 1:23
5
$\begingroup$

This is about as efficient as it gets (as D.L. said, just track seen values):

(* sequence generator *)
ClearAll[ss]
ss[0] = 2;
ss[n_] := ss[n] = ss[n - 1]^2 - ss[n - 1] + 1;

(* repeat finder *)
ssrep[mod_] := Module[{t, res, idx = 0},
  t[_] = True;
  While[t[res = Mod[ss[idx++], mod]], t[res] = False];
  {idx - 1, res}];

ssrep[Prime[#]] & /@ Range@10

(* {{2, 1}, {3, 1}, {2, 2}, {4, 1}, {4, 3}, {6, 1}, {7, 4}, {4, 2}, {7, 7}, {8, 3}} *)

Returns sequence index and value (Mod the argument - e.g., the second entries above of 1,1,2,1,3,1,4,2,7,3 are OEIS A256147 for the first ten primes)...

Be prepared for long running times / overflow / memory pressure...

$\endgroup$
2
$\begingroup$

I may have misunderstood so please correct me:

f = #^2 - # + 1 &;
s[n_] := Nest[f, 2, n - 1];
nf[n_] := 
 With[{lst = NestWhileList[Mod[f@#, n] &, 2, UnsameQ, All]}, 
  Last@lst -> 
   Grid[({Subscript["e", #], s@#} & /@ 
      Flatten@Position[lst, Last@lst]), Frame -> All]]
pnf[num_] := nf[Prime[num]]

So, looking at first ten primes:

Grid[Prepend[
  Table[{j, Prime[j], pnf[j]}, {j, 10}], {"n", "Prime[n]", 
   "Mod[\!\(\*SubscriptBox[\(e\), \(j\)]\),Prime[n]]->First \
consectuive Sylvester numbers same modulo Prime[n]"}], Frame -> All]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.