A340745 a(n) is the number of "add the square" iterations required to reach or exceed 1 starting at 1/n.

0, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70

Offset

1,2

Comments

For a given n > 0, let t(0) = 1/n and t(k) = t(k-1) + t(k-1)^2 for k > 0. Then a(n) is the smallest k such that t(k) >= 1.

For large n, the sequence of rational fractions {t(0), t(1), t(2), ...} = {1/n, 1/n + (1/n)^2, 1/n + (1/n)^2 + (1/n + (1/n)^2)^2, ...} begins growing slightly faster than the linear-growth sequence {1/n, 1/n + 1/n^2, 1/n + 2/n^2, 1/n + 3/n^2, ...}, which would reach 2/n in n steps; {t(0), t(1), t(2), ...} reaches nearly 2/n in n/2 steps, then nearly doubles again to 4/n in the next n/4 steps, etc., so reaching 1 requires a little more than n/2 + n/4 + n/8 + ... = n steps.

For the smallest k such that a(n) - k = n, see A340825.

Truncating the expansion given in the Formula section to just ceiling(n + log(n) + c0) gives the correct value of a(n) except at certain values of n at which log(n) + c0 is slightly less than an integer, namely, n = 10, 206, 1524, 11261, 30611, 226188, 614843, 33569293, 91250800, 674257283, 1832821321, 4982124892, 5463563356246, 14851504989918, 40370576139364, ..., where it instead gives a(n) - 1.

Conjecture: a(n) = ceiling(n + log(n) + c0 + (1/2)/n) for all n > 1.

Links

Table of n, a(n) for n=1..67.

Formula

For n > 1, a(n) = ceiling(n + log(n) + c0 + (1/2)/n - (1/3)/n^2 + ...) (see A340825), where c0 = -1.329122322... (A340875).

Example

a(1)=0 since the starting value 1/n = 1/1 = 1 is already at 1.
a(2)=2 since we have t(0) = 1/2, t(1) = 1/2 + (1/2)^2 = 3/4, and t(2) = 3/4 + (3/4)^2 = 21/16 > 1.
a(4)=5 since we have t(0) = 1/4 = 0.25, t(1) = 0.3125, t(2) = 0.4101..., t(3) = 0.5783..., t(4) = 0.9129..., t(5) = 1.7463... > 1.
a(28)=31 since we have t(0) = 1/28 = 0.0357..., t(1) = 0.0369..., ..., t(30) = 0.9884..., t(31) = 1.9655... > 1.

Prog

(PARI) a(n) = {my(t=1./n, k=0); while(t < 1, t += t^2; k++; ); k; } \\ Michel Marcus, Jan 19 2021

Crossrefs

Cf. A340824 (complement of this sequence), A340825, A340844, A340845, A340875.

Sequence in context: A074137 A206027 A039222 * A183295 A029927 A047334

Adjacent sequences: A340742 A340743 A340744 * A340746 A340747 A340748

Keyword

nonn

Author

Jon E. Schoenfield, Jan 18 2021

Status

approved