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.

4, 9, 7, 20, 6, 33, 13, 23, 16, 62, 8, 75, 18, 17, 25

Offset: 2

Author

Gordon Hamilton, Mar 17 2015

Keywords

• nonn
• more
• nice

Comments

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.

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

Jon E. Schoenfield confirms a(14) and a(15) and finds the following:

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

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

From Jon E. Schoenfield, Apr 03 2015: (Start)

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:

.

n a(n) solution in a(n) steps

-- ---- ----------------------

2 4 Nr+

3 9 NNr++

4 7 Nr++

5 20 NrNNr+++

6 6 +++r++ (no 6-step solution can begin with N)

7 33 NrNNrNr++

8 13 Nr++++

9 23 NrNr+++

10 16 Nr+++++

11 62 NrNrNNrNr+++

12 8 ++++r+++ (no 8-step solution can begin with N)

(End)

From Chai Wah Wu, Apr 09 2015: (Start)

Restricting to the type of solutions above leads to the following minimal solutions for prime n:

13 75 NrNrNrNrNr+++++

17 111 NrNNrNNrNr+++++

19 126 NrNNrNrNrNr+++++++

23 171 NrNrNrNNNrNr+++++

29 217 NrNrNrNrNNrNr++++++++

31 235 NrNNrNrNrNrNr++++++++++++

37 310 NrNrNrNrNNNrNr++++++++

...

211 2586 NrNrNNrNNrNrNrNNNrNr++++++++++++++++++++++++++++++++++++++++++++++

223 2750 NrNNNrNrNrNrNNrNNrNr++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

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.

(End)

From Jon E. Schoenfield, Apr 11 2015: (Start)

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].

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.

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

a(2^k) = 3 * 2^(k-1) + 1,

a(3^k) = 7 * 3^(k-1) + 2,

a(5^k) = 17 * 5^(k-1) + 3,

a(7^k) = 30 * 7^(k-1) + 3,

a(11^k) = 58 * 11^(k-1) + 4,

a(13^k) = 70 * 13^(k-1) + 5,

a(17^k) = 107 * 17^(k-1) + 4;

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.

(End)

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

Examples

			a(2) = 4 because 1 -> 3/2 -> 2 -> 1/2 -> 1 using four steps (addition, addition, reciprocal, addition).
		

Links

• OEIS Wiki, Report on Integer Sequences K-12 Conference
• Jon E. Schoenfield, 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

Extensions

a(13)-a(16) from Jon E. Schoenfield, Apr 20 2015