A057058 -id:A057058 - cp's OEIS frontend

A194959 Fractalization of (1 + floor(n/2)).

1, 1, 2, 1, 3, 2, 1, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 5, 6, 4, 2, 1, 3, 5, 7, 6, 4, 2, 1, 3, 5, 7, 8, 6, 4, 2, 1, 3, 5, 7, 9, 8, 6, 4, 2, 1, 3, 5, 7, 9, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 12, 10, 8, 6, 4, 2, 1, 3, 5

Offset: 1

Clark Kimberling, Sep 06 2011

Suppose that p(1), p(2), p(3), ... is an integer sequence satisfying 1 <= p(n) <= n for n >= 1. Define g(1)=(1) and for n > 1, form g(n) from g(n-1) by inserting n so that its position in the resulting n-tuple is p(n). The sequence f obtained by concatenating g(1), g(2), g(3), ... is clearly a fractal sequence, here introduced as the fractalization of p. The interspersion associated with f is here introduced as the interspersion fractally induced by p, denoted by I(p); thus, the k-th term in the n-th row of I(p) is the position of the k-th n in f. Regarded as a sequence, I(p) is a permutation of the positive integers; its inverse permutation is denoted by Q(p).
...
Example: Let p=(1,2,2,3,3,4,4,5,5,6,6,7,7,...)=A008619. Then g(1)=(1), g(2)=(1,2), g(3)=(1,3,2), so that
f=(1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,1,3,5,6,4,2,1,...)=A194959; and I(p)=A057027, Q(p)=A064578.
The interspersion I(P) has the following northwest corner, easily read from f:
  1  2  4  7 11 16 22
  3  6 10 15 21 28 36
  5  8 12 17 23 30 38
  9 14 20 27 35 44 54
  ...
Following is a chart of selected p, f, I(p), and Q(p):
   p         f        I(p)      Q(p)
A000027   A002260   A000027   A000027
A008619   A194959   A057027   A064578
A194960   A194961   A194962   A194963
A053824   A194965   A194966   A194967
A053737   A194973   A194974   A194975
A019446   A194968   A194969   A194970
A049474   A194976   A194977   A194978
A194979   A194980   A194981   A194982
A194964   A194983   A194984   A194985
A194986   A194987   A194988   A194989
Count odd numbers up to n, then even numbers down from n. - Franklin T. Adams-Watters, Jan 21 2012
This sequence defines the square array A(n,k), n > 0 and k > 0, read by antidiagonals and the triangle T(n,k) = A(n+1-k,k) for 1 <= k <= n read by rows (see Formula and Example). - Werner Schulte, May 27 2018

			The sequence p=A008619 begins with 1,2,2,3,3,4,4,5,5,..., so that g(1)=(1). To form g(2), write g(1) and append 2 so that in g(2) this 2 has position p(2)=2: g(2)=(1,2). Then form g(3) by inserting 3 at position p(3)=2: g(3)=(1,3,2), and so on. The fractal sequence A194959 is formed as the concatenation g(1)g(2)g(3)g(4)g(5)...=(1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,...).
From _Werner Schulte_, May 27 2018: (Start)
This sequence seen as a square array read by antidiagonals:
  n\k: 1  2  3  4  5   6   7   8   9  10  11  12 ...
  ===================================================
   1   1  2  2  2  2   2   2   2   2   2   2   2 ... (see A040000)
   2   1  3  4  4  4   4   4   4   4   4   4   4 ... (see A113311)
   3   1  3  5  6  6   6   6   6   6   6   6   6 ...
   4   1  3  5  7  8   8   8   8   8   8   8   8 ...
   5   1  3  5  7  9  10  10  10  10  10  10  10 ...
   6   1  3  5  7  9  11  12  12  12  12  12  12 ...
   7   1  3  5  7  9  11  13  14  14  14  14  14 ...
   8   1  3  5  7  9  11  13  15  16  16  16  16 ...
   9   1  3  5  7  9  11  13  15  17  18  18  18 ...
  10   1  3  5  7  9  11  13  15  17  19  20  20 ...
  etc.
