A035106 1, together with numbers of the form k*(k+1) or k*(k+2), k > 0.

1, 2, 3, 6, 8, 12, 15, 20, 24, 30, 35, 42, 48, 56, 63, 72, 80, 90, 99, 110, 120, 132, 143, 156, 168, 182, 195, 210, 224, 240, 255, 272, 288, 306, 323, 342, 360, 380, 399, 420, 440, 462, 483, 506, 528, 552, 575, 600, 624, 650, 675, 702, 728, 756, 783, 812, 840

Offset: 1

Author

N. J. A. Sloane, revised Oct 30 2001

Keywords

• nonn
• nice
• easy

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

Examples

			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.
		

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).

Crossrefs

Cf. A006446, A052938, A064764, A064796, A064797, A064817, A004652, A035104, A035107.

First differences give (essentially) A028242.

Bisections: A002378 (pronic numbers) and A005563.

Programs

GAP

Concatenation([1], List([2..60], n-> (2*n*(n+2) +3*((-1)^n -1))/8)); # G. C. Greubel, Jun 10 2019

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

Magma

[1] cat [(2*n*(n+2) +3*((-1)^n -1))/8: n in [2..60]]; // G. C. Greubel, Jun 10 2019

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 *)

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

Sage

[1]+[(2*n*(n+2) +3*((-1)^n -1))/8 for n in (2..60)] # G. C. Greubel, Jun 10 2019

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) = a(n-1) + a(n-2) - a(n-3) + 1 = A002620(n+2) + A004526(n+2). - Henry Bottomley, Mar 08 2000

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

Extensions

Edited by Max Alekseyev, Oct 09 2015

Definition modified to allow for the initial 1. - N. J. A. Sloane, May 17 2016