A047988 Start with n and reach 2 by repeatedly either dividing by d where d <= the square root or by adding or subtracting 1. The division steps are free, but adding or subtracting 1 costs 1 point. a(n) is the smallest cost to reach 2.

0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 0, 1, 2, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2

Offset

2,18

Links

David A. Corneth, Table of n, a(n) for n = 2..10001

David A. Corneth, PARI program

Thomas Kantke, Das Spiel Minimum und die Zerlegung natürlicher Zahlen, Mathematische Unterhaltungen, Spectrum der Wissenschaft, April 1993, pp. 11-13.

Example

From David A. Corneth, Jun 05 2020: (Start)
For n = 19 we get to 2 via
n := 19 - 1 = 2 (+1 point as we subtract 1 from n)
n := 18/3 = 6 (+0 point as we divide by a divisor)
n := 6/2 = 3 (+0 point, we divide by a divisor. we can't divide by 3 as 3 > sqrt(6)).
n := 3 - 1 = 2 (+1 point; steps end here; we have n = 2)
We earned 2 points in these steps. As this is the minimal number of points starting at n = 19, a(19) = 2. (End)

Prog

(PARI) \\ see Corneth link \\ David A. Corneth, Jun 05 2020

Crossrefs

Cf. A047836, A047984, A047985, A047986, A047987.

Cf. A048823, A048824, A048825, A048826, A048827.

Sequence in context: A037879 A178535 A025449 * A037818 A087116 A033264

Adjacent sequences: A047985 A047986 A047987 * A047989 A047990 A047991

Keyword

nonn,easy

Author

Thomas Kantke (bytes.more(AT)ibm.net)

Extensions

More terms from David W. Wilson

Status

approved