OFFSET
1,2
COMMENTS
Largest integer m such that every permutation (p_1, ..., p_n) of (1, ..., n) satisfies p_i * p_{i+1} >= m for some i, 1 <= i <= n-1. Equivalently, smallest integer m such that there exists a permutation (p_1, ..., p_n) of (1, ..., n) satisfying p_i * p_{i+1} <= m for every i, 1 <= i <= n-1.
Also, nonsquare positive integers m such that floor(sqrt(m)) divides m. - Max Alekseyev, Nov 27 2006
Also, for n>1, a(n) is the number of non-isomorphic simple connected undirected graphs having n+1 edges and a longest path of length n. - Nathaniel Gregg, Nov 02 2021
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).
FORMULA
For n > 1, a(n) = n*(n+2)/4 if n is even and (n-1)*(n+3)/4 if n is odd. - Jud McCranie, Oct 25 2001
a(n+2) = (2*n^2 + 12*n + 3*(-1)^n + 13)/8, with a(1)=1, i.e., a(n+2) = (n+2)*(n+4)/4 if n is even and (n+1)*(n+5)/4 if n is odd. - Vladeta Jovovic, Oct 23 2001
From Cecilia Rossiter (cecilia(AT)noticingnumbers.net), Dec 14 2004: (Start)
a(n) = a(n-2) + (n-1), where a(1) = 0, a(2) = 0.
a(n) = (2*(n+1)^2 + 3*(-1)^n - 5)/8, n>=2, with a(1)=1. (End)
For n > 1, a(n) = floor((n+1)^4/(4*(n+1)^2+1)). - Gary Detlefs, Feb 11 2010
For n > 1, a(n) = n + ceiling((1/4)*(n-1)^2) - 1. - Clark Kimberling, Jan 07 2011; corrected by Arkadiusz Wesolowski, Sep 25 2012
a(1)=1, a(2)=2, a(3)=3, a(4)=6, a(5)=8; for n > 5, a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4). - Harvey P. Dale, May 03 2012
G.f.: x + x^2*(2-x) / ( (1+x)*(1-x)^3 ) = x*(x^4 - 2*x^3 + x^2 - 1)/((x-1)^3*(x+1)). - Vladeta Jovovic, Oct 23 2001; Harvey P. Dale, May 03 2012
a(n) = floor(n/2)*(1 + ceiling(n/2)), a(1) = 1. - Arkadiusz Wesolowski, Sep 25 2012
a(n) = ceiling((n-1)*(n+3)/4), n > 1. - Wesley Ivan Hurt, Jun 14 2013
a(n+1) - a(n) = A052938(n-2) for n > 1. - Reinhard Zumkeller, Oct 06 2015
E.g.f.: (8*x + 3*exp(-x) - (3-6*x-2*x^2)*exp(x))/8. - G. C. Greubel, Jun 10 2019
Sum_{n>=1} 1/a(n) = 11/4. - Amiram Eldar, Sep 24 2022
EXAMPLE
n=5: we must arrange the numbers 1..5 so that the max of the products of pairs of adjacent terms is minimized. The answer is 51324, with max product = 8, so a(5) = 8.
MATHEMATICA
Join[{1}, LinearRecurrence[{2, 0, -2, 1}, {2, 3, 6, 8}, 60]] (* or *) Join[{1}, Table[ If[EvenQ[n], (n(n+2))/4, ((n-1)(n+3))/4], {n, 2, 60}]] (* Harvey P. Dale, May 03 2012 *)
PROG
(Haskell)
import Data.List.Ordered (union)
a035106 n = a035106_list !! (n-1)
a035106_list = 1 : tail (union a002378_list a005563_list)
-- Reinhard Zumkeller, Oct 05 2015
(PARI) my(x='x+O('x^60)); Vec(x*(x^4-2*x^3+x^2-1)/((x-1)^3*(x+1))) \\ Altug Alkan, Oct 23 2015
(PARI) A035106(n)=!(n-1)+floor((n^2)/4+n/2); \\ R. J. Cano, Jul 24 2023
(Magma) [1] cat [(2*n*(n+2) +3*((-1)^n -1))/8: n in [2..60]]; // G. C. Greubel, Jun 10 2019
(Sage) [1]+[(2*n*(n+2) +3*((-1)^n -1))/8 for n in (2..60)] # G. C. Greubel, Jun 10 2019
(GAP) Concatenation([1], List([2..60], n-> (2*n*(n+2) +3*((-1)^n -1))/8)); # G. C. Greubel, Jun 10 2019
CROSSREFS
First differences give (essentially) A028242.
KEYWORD
nonn,nice,easy
AUTHOR
N. J. A. Sloane, revised Oct 30 2001
EXTENSIONS
Edited by Max Alekseyev, Oct 09 2015
Definition modified to allow for the initial 1. - N. J. A. Sloane, May 17 2016
STATUS
approved