2,1

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 (checkman(AT)mathi17.la.asu.edu), 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.'"

T. D. Noe, Table of n, a(n) for n=2..1000

Max Alekseyev, Proof that A001000 and A071111 are essentially the same sequence

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?

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.

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

Sequence in context: A067567 A104294 A137270 this_sequence A038929 A070806 A003424

Adjacent sequences: A071108 A071109 A071110 this_sequence A071112 A071113 A071114

nonn,nice

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

Edited by Dean Hickerson (dean(AT)math.ucdavis.edu) and Robert G. Wilson v (rgwv(AT)rgwv.com), Jun 04 2002