This sequence seen as a triangle read by rows:
  n\k:  1  2  3  4  5   6   7   8   9  10  11  12  ...
  ======================================================
   1    1
   2    1  2
   3    1  3  2
   4    1  3  4  2
   5    1  3  5  4  2
   6    1  3  5  6  4   2
   7    1  3  5  7  6   4   2
   8    1  3  5  7  8   6   4   2
   9    1  3  5  7  9   8   6   4   2
  10    1  3  5  7  9  10   8   6   4   2
  11    1  3  5  7  9  11  10   8   6   4   2
  12    1  3  5  7  9  11  12  10   8   6   4   2
  etc.
(End)

Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.

Paul Lévy, Sur quelques classes de permutations, Compositio Mathematica, Volume 8, 1951, pages 1-48. P_n = g(n).
Eric Weisstein's World of Mathematics, Fractal sequence
Eric Weisstein's World of Mathematics, Interspersion
Wikipedia, Fractal sequence

Cf. A000142, A000217, A005408, A005843, A008619, A057027, A064578, A209229, A210535, A219977; A000012 (col 1), A157532 (col 2), A040000 (row 1), A113311 (row 2); A194029 (introduces the natural fractal sequence and natural interspersion of a sequence - different from those introduced at A194959).

Cf. A003558 (g permutation order), A102417 (index), A330081 (on bits), A057058 (inverse).

