Repository: sympy/sympy

Issue:
`cycle_length` documentation / behaviour mismatch
Documentation reads

> The sequence is started with value `x0`

but the examples (including in the docstring for `pollard_rho`), implementation, and tests all use the sequence

$f(x_0), f(f(x_0)), \dots$

I think either the documentation should read "The sequence is started with value `f(x0)`", or the examples, implementation, and tests should be tweaked to match the behaviour of Brent's method as described in the cited Wikipedia article. Personally I'm inclined to the latter, as the hack to adjust `mu` at the end of `cycle_length` is a bit unlovely, and I was expecting consistency with the article, but that would change the way the method has behaved since a decade. Also, I'd be happy to create a PR, but I'm new to contributing, so thought I'd ask which fix is preferred!

Discussion:

Patch:
diff --git a/.mailmap b/.mailmap
index 34ec491296..6b0847bc2b 100644
--- a/.mailmap
+++ b/.mailmap
@@ -468,6 +468,7 @@ Colleen Lee <colleenclee@gmail.com> <clee@coursera.org>
 Comer Duncan <comer.duncan@gmail.com>
 Congxu Yang <u7189828@anu.edu.au>
 Constantin Mateescu <costica1234@me.com>
+Corey Cerovsek <corey@cerovsek.com>
 Costor <pcs2009@web.de>
 Craig A. Stoudt <craig.stoudt@gmail.com>
 Cristian Di Pietrantonio <cristiandipietrantonio@gmail.com>
diff --git a/sympy/ntheory/factor_.py b/sympy/ntheory/factor_.py
index 12a1083ab9..704406ec95 100644
--- a/sympy/ntheory/factor_.py
+++ b/sympy/ntheory/factor_.py
@@ -638,20 +638,21 @@ def pollard_rho(n, s=2, a=1, retries=5, seed=1234, max_steps=None, F=None):
     >>> for s in range(5):
     ...     print('loop length = %4i; leader length = %3i' % next(cycle_length(F, s)))
     ...
-    loop length = 2489; leader length =  42
-    loop length =   78; leader length = 120
-    loop length = 1482; leader length =  99
-    loop length = 1482; leader length = 285
+    loop length = 2489; leader length =  43
+    loop length =   78; leader length = 121
     loop length = 1482; leader length = 100
+    loop length = 1482; leader length = 286
+    loop length = 1482; leader length = 101
 
-    Here is an explicit example where there is a two element leadup to
+    Here is an explicit example where there is a three element leadup to
     a sequence of 3 numbers (11, 14, 4) that then repeat:
 
     >>> x=2
     >>> for i in range(9):
-    ...     x=(x**2+12)%17
     ...     print(x)
+    ...     x=(x**2+12)%17
     ...
+    2
     16
     13
     11
@@ -660,11 +661,10 @@ def pollard_rho(n, s=2, a=1, retries=5, seed=1234, max_steps=None, F=None):
     11
     14
     4
-    11
     >>> next(cycle_length(lambda x: (x**2+12)%17, 2))
-    (3, 2)
+    (3, 3)
     >>> list(cycle_length(lambda x: (x**2+12)%17, 2, values=True))
-    [16, 13, 11, 14, 4]
+    [2, 16, 13, 11, 14, 4]
 
     Instead of checking the differences of all generated values for a gcd
     with n, only the kth and 2*kth numbers are checked, e.g. 1st and 2nd,
diff --git a/sympy/ntheory/generate.py b/sympy/ntheory/generate.py
index b03af55fe4..03d3de013d 100644
--- a/sympy/ntheory/generate.py
+++ b/sympy/ntheory/generate.py
@@ -929,11 +929,10 @@ def cycle_length(f, x0, nmax=None, values=False):
 
     This will yield successive values of i <-- func(i):
 
-        >>> def iter(func, i):
+        >>> def gen(func, i):
         ...     while 1:
-        ...         ii = func(i)
-        ...         yield ii
-        ...         i = ii
+        ...         yield i
+        ...         i = func(i)
         ...
 
     A function is defined:
@@ -943,23 +942,23 @@ def cycle_length(f, x0, nmax=None, values=False):
     and given a seed of 4 and the mu and lambda terms calculated:
 
         >>> next(cycle_length(func, 4))
-        (6, 2)
+        (6, 3)
 
     We can see what is meant by looking at the output:
 
-        >>> n = cycle_length(func, 4, values=True)
-        >>> list(ni for ni in n)
-        [17, 35, 2, 5, 26, 14, 44, 50, 2, 5, 26, 14]
+        >>> iter = cycle_length(func, 4, values=True)
+        >>> list(iter)
+        [4, 17, 35, 2, 5, 26, 14, 44, 50, 2, 5, 26, 14]
 
-    There are 6 repeating values after the first 2.
+    There are 6 repeating values after the first 3.
 
     If a sequence is suspected of being longer than you might wish, ``nmax``
     can be used to exit early (and mu will be returned as None):
 
         >>> next(cycle_length(func, 4, nmax = 4))
         (4, None)
-        >>> [ni for ni in cycle_length(func, 4, nmax = 4, values=True)]
-        [17, 35, 2, 5]
+        >>> list(cycle_length(func, 4, nmax = 4, values=True))
+        [4, 17, 35, 2]
 
     Code modified from:
         https://en.wikipedia.org/wiki/Cycle_detection.
@@ -970,7 +969,9 @@ def cycle_length(f, x0, nmax=None, values=False):
     # main phase: search successive powers of two
     power = lam = 1
     tortoise, hare = x0, f(x0)  # f(x0) is the element/node next to x0.
-    i = 0
+    i = 1
+    if values:
+        yield tortoise
     while tortoise != hare and (not nmax or i < nmax):
         i += 1
         if power == lam:   # time to start a new power of two?
@@ -997,8 +998,6 @@ def cycle_length(f, x0, nmax=None, values=False):
             tortoise = f(tortoise)
             hare = f(hare)
             mu += 1
-        if mu:
-            mu -= 1
         yield lam, mu
 
 


Test patch:
diff --git a/sympy/ntheory/tests/test_generate.py b/sympy/ntheory/tests/test_generate.py
index 540925caee..e487b89686 100644
--- a/sympy/ntheory/tests/test_generate.py
+++ b/sympy/ntheory/tests/test_generate.py
@@ -232,12 +232,12 @@ def test_generate():
     assert mr(1, [2]) is False
 
     func = lambda i: (i**2 + 1) % 51
-    assert next(cycle_length(func, 4)) == (6, 2)
+    assert next(cycle_length(func, 4)) == (6, 3)
     assert list(cycle_length(func, 4, values=True)) == \
-        [17, 35, 2, 5, 26, 14, 44, 50, 2, 5, 26, 14]
+        [4, 17, 35, 2, 5, 26, 14, 44, 50, 2, 5, 26, 14]
     assert next(cycle_length(func, 4, nmax=5)) == (5, None)
     assert list(cycle_length(func, 4, nmax=5, values=True)) == \
-        [17, 35, 2, 5, 26]
+        [4, 17, 35, 2, 5]
     sieve.extend(3000)
     assert nextprime(2968) == 2969
     assert prevprime(2930) == 2927