A177922 For each composition (ordered partition) of n, remove the first part z(1) and add 1 to the next z(1) parts to get a new composition until a partition is repeated. Among all compositions of n, a(n) gives the maximum of steps needed to reach a period.

0, 2, 3, 5, 7, 9, 9, 11, 16, 18, 18, 18, 22, 28, 30, 30, 25, 29, 36, 43, 45, 45, 39, 39, 45, 53, 61, 63, 63, 56, 49, 55, 64, 73, 82, 84, 84, 76, 68, 68, 76, 86, 96, 106, 108, 99, 90, 81, 89, 100, 111, 122, 133, 135, 135, 125, 115, 105, 105, 115, 127, 139

Offset

1,2

Comments

n=4 has 2^3=8 compositions: 4; 3+1; 1+3; 1+1+2; 1+2+1: 2+1+1; 2+2; 1+1+1+1; the period is [(2+1+1),(2+2),(3+1)]; to reach the repetition from each composition one needs at most 5 steps; (1+3)->(4)->(1+1+1+1)->(2+1+1)->(2+2)->(3+1)->(2+1+1).

Links

Table of n, a(n) for n=1..62.

R. Baumann, Computer-Knobelei, , LOGIN, 163/164 (2010), 141-142 (in German).

Formula

a((k^2+k-2)/2-j) = (3k^2-3k-4)/2-(k+1)*j with 0<=j<=(k-2) div 2, for k>1.

a((k^2+k)/2) = (3k^2-3k)/2, for k>1.

a((k^2+k+2)/2) = (3k^2-3k)/2-k*j with 0<=j<=(k-3) div 2, for k>1.

a(2u^2+2u) = 4u^2+u with 1<=u and k=2u.

Example

For k=10 and j=2 the formula gives; a(52)=111; a(55)=135; a(58)=115; a(60)=105;
For n=4: (4)->(1+1+1+1)->(2+1+1)->(2+2)->(3+1) [4 steps]; (3+1)->(2+1+1)->(2+2) [2 steps]; (1+3)->(4)->(1+1+1+1)->(2+1+1)-(2+2)->(3+1) [5 steps]; (1+1+2)->(2+2)->(3+1)->(2+1+1) [3 steps]; (1+2+1)->(3+1)->(2+1+1)->(2+2) [3 steps]; (2+1+1)->(2+2)->(3+1) [2 steps]; (2+2)->(3+1)->(2+1+1) [2 steps]; (1+1+1+1)->(2+1+1)->(2+2)->(3+1) [3 steps]; so at most 5 steps are needed, a(4)=5.

Crossrefs

Sequence in context: A139790 A118784 A193889 * A102246 A089743 A080587

Adjacent sequences: A177919 A177920 A177921 * A177923 A177924 A177925

Keyword

nonn

Author

Paul Weisenhorn, Dec 16 2010

Status

approved