A071111 a(n) is the least integer x such that there exists an integer in the open interval (x/(i+1), x/i) for i= n-1, n-2 ..., 3, 2, 1.

3, 5, 7, 13, 17, 26, 31, 43, 57, 65, 82, 101, 111, 133, 157, 183, 197, 226, 257, 290, 307, 343, 381, 421, 463, 485, 530, 577, 626, 677, 703, 757, 813, 871, 931, 993, 1025, 1090, 1157, 1226, 1297, 1370, 1407, 1483, 1561, 1641, 1723, 1807, 1893, 1937, 2026, 2117

Offset: 2

Author

Fernando Delgado, Paul Monasterios, and Adolfo Rodriguez (misterioso53(AT)hotmail.com), May 27 2002

Keywords

• nonn
• nice

Comments

a(10) = 57, a(100) = 8191, a(1000) = 937993.

a(n) is the least integer that for k=1, 2, ..., (n-1) can be expressed as: a(n)=p*k + b for some positive integers p and b such that p>1 and p>b>0.

This is the same sequence (apart from the initial term) as A001000. The identity of these two sequences was first proved by Rustem Aidagulov and a detailed version of the proof can be found in the Alekseyev link below.

Comments from Christopher Carl Heckman, May 23 2004: "This problem was given in Crux Mathematicorum, Vol. 23 #6 (October 1997) as Problem #2272. A solution, which includes a general formula, can be found in Crux Mathematicorum, Vol. 24 #7 (November 1998): a(n) = floor (((n + x_n) / 2)^2 + 1), where x_n = floor (n + 1 - 2 sqrt (n - 1)).

"This formula was found by Florian Herzig (then a student at Cambridge, UK), who also proved that the proposer's conjecture that a(n) = cases (1 + (n-m)^2, if m^2 <= n - 2, 1 + (n-m)^2 + (n - m), otherwise) where m = floor ((1 + sqrt (4 n - 7)) / 2) also is true although 'the proof of this fact is quite challenging'.

"The problem was also solved by Peter Tingley (then an undergraduate student at the University of Waterloo, Waterloo, Ontario), who gave the alternate formula: a(n) = n y_n + floor ((n - y_n)^2 / 4 + 1), where y_n = floor (n - 2 sqrt(n - 1) + 1), which 'is readily seen to be the same as the one obtained by Herzig.'"

Examples

			a(4)=7 because 2 lies in (7/4,7/3), 3 lies in (7/3,7/2) and 4, 5 and 6 lie in (7/2,7) and for x<7 the definition doesn't hold.
		

Links

• T. D. Noe, Table of n, a(n) for n=2..1000
• Max Alekseyev, Proof that A001000 and A071111 are essentially the same sequence
• Florian Herzig and Peter Tingley, Solutions to Problem 2272, Crux Mathematicorum 24:7 (1998), pp. 438-441.

Programs

Mathematica

test[x_, n_] := Module[{k}, For[k=n, x<=k(k-1), k--, If[Ceiling[x/(k-1)]-Floor[x/k]<2, Return[False]]]; True]; a[n_] := For[x=1, True, x++, If[test[x, n], Return[x]]]

Formula

For 2<=n<=200, a(n) = n^2 - n*c(n) + floor(c(n)^2/4) + 1, where c(n) = floor(sqrt(4n-5)). Is this true for all n>=2?

Extensions

Edited by Dean Hickerson and Robert G. Wilson v, Jun 04 2002