cp's OEIS Frontend

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.

%I A071111 #18 Jul 25 2025 12:17:42
%S A071111 3,5,7,13,17,26,31,43,57,65,82,101,111,133,157,183,197,226,257,290,
%T A071111 307,343,381,421,463,485,530,577,626,677,703,757,813,871,931,993,1025,
%U A071111 1090,1157,1226,1297,1370,1407,1483,1561,1641,1723,1807,1893,1937,2026,2117
%N 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.
%C A071111 a(10) = 57, a(100) = 8191, a(1000) = 937993.
%C A071111 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.
%C A071111 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.
%C A071111 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)).
%C A071111 "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'.
%C A071111 "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.'"
%H A071111 T. D. Noe, <a href="/A071111/b071111.txt">Table of n, a(n) for n=2..1000</a>
%H A071111 Max Alekseyev, <a href="/A071111/a071111.txt">Proof that A001000 and A071111 are essentially the same sequence</a>
%H A071111 Florian Herzig and Peter Tingley, <a href="https://cms.math.ca/wp-content/uploads/crux-pdfs/CRUXv24n7.pdf">Solutions to Problem 2272</a>, Crux Mathematicorum 24:7 (1998), pp. 438-441.
%F A071111 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?
%e A071111 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.
%t A071111 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]]]
%K A071111 nonn,nice
%O A071111 2,1
%A A071111 Fernando Delgado, Paul Monasterios, and Adolfo Rodriguez (misterioso53(AT)hotmail.com), May 27 2002
%E A071111 Edited by _Dean Hickerson_ and _Robert G. Wilson v_, Jun 04 2002