r = 2; p[n_] := 1 + Floor[n/r]
Table[p[n], {n, 1, 90}]  (* A008619 *)
g[1] = {1}; g[n_] := Insert[g[n - 1], n, p[n]]
f[1] = g[1]; f[n_] := Join[f[n - 1], g[n]]
f[20] (* A194959 *)
row[n_] := Position[f[30], n];
u = TableForm[Table[row[n], {n, 1, 5}]]
v[n_, k_] := Part[row[n], k];
w = Flatten[Table[v[k, n - k + 1], {n, 1, 13},
{k, 1, n}]]  (* A057027 *)
q[n_] := Position[w, n]; Flatten[
Table[q[n], {n, 1, 80}]]  (* A064578 *)
Flatten[FoldList[Insert[#1, #2, Floor[#2/2] + 1] &, {}, Range[10]]] (* Birkas Gyorgy, Jun 30 2012 *)

T(n,k) = min(k<<1-1,(n-k+1)<<1); \\ Kevin Ryde, Oct 09 2020

From Werner Schulte, May 27 2018 and Jul 10 2018: (Start)
Seen as a triangle: It seems that the triangle T(n,k) for 1 <= k <= n (see Example) is the mirror image of A210535.
Seen as a square array A(n,k) and as a triangle T(n,k):
A(n,k) = 2*k-1 for 1 <= k <= n, and A(n,k) = 2*n for 1 <= n < k.
A(n+1,k+1) = A(n,k+1) + A(n,k) - A(n-1,k) for k > 0 and n > 1.
A(n,k) = A(k,n) - 1 for n > k >= 1.
P(n,x) = Sum_{k>0} A(n,k)*x^(k-1) = (1-x^n)*(1-x^2)/(1-x)^3 for n >= 1.
Q(y,k) = Sum_{n>0} A(n,k)*y^(n-1) = 1/(1-y) for k = 1 and Q(y,k) = Q(y,1) + P(k-1,y) for k > 1.
G.f.: Sum_{n>0, k>0} A(n,k)*x^(k-1)*y^(n-1) = (1+x)/((1-x)*(1-y)*(1-x*y)).
Sum_{k=1..n} A(n+1-k,k) = Sum_{k=1..n} T(n,k) = A000217(n) for n > 0.
Sum_{k=1..n} (-1)^(k-1) * A(n+1-k,k) = Sum_{k=1..n} (-1)^(k-1) * T(n,k) = A219977(n-1) for n > 0.
Product_{k=1..n} A(n+1-k,k) = Product_{k=1..n} T(n,k) = A000142(n) for n > 0.
A(n+m,n) = A005408(n-1) for n > 0 and some fixed m >= 0.
A(n,n+m) = A005843(n) for n > 0 and some fixed m > 0.
Let A_m be the upper left part of the square array A(n,k) with m rows and m columns. Then det(A_m) = 1 for some fixed m > 0.
The P(n,x) satisfy the recurrence equation P(n+1,x) = P(n,x) + x^n*P(1,x) for n > 0 and initial value P(1,x) = (1+x)/(1-x).
Let B(n,k) be multiplicative with B(n,p^e) = A(n,e+1) for e >= 0 and some fixed n > 0. That yields the Dirichlet g.f.: Sum_{k>0} B(n,k)/k^s = (zeta(s))^3/(zeta(2*s)*zeta(n*s)).
Sum_{k=1..n} A(k,n+1-k)*A209229(k) = 2*n-1. (conjectured)
(End)
From Kevin Ryde, Oct 09 2020: (Start)
T(n,k) = 2*k-1 if 2*k-1 <= n, or 2*(n+1-k) if 2*k-1 > n. [Lévy, chapter 1 section 1 equations (a),(b)]
Fixed points T(n,k)=k for k=1 and k = (2/3)*(n+1) when an integer. [Lévy, chapter 1 section 2 equation (3)]
(End)

Name corrected by Franklin T. Adams-Watters, Jan 21 2012

A057059 Let R(i,j) be the rectangle with antidiagonals 1; 2,3; 4,5,6; ... Define i(m) and j(m) by R(i(m),j(m)) = m. Then a(n) = j(A057027(n)).

Original entry on oeis.org

1, 2, 1, 3, 1, 2, 4, 1, 3, 2, 5, 1, 4, 2, 3, 6, 1, 5, 2, 4, 3, 7, 1, 6, 2, 5, 3, 4, 8, 1, 7, 2, 6, 3, 5, 4, 9, 1, 8, 2, 7, 3, 6, 4, 5, 10, 1, 9, 2, 8, 3, 7, 4, 6, 5, 11, 1, 10, 2, 9, 3, 8, 4, 7, 5, 6, 12, 1, 11, 2, 10, 3, 9, 4, 8, 5, 7, 6, 13, 1, 12, 2, 11, 3, 10

Offset: 1

Clark Kimberling, Jul 30 2000

Since A057027 is a permutation of the natural numbers, every natural number occurs in this sequence infinitely many times.
Triangle of spiral permutations. In the Saclolo reference sigma_n(x) is called a spiral permutation. - Michael Somos, Apr 21 2011
Second inverse function (numbers of columns) for pairing function A194982. - Boris Putievskiy, Jan 10 2013
The triangle T(n, k) (see the formula by Michael Somos) has in row n a certain permutation of [1, 2, ..., n]. This permutation is useful for the proof of the identity Product_{k=1..n} f(sin(Pi*k/(2*n+1))) = Product_{m=1..n} f(sin(2*Pi*m/(2*n+1))) for any function f, n >= 1 (also for  n = 0). The permutation of the arguments of f goes via m = T(n, k), and this is due to sin(Pi-x) = sin(x). Of course, one can replace the product by a sum in this identity. The product identity is used in a trivial variant of Eisenstein's proof of the quadratic reciprocity law. See the W. Lang Aug 28 2016 comment under A049310. - Wolfdieter Lang, Aug 28 2016
For the proof of the (slightly extended) conjecture stated in the formula section by L. Edson Jeffery see the W. Lang link. - Wolfdieter Lang, Sep 14 2016

			Formatted as a triangle T(n, k) (see Michael Somos' formula):
n, 2n+1\k 1 2  3 4  5 6  7 8  9 10 11 12 ..
1,   3:   1
2,   5:   2 1
3,   7:   3 1  2
4,   9:   4 1  3 2
5,  11:   5 1  4 2  3
6,  13:   6 1  5 2  4 3
7,  15:   7 1  6 2  5 3  4
8,  17:   8 1  7 2  6 3  5 4
9,  19:   9 1  8 2  7 3  6 4  5
10, 21:  10 1  9 2  8 3  7 4  6  5
11, 23:  11 1 10 2  9 3  8 4  7  5  6
12, 25:  12 1 11 2 10 3  9 4  8  5  7  6
... formatted by _Wolfdieter Lang_, Aug 28 2016
n=4: sin identity: sin(Pi*k/9) = sin(2*Pi*T(4, k)/9), for k = 1, ..., n. That is: sin(Pi*1/9) = sin(2*Pi*4/9) = sin(Pi*(1 - 8/9)), sin(Pi*3/9) = sin(2*Pi*3/9) = sin(Pi*(1 - 6/9)). For even k this is trivial. - _Wolfdieter Lang_, Aug 28 2016

Wolfdieter Lang, Proof of a Conjecture Involving Chebyshev Polynomials.
Boris Putievskiy, Transformations Integer Sequences And Pairing Functions, arXiv:1212.2732 [math.CO], 2012.
M. P. Saclolo, How a Medieval Troubadour Became a Mathematical Figure, Notices Amer. Math. Soc. 58 (2011), no. 5, 682-687. See p. 684 Equation (1).

Cf. A057058, A194982; related to A141419.

Table[If[OddQ@ k, n - (k - 1)/2, k/2], {n, 12}, {k, n}] // Flatten (* Michael De Vlieger, Aug 28 2016 *)

{T(n, k) = if( k<1 || k>n, 0, if( k%2, n - (k - 1) / 2, k / 2))} /* Michael Somos, Apr 21 2011 */

T(n, k) = k / 2 if k is even, n - (k - 1) / 2 if k is odd where 0 < k <= n are integers. - Michael Somos, Apr 21 2011
(Conjecture) Define the Chebyshev polynomials of the second kind by U_0(t) = 1, U_1(t) = 2*t, and U_r(t) = 2*t*U_(r-1)(t) - U_(r-2)(t) (r>1). Then T(n,k) = Sum_{j=1..n} U_(k-1)(cos((2*j-1)*Pi/(2*n+1))), 1<=k<=n. - L. Edson Jeffery, Jan 09 2012 (See the Sep 14 2016 comment above.)
From Boris Putievskiy, Jan 10 2013: (Start)
a(n) = -(A004736(n)+(A002260(n)-1)/2)*((-1)^A002260(n)-1)/2+(A002260(n)/2)*((-1)^A002260(n)+1)/2.
a(n) = -(j+(i-1)/2)*((-1)^i-1)/2+(i/2)*((-1)^i+1)/2, where i = n-t*(t+1)/2, j = (t*t+3*t+4)/2-n, t = floor((-1+sqrt(8*n-7))/2). (End)

A165162 Triangle T(n,m) with 2n-1 entries per row, read by rows: the first n entries count down from n to 1, the remaining n-1 entries down from n-1 to 1.

Original entry on oeis.org

1, 2, 1, 1, 3, 2, 1, 2, 1, 4, 3, 2, 1, 3, 2, 1, 5, 4, 3, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 7, 6, 5, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 7, 6, 5, 4, 3, 2, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Paul Curtz, Sep 06 2009

Arose in a study of saddle-point quantities (see A057058 and references therein).
In conjunction with denominators defined in A165200 this constitutes a triangle of fractions:
1;
2,1/2,1/4;
3,2/2,1/3,2/6,1/9;
4,3/2,2/3,1/4,3/8,2/12,1/16;

			1;
2,1,1;
3,2,1,2,1;
4,3,2,1,3,2,1;
5,4,3,2,1,4,3,2,1;

P. Curtz, Stabilite locale des systemes quadratiques. Ann. sc. Ecole Normale Sup., 1980, 293-302.

Flatten[ Table[ Range[k, 1, -1], {n, 1, 10}, {k, {n, n-1}}]] (* Jean-François Alcover, Aug 02 2012 *)

T(n,m) = n-m+1 for 1 <= m <= n. T(n,m) = 2n-m for n< m <= 2n-1. [R. J. Mathar, Nov 24 2010]

sum_{m=1..2n-1} T(n,m) = n^2.

cp's OEIS Frontend

A194959 Fractalization of (1 + floor(n/2)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A057059 Let R(i,j) be the rectangle with antidiagonals 1; 2,3; 4,5,6; ... Define i(m) and j(m) by R(i(m),j(m)) = m. Then a(n) = j(A057027(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A165162 Triangle T(n,m) with 2n-1 entries per row, read by rows: the first n entries count down from n to 1, the remaining n-1 entries down from n-1 to 1.

Views

Author

Keywords

Comments

Examples

References

Programs

Mathematica

Formula