KIMBERLING'S EXPULSION ARRAY

Recurrence Relation:

$K(i,j)=\left\{{\begin{array}{ll}i+j-1&{\mbox{if }}(j\geq 2i-3)\\\\K(i-1,i-1-{\frac {j}{2}})&{\mbox{if }}j{\text{ is Even and }}(j<2i-3)\\\\K(i-1,i+{\frac {j-1}{2}})&{\mbox{if }}j{\text{ is Odd and }}(j<2i-3)\\\\\end{array}}\right.$

$\displaystyle K(i)=K(i,i)$

Bounds and Formulas:

L is the K inverse function:

$\displaystyle L(K(n))=n$

$\displaystyle K(L(n))=n$

$K(i)\leq 3i-4;(i\geq 3)$

$K(i)\leq 3i-7;(i\geq 9)$

$\displaystyle L(n)\geq {\bigg \lfloor }{\frac {n+4}{3}}{\bigg \rfloor }$

$\displaystyle K({\bigg \lfloor }{\frac {n+4}{3}}{\bigg \rfloor },{\bigg \lfloor }{\frac {2n+1}{3}}{\bigg \rfloor })=n$

Maximum value on the Lower Shuffle Part:

$A(i)=Max(K(i,1),K(i,2),\cdots ,K(i,i))$

$K(i)\leq A(i)$

$A(i)=1+3(i-\lambda (i))-{\bigg \lfloor }{\frac {i+2}{2^{\lambda (i)}}}{\bigg \rfloor }$

$\lambda (i)={\bigg \lfloor }\log _{2}{{\bigg (}{\frac {i+2}{3}}}{\bigg )}{\bigg \rfloor }$

New Sequence A175312

Particular values for K:

$\displaystyle \theta (k)=\sum _{i=0}^{k-1}{2^{\lfloor i/3\rfloor }}$

$\displaystyle K(\theta (k))=A(\theta (k))=3\cdot \theta (k)-(k+1)$

Computing Sequences:

A007063: Main diagonal of Kimberling's expulsion array:

$\displaystyle K(n)=A007063(n)$

Mathematica: A007063

K[i_, j_] := i + j - 1 /; (j >= 2 i - 3);
K[i_, j_] := K[i - 1, i - (j + 2)/2] /; (EvenQ[j] && (j < 2 i - 3));
K[i_, j_] := K[i - 1, i + (j - 1)/2] /; (OddQ[j] && (j < 2 i - 3));
K[i_] := K[i] = K[i, i]; SetAttributes[K, Listable];
A007063[i_]:=K[i];

Pari/GP: A007063

\\ Kimberling Expulsion Array
K(i,j) =
{
my(i1,j1);
i1=i;
j1=j;
while(j1<(2*i1-3),
	if(j1%2,
	j1=i1+((j1-1)/2),
	j1=i1-((j1+2)/2)
	);
	i1--;
);
return(i1+j1-1);
}
A007063(i)=K(i,i);

A006852: Step at which n is expelled in Kimberling's puzzle

$\displaystyle L(n)=A006852(n)$

Mathematica: A006852

L[n_] := L[n] = ( 
   	i = Floor[(n + 4)/3];
   	j = Floor[(2*n + 1)/3];
   	While[(i != j), j = Max[2*(i - j), 2*(j - i) - 1]; i++];
       Return[i];
       )
A006852[n_] := L[n]

Pari/GP: A006852

\\A006852: Step at which n is expelled in Kimberling's puzzle 
L(n)=
{
my(i,j);
i=floor((n+4)/3);
j=floor((2*n+1)/3);
while((i!=j),
     j=max(2*(i-j),2*(j-i)-1);
     i++;
);
return(i);
}
A006852(n)=L(n);

Counterexample Found?

Element never expulsed:

$L(3330)=+\infty ?$

Pari/GP Program:

L3330(w)=
{
my(i,j,n);
n=3330;
i=floor((n+4)/3);
j=floor((2*n+1)/3);
while((i!=j),
     j=max(2*(i-j),2*(j-i)-1);
     i++;
     if(!(i%10000000),
       	write("3330.txt",i" "j);
      		print(i" "j)
      		);
);
return(i);

Search History:

**K(i,j)=3330**
Date:	i	j
04/March/2010	3610000000	6194024295
05/March/2010	15100000000	25674482259
07/March/2010	46710000000	13464271446
08/March/2010	74940000000	118678836420
09/March/2010	117130000000	151697044688
11/March/2010	165410000000	182337709889
13/March/2010	195770000000	354148040880
17/March/2010	244230000000	138151214306
22/March/2010	267793599431	267793599431

$\displaystyle L(3330)=267793599431$

**Largest Values for n<12500**
n	L(n)
12339	>1879280000000
3330	267793599431
9756	113896793310
5910	8919080271
6859	8629373155
3807	6172570365
7113	4404762916
5373	1790316538
9764	1328203761
8444	1177386991
4502	1023177339

$\displaystyle K(1879280000000,1198916588307)=12339$

A035486: Kimberling's expulsion array read by antidiagonals.

Mathematica: A035486

K[i_, j_] := i + j - 1 /; (j >= 2 i - 3);
K[i_, j_] := K[i - 1, i - (j + 2)/2] /; (EvenQ[j] && (j < 2 i - 3));
K[i_, j_] := K[i - 1, i + (j - 1)/2] /; (OddQ[j] && (j < 2 i - 3));
K[i_] := K[i] = K[i, i]; SetAttributes[K, Listable];
T[n_] := n*(n + 1)/2;
S[n_] := Floor[1/2 + Sqrt[2 n}};
j[n_] := 1 + T[S[n}} - n;
i[n_] := 1 + S[n] - j[n];
A035486[n_] := K[i[n], j[n}};

Pari/GP: A035486

\\ Kimberling Expulsion Array
K(i,j) =
{
my(i1,j1);
i1=i;
j1=j;
while(j1<(2*i1-3), 
       if(j1%2,
       j1=i1+((j1-1)/2),
       j1=i1-((j1+2)/2)
       );
       i1--;
);
return(i1+j1-1);
S(n)=floor(1/2+sqrt(2*n));
T(n)=n*(n+1)/2
j(n)=1+T(S(n))-n;
i(n)=1+S(n)-j(n);
A035486(n)=K(i(n),j(n));

A175312: Maximum value on Lower Shuffle Part of Kimberling's Expulsion Array A035486

Mathematica: A175312

(*  A175312: By the Formula *)
\[Lambda][n_] := Floor[Log[2, (n + 2)/3}};
A175312[n_] := 
1 + 3*(n - \[Lambda][n]) - Floor[(n + 2)/(2^\[Lambda][n])]

(* A175312: By direct computation *)
K[i_, j_] := i + j - 1 /; (j >= 2 i - 3);
K[i_, j_] := K[i - 1, i - (j + 2)/2] /; (EvenQ[j] && (j < 2 i - 3));
K[i_, j_] := K[i - 1, i + (j - 1)/2] /; (OddQ[j] && (j < 2 i - 3));
K[i_] := K[i] = K[i, i]; SetAttributes[K, Listable];
A175312[n_] := Max[Table[K[n, i], {i, 1, n}}}

Pari/GP: A175312

\\A175312:  Maximum value on Lower Shuffle Part of Kimberling's Expulsion Array 
lambda(n)= floor(log((n + 2)/3)/log(2));
A175312(n)= 1 + 3*(n - lambda(n)) - floor((n + 2)/(2^lambda(n)));

A035505: Active part of Kimberling' s expulsion array as a triangular array

Mathematica: A035505

This code is based on sequences of rows and columns given by A000194 and A074294

A000194[n_] := Floor[(1 + Sqrt[4 n - 3])/2];
A074294[n_] := n - 2*Binomial[Floor[1/2 + Sqrt[n}}, 2]
K[i_, j_] := i + j - 1 /; (j >= 2 i - 3);
K[i_, j_] := K[i - 1, i - (j + 2)/2] /; (EvenQ[j] && (j < 2 i - 3));
K[i_, j_] := K[i - 1, i + (j - 1)/2] /; (OddQ[j] && (j < 2 i - 3));
K[i_] := K[i] = K[i, i]; SetAttributes[K, Listable];
A035505[n_] := K[A000194[n] + 2, A074294[n}};

Pari/GP: A035505

\\A035505: Active part of Kimberling' s expulsion array as a triangular array 
A000194(n)=floor((1+sqrt(4*n-3))/2);
A074294(n)=n-2*binomial(floor(1/2+sqrt(n)),2);
A035505(n)=K(A000194(n)+2,A074294(n));

A038807: Future of the smallest-perizeroin komet in Kimberling's expulsion array

Mathematica: A038807

A038807[1] := 2;
A038807[n_] := A007063[A038807[n - 1]];

A356026: Main diagonal of right-and-left variant of Kimberling expulsion array, A007063.

$K_{L}(i,j)=\left\{{\begin{array}{ll}i+j-1&{\mbox{if }}(j\geq 2i-3)\\\\K_{L}(i-1,i+{\frac {j-2}{2}})&{\mbox{if }}j{\text{ is Even and }}(j<2i-3)\\\\K_{L}(i-1,i-{\frac {j+3}{2}})&{\mbox{if }}j{\text{ is Odd and }}(j<2i-3)\\\\\end{array}}\right.$

$\displaystyle K_{L}(i)=K_{L}(i,i)$

$\displaystyle K_{L}({\bigg \lfloor }{\frac {n+4}{3}}{\bigg \rfloor },{\bigg \lfloor }{\frac {2n+1}{3}}{\bigg \rfloor })=n$

Mathematica: A356026

KL[i_, j_] := i + j - 1 /; (j >= 2 i - 3);
KL[i_, j_] := KL[i - 1, i + (j - 2)/2] /; (EvenQ[j] && (j < 2 i - 3));
KL[i_, j_] := KL[i - 1, i - (j + 3)/2] /; (OddQ[j] && (j < 2 i - 3));
KL[i_] := KL[i, i];
A356026[n_] := KL[n];
Array[A356026, 30]

Pari: A356026

\\ Kimberling Expulsion Array alternate version
KL(i,j) =
{
my(i1,j1);
i1=i;
j1=j;
while(j1<(2*i1-3),
      if(j1%2,
         j1=i1-((j1+3)/2),
         j1=i1+((j1-2)/2)
         );
      i1--;
);
return(i1+j1-1);
}
A356026(i)=KL(i,i);

CODE:

Download Complete Kimberling's Array Code for PARI/GP

Bibliography:

[1] C. Kimberling, “Problem 1615,” Crux Mathematicorum, vol. 17, no. 1, p. 288, 1991. .pdf

[2] C. Kimberling, “Interspersions and dispersions,” Proceedings of the American Mathematical Society, pp. 313-321, 1993.

[3] A. S. Fraenkel and C. Kimberling, “Generalized wythoff arrays, shuffles and interspersions,” Discrete Math., vol. 126, pp. 137-149, March 1994.

[4] C. Kimberling, “Unsolved problems and rewards..” http://faculty.evansville.edu/ck6/integer/unsolved.html, 1999.

[5] C. Kimberling and J. Brown, “Partial complements and transposable dispersions,” J. Integer Sequences, vol. 7, 2004.

[6] D. Gale, Tracking the Automatic Ant: And Other Mathematical Explorations, ch. 5, p. 27. Springer, 1998.

[7] R. K. Guy, Unsolved Problems in Number Theory (Problem Books in Mathematics / Unsolved Problems in Intuitive Mathematics). Springer, 2004.

[8] E. W. Weisstein, “Kimberling sequence.” MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/KimberlingSequence.html, 1999.

[9] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences.” A007063. Main diagonal of Kimberling's expulsion array (A035486).

[10] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences.” A035486. Kimberling's expulsion array read by antidiagonals.

[11] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences.” A006852. Step at which n is expelled in Kimberling's puzzle (A035486).

[12] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences.” A035505. Active part of Kimberling's expulsion array as a triangular array.

[13] E.Pérez Herrero, “The On-Line Encyclopedia of Integer Sequences.” A175312. Maximum value on Lower Shuffle Part of Kimberling's Expulsion Array A035486 (New Sequence)

User:Enrique Pérez Herrero/Kimberling

Contents