cp's OEIS Frontend

A256174 Boomerang Fractions: Starting with 1, on the first step add 1/n, and on subsequent steps either add 1/n or take the reciprocal. a(n) = minimal number of steps needed to return to 1.

%I A256174 #66 Jul 14 2019 22:22:03
%S A256174 4,9,7,20,6,33,13,23,16,62,8,75,18,17,25
%N A256174 Boomerang Fractions: Starting with 1, on the first step add 1/n, and on subsequent steps either add 1/n or take the reciprocal. a(n) = minimal number of steps needed to return to 1.
%C A256174 _David W. Wilson_ suggested this question. It was worked on at the Integer Sequences K-12 conference (Feb 27 - Mar 01 2015) by _Joshua Zucker_, Amanda Serenevy and _R. K. Guy_. It is an elegant sequence to have students play with fractions.
%C A256174 At that event, the sequence was calculated with conjectures for the 11th and 13th terms: 4, 9, 7, 20, 6, 33, 13, 23, 16, 62?, 8, 75?, 18, 17, 25. - _Gordon Hamilton_, Apr 02 2015
%C A256174 Jon E. Schoenfield confirms a(14) and a(15) and finds the following:
%C A256174 a(18) = 16, a(20) = 10, a(24) = 15, a(30) = 12, a(40) = 19, a(42) = 14, a(56) = 16, a(72) = 18. - _Gordon Hamilton_, Apr 02 2015
%C A256174 Additional values: a(35) = 25, a(48) = 29. Upper bounds: a(n) <= n^2. Add n(n-1) times, take the reciprocal and add n-1 times. a(bc) <= c(b^2-1) + 1. Add n(b-1) times, take the reciprocal and add (b-1)c times. For c > b, a(bc) <= c^2- b^2 + 1. Add c(c-b) times, take the reciprocal and add (c-b)b times. In particular, for n = b(b+1), a(n) <= 2(b+1). The minimum of these bounds give a(n) for n = 2, 3, 4, 6, 8, 10, 12, 15, 20, 30, 35, 42, 48, 56, 72, 90, 110, 132. Exhaustive search show that a(b*(b+1)) = 2(b+1) for b <= 12 which seems to support the conjecture that this is true for all b. - _Chai Wah Wu_, Apr 02 2015
%C A256174 From _Jon E. Schoenfield_, Apr 03 2015: (Start)
%C A256174 It appears that, for many values of n, there exists a solution that uses the minimal number of steps and uses an exact multiple of n "add 1/n" steps before each "take the reciprocal" step. E.g., let the characters "N", "r", and "+" denote, respectively, exactly n consecutive "add 1/n" steps, a single "take the reciprocal" step, and a single "add 1/n" step; then solutions in a(n) steps for n = 2..12 include the following:
%C A256174 .
%C A256174    n a(n) solution in a(n) steps
%C A256174   -- ---- ----------------------
%C A256174    2    4 Nr+
%C A256174    3    9 NNr++
%C A256174    4    7 Nr++
%C A256174    5   20 NrNNr+++
%C A256174    6    6 +++r++ (no 6-step solution can begin with N)
%C A256174    7   33 NrNNrNr++
%C A256174    8   13 Nr++++
%C A256174    9   23 NrNr+++
%C A256174   10   16 Nr+++++
%C A256174   11   62 NrNrNNrNr+++
%C A256174   12    8 ++++r+++ (no 8-step solution can begin with N)
%C A256174 (End)
%C A256174 From _Chai Wah Wu_, Apr 09 2015: (Start)
%C A256174 Restricting to the type of solutions above leads to the following minimal solutions for prime n:
%C A256174   13   75 NrNrNrNrNr+++++
%C A256174   17  111 NrNNrNNrNr+++++
%C A256174   19  126 NrNNrNrNrNr+++++++
%C A256174   23  171 NrNrNrNNNrNr+++++
%C A256174   29  217 NrNrNrNrNNrNr++++++++
%C A256174   31  235 NrNNrNrNrNrNr++++++++++++
%C A256174   37  310 NrNrNrNrNNNrNr++++++++
%C A256174   ...
%C A256174 211 2586 NrNrNNrNNrNrNrNNNrNr++++++++++++++++++++++++++++++++++++++++++++++
%C A256174 223 2750 NrNNNrNrNrNrNNrNNrNr++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
%C A256174 Upper bound for a(n): For c, d divisors of n such that c < d, the following solution will take n(d/c - c/d)+1 steps: add n(d/c - 1) times, take 1 reciprocal step, then add n(1 - c/d) times. Since we can factor out gcd(c,d) without affecting the ratio d/c, without loss of generality we can assume that c and d are coprime, in which case the number of steps is (n/dc)*(d^2 - c^2)+1. For prime n, c = 1 and d = n and we get n^2 as the bound. It can be shown that all solutions with one reciprocal step are of this form, so we can find the minimal solution with one reciprocal step by minimizing among divisors c, d of n such that d*c divides n. Thus for n = b(b+1), the minimal solution with 1 reciprocal step has 2(b+1) steps.
%C A256174 (End)
%C A256174 From _Jon E. Schoenfield_, Apr 11 2015: (Start)
%C A256174 Minimizing the total number of steps under the additional constraint that the number of consecutive "add 1/n" steps immediately before each "take the reciprocal" step must be a multiple of n gives the following upper bound on a(n) for n in [2..13]: 4, 9, 7, 20, 10, 33, 13, 23, 16, 62, 19, 75. Note that these values match the known exact values of a(n) at n = 2, 3, 4, 5, 7, 8, 9, 10, and 11, as well as the conjectured value at n = 13. See the Links for a file giving the value of this upper bound, and a solution at that number of steps, for all n in [2..10000].
%C A256174 Conjecture: For all prime values of n, a(n) is exactly the minimal number of steps to return to 1 under the added constraint that the number of consecutive "add 1/n" steps immediately before each "take the reciprocal" step must be a multiple of n.
%C A256174 A stronger conjecture: The above conjecture applies not only when n is prime, but also when n is a prime power. If this is true, then it appears that
%C A256174      a(2^k)  =   3 *  2^(k-1) + 1,
%C A256174      a(3^k)  =   7 *  3^(k-1) + 2,
%C A256174      a(5^k)  =  17 *  5^(k-1) + 3,
%C A256174      a(7^k)  =  30 *  7^(k-1) + 3,
%C A256174      a(11^k) =  58 * 11^(k-1) + 4,
%C A256174      a(13^k) =  70 * 13^(k-1) + 5,
%C A256174      a(17^k) = 107 * 17^(k-1) + 4;
%C A256174 that these have minimal solutions using 1, 2, 3, 3, 4, 5, and 4 "take the reciprocal" steps, respectively (see Links); and that similar forms apply for powers of larger primes.
%C A256174 (End)
%C A256174 If the above conjectures about a(n) where n is a prime or prime power are correct, then a(17)..a(49) are 111, 16, 126, 10, 29, 34, 171, 15, 88, 40, 65, 27, 217, 12, 235, 49, 66, 52, 25, 22, 310, 58, 31, 19, 345, 14, 362, 66, 49, 70, 396, 29, 213; a(50) seems very likely to be 73. - _Jon E. Schoenfield_, Apr 20 2015
%H A256174 OEIS Wiki, <a href="http://oeis.org/wiki/Integer_Sequence_K-12_(Banff,_2015)">Report on Integer Sequences K-12 Conference</a>
%H A256174 Jon E. Schoenfield, <a href="/A256174/a256174_1.txt">Upper bound on a(n) (and a corresponding solution) under the additional constraint that the number of consecutive "add 1/n" steps immediately before each "take the reciprocal" step must be a multiple of n, for n = 2..10000</a>
%e A256174 a(2) = 4 because 1 -> 3/2 -> 2 -> 1/2 -> 1 using four steps (addition, addition, reciprocal, addition).
%K A256174 nonn,more,nice
%O A256174 2,1
%A A256174 _Gordon Hamilton_, Mar 17 2015
%E A256174 a(13)-a(16) from _Jon E. Schoenfield_, Apr 20 2015