A088370 -id:A088370 - cp's OEIS frontend

A088371 Position where n is inserted into the n-th row of triangle A088370, where the n-th row differs from the prior row only by the presence of n.

1, 2, 2, 4, 2, 5, 4, 8, 2, 7, 5, 11, 4, 11, 8, 16, 2, 11, 7, 17, 5, 16, 11, 23, 4, 17, 11, 25, 8, 23, 16, 32, 2, 19, 11, 29, 7, 26, 17, 37, 5, 26, 16, 38, 11, 34, 23, 47, 4, 29, 17, 43, 11, 38, 25, 53, 8, 37, 23, 53, 16, 47, 32, 64, 2, 35, 19, 53, 11, 46, 29, 65, 7, 44, 26, 64, 17

Offset: 1

Paul D. Hanna, Sep 28 2003

nonn

			A088370 rows: {1}, {1, 2}, {1, 3, 2}, {1, 3, 2, 4}, {1, 5, 3, 2, 4}, {1, 5, 3, 2, 6, 4}, {1, 5, 3, 7, 2, 6, 4}, ...
Row 5 is formed from row 3, {1, 3, 2} and row 2, {1, 2}: {1, 5, 3, 2, 4} = {1*2-1, 3*2-1, 2*2-1}|{1*2, 2*2}.
This sequence can form the following irregular triangle:
1;
2;
2, 4;
2, 5, 4, 8;
2, 7, 5, 11, 4, 11, 8, 16;
2, 11, 7, 17, 5, 16, 11, 23, 4, 17, 11, 25, 8, 23, 16, 32;
2, 19, 11, 29, 7, 26, 17, 37, 5, 26, 16, 38, 11, 34, 23, 47, 4, 29, 17, 43, 11, 38, 25, 53, 8, 37, 23, 53, 16, 47, 32, 64;
2, 35, 19, 53, 11, 46, 29, 65, 7, 44, 26, 64, 17, 56, 37, 77, 5, 46, 26, 68, 16, 59, 38, 82, 11, 56, 34, 80, 23, 70, 47, 95, 4, 53, 29, 79, 17, 68, 43, 95, 11, 64, 38, 92, 25, 80, 53, 109, 8, 65, 37, 95, 23, 82, 53, 113, 16, 77, 47, 109, 32, 95, 64, 128; ...

Alois P. Heinz, Table of n, a(n) for n = 1..16384 (first 1024 terms from Paul D. Hanna)

Cf. A088370 (triangle).

a:= proc(n) option remember; `if`(n<2, n,
     `if`(n::odd, a(n/2+1/2), a(n/2)+n/2))
    end:
seq(a(n), n=1..128);  # Alois P. Heinz, Jul 26 2019

L=100; b=vector(L,k,k); c=vector(L); a=vector(L,k,b); a[1]=[1]; print1(1,","); for(n=2,L,i=floor((n+1)/2); j=floor(n/2); b=a[i]; b=vector(i,k,b[k]=2*b[k]-1 ); c=a[j]; c=vector(j,k,c[k]=2*c[k]); a[n]=concat(b,c); t=a[n]; for(k=1,n,if(t[k]==n,print1(k,","); k=n+1)))

a(2^n)=2^n.

a(2*n-1)=a(n), a(2*n)=n+a(n).

A131966 Interspersion associated with the Cantor fractal sequence, A088370.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 9, 8, 10, 11, 14, 13, 15, 12, 16, 19, 18, 21, 17, 20, 22, 26, 24, 28, 23, 27, 25, 29, 33, 31, 35, 30, 34, 32, 36, 37, 42, 40, 44, 39, 43, 41, 45, 38, 46, 51, 49, 54, 48, 53, 50, 55, 47, 52, 56, 62, 59, 65, 58, 64, 61, 66, 57, 63, 60, 67, 73, 70, 76, 69, 75, 72, 78, 68, 74, 71, 77

Offset: 1

Clark Kimberling, Aug 02 2007

A permutation of the natural numbers.

			Northwest corner:
   1,  2,  4,  7,  11,  16,  22,  29,  37,  46, ...
   3,  6,  9, 14,  19,  26,  33,  42,  51,  62, ...
   5,  8, 13, 18,  24,  31,  40,  49,  59,  70, ...
  10, 15, 21, 28,  35,  44,  54,  65,  76,  89, ...
  12, 17, 23, 30,  39,  48,  58,  69,  81,  94, ...
  20, 27, 34, 43,  53,  64,  75,  88, 101, 116, ...
  25, 32, 41, 50,  61,  72,  85,  98, 112, 127, ...
  36, 45, 55, 66,  78,  91, 105, 120, 135, 152, ...
  38, 47, 57, 68,  80,  93, 107, 122, 139, 156, ...
  52, 63, 74, 87, 100, 115, 130, 147, 165, 184, ...

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

Alois P. Heinz, Antidiagonals n = 1..200, flattened

Cf. A088370.

T is a rectangular array given by antidiagonals: T(i,j) = the j-th index n for which A088370(n) = i.

Typo in a(18) corrected by Alois P. Heinz, Jul 26 2019

A309371 a(n) = Sum_{k=1..n} k * A088370(n,k).

Original entry on oeis.org

0, 1, 5, 13, 29, 48, 82, 122, 186, 239, 327, 419, 559, 674, 852, 1028, 1284, 1453, 1721, 1977, 2353, 2636, 3062, 3462, 4030, 4403, 4971, 5495, 6243, 6790, 7592, 8328, 9352, 9945, 10861, 11685, 12869, 13704, 14938, 16050, 17602, 18567, 20015, 21307, 23127, 24410

Offset: 0

Alois P. Heinz, Jul 25 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A000292, A000330, A088370.

b:= proc(n) option remember; `if`(n<2, n, (h->
      [map(x-> 2*x-1, [b(n-h)])[],
       map(x-> 2*x, [b(h)])[]][])(iquo(n, 2)))
    end:
a:= n-> (l-> add(i*l[i], i=1..n))([b(n)]):
seq(a(n), n=0..50);

T[n_] := T[n] = If[n == 1, {1}, Join[q = Quotient[n, 2];
   2*T[n - q] - 1, 2*T[q]]];
a[n_] := Sum[k*T[n][[k]], {k, 1, n}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Sep 15 2022, after Alois P. Heinz in A088370 *)

a(n) = Sum_{k=1..n} k * A088370(n,k).

A000292(n) <= a(n) <= A000330(n).

A053644 Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

Original entry on oeis.org

0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64

Offset: 0

Henry Bottomley, Mar 22 2000

Except for the initial term, 2^n appears 2^n times. - Lekraj Beedassy, May 26 2005
a(n) is the smallest k such that row k in triangle A265705 contains n. - Reinhard Zumkeller, Dec 17 2015
a(n) is the sum of totient function over powers of 2 <= n. - Anthony Browne, Jun 17 2016
Given positive n, reverse the bits of n and divide by 2^floor(log_2 n). Numerators are in A030101. Ignoring the initial 0, denominators are in this sequence. - Alonso del Arte, Feb 11 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Transforms
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

See A000035 for least significant bit(n).
MASKTRANS transform of A055975 (prepended with 0), MASKTRANSi transform of A048678.
Bisection of A065267, A065279, A065291, A072376.
First differences of A063915. Cf. A076877, A073121.
This is Guy Steele's sequence GS(5, 5) (see A135416).
Equals for n >= 1 the first right hand column of A160464. - Johannes W. Meijer, May 24 2009
Diagonal of A088370. - Alois P. Heinz, Oct 28 2011
Cf. A265705, A000010.

a053644 n = if n <= 1 then n else 2 * a053644 (div n 2)
-- Reinhard Zumkeller, Aug 28 2014
a053644_list = 0 : concat (iterate (\zs -> map (* 2) (zs ++ zs)) [1])
-- Reinhard Zumkeller, Dec 08 2012, Oct 21 2011, Oct 17 2010

[0] cat [2^Ilog2(n): n in [1..90]]; // Vincenzo Librandi, Dec 11 2018

a:= n-> 2^ilog2(n):
seq(a(n), n=0..80);  # Alois P. Heinz, Dec 20 2016

A053644[n_] := 2^(Length[ IntegerDigits[n, 2]] - 1); A053644[0] = 0; Table[A053644[n], {n, 0, 74}] (* Jean-François Alcover, Dec 01 2011 *)
nv[n_] := Module[{c = 2^n}, Table[c, {c}]]; Join[{0}, Flatten[Array[nv, 7, 0]]] (* Harvey P. Dale, Jul 17 2012 *)

a(n)=my(k=1);while(k<=n,k<<=1);k>>1 \\ Charles R Greathouse IV, May 27 2011

a(n) = if(!n, 0, 2^exponent(n)) \\ Iain Fox, Dec 10 2018

def a(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1) # Indranil Ghosh, May 25 2017

def A053644(n): return 1<Chai Wah Wu, Jul 27 2022

(0 to 127).map(Integer.highestOneBit()) // _Alonso del Arte, Feb 26 2020

a(n) = a(floor(n / 2)) * 2.
a(n) = 2^A000523(n).
From n >= 1 onward, A053644(n) = A062383(n)/2.
a(0) = 0, a(1) = 1 and a(n+1) = a(n)*floor(n/a(n)). - Benoit Cloitre, Aug 17 2002
G.f.: 1/(1 - x) * (x + Sum_{k >= 1} 2^(k - 1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = (A003817(n) + 1)/2 = A091940(n) + 1. - Reinhard Zumkeller, Feb 15 2004
a(n) = Sum_{k = 1..n} (floor(2^k/k) - floor((2^k - 1)/k))*A000010(k). - Anthony Browne, Jun 17 2016
a(2^m+k) = 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 07 2016

A049773 Triangular array T read by rows: if row n is r(1),...,r(m), then row n+1 is 2r(1)-1,...,2r(m)-1,2r(1),...,2r(m).

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, 6, 22, 14, 30, 4, 20, 12, 28, 8, 24, 16, 32, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19

Offset: 1

Clark Kimberling

n-th row = (r(1),r(2),...,r(m)), where m=2^(n-1), satisfies r(r(k))=k for k=1,2,...,m and has exactly 2^[ n/2 ] solutions of r(k)=k. (The function r(k) reverses bits. Or rather, r(k)=revbits(k-1)+1.)
In a knockout competition with m players, arranging the competition brackets (see links) in r(k) order, where k is the rank of the player, ensures that highest ranked players cannot meet until the later stages of the competition.  None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition.  At the same time the top ranked players in each match meet the highest ranked player possible consistent with this rule.  The sequence for the top ranked players meeting the lowest ranked player possible is A131271. - Colin Hall, Jul 31 2011, Feb 29 2012
Row n contains one of A003407(2^(n-1)) non-averaging permutations of [2^(n-1)], i.e., a permutation of [2^(n-1)] without 3-term arithmetic progressions. - Alois P. Heinz, Dec 05 2017

			Triangle begins:
1;
1,  2;
1,  3, 2,  4;
1,  5, 3,  7, 2,  6,  4,  8;
1,  9, 5, 13, 3, 11,  7, 15, 2, 10,  6, 14, 4, 12,  8, 16;
1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, ...

Alois P. Heinz, Rows n = 1..13, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence.
Wikipedia, Arithmetic progression.
Wikipedia, Bracket (tournament).
Index entries related to non-averaging sequences.

Sum of odd-indexed terms of n-th row gives A007582. Sum of even-indexed terms gives A049775.
A030109 is another version.
Cf. A131271.
Cf. A088370.
Cf. A003407, A088208.

a049773 n k = a049773_tabf !! (n-1) !! (k-1)
a049773_row n = a049773_tabf !! (n-1)
a049773_tabf = iterate f [1] where
   f vs = (map (subtract 1) ws) ++ ws where ws = map (* 2) vs
-- Reinhard Zumkeller, Mar 14 2015

T:= proc(n) option remember; `if`(n=1, 1,
      [map(x->2*x-1, [T(n-1)])[], map(x->2*x, [T(n-1)])[]][])
    end:
seq(T(n), n=1..7);  # Alois P. Heinz, Oct 28 2011

row[1] = {1}; row[n_] := row[n] = Join[ 2*row[n-1] - 1, 2*row[n-1] ]; Flatten[ Table[ row[n], {n, 1, 7}]] (* Jean-François Alcover, May 03 2012 *)

(a(n, k) = if( k<=0 || k>=n, 0, if( k%2, n\2) + a(n\2, k\2))); {T(n, k) = if( k<=0 || k>2^n/2, 0, 1 + a(2^n/2, k-1))}; /* Michael Somos, Oct 13 1999 */

A292523 Decimal encoding T(n,k) of the k-th non-averaging permutation of [n]; triangle T(n,k), n >= 0, k = 1..A003407(n), read by rows.

Original entry on oeis.org

0, 1, 12, 21, 132, 213, 231, 312, 1324, 1342, 2143, 2413, 2431, 3124, 3142, 3412, 4213, 4231, 15324, 15342, 21453, 24153, 24315, 24351, 24513, 31254, 31524, 31542, 35124, 35142, 35412, 42153, 42315, 42351, 42513, 45213, 51324, 51342, 153264, 153426, 153462

Offset: 0

Alois P. Heinz, Dec 08 2017

A non-averaging permutation avoids any 3-term arithmetic progression.
The encoding of the empty permutation () is 0. For positive n each element in the permutation is encoded using 1+floor(log_10(n)) = A055642(n) digits with leading 0's if necessary. Then all elements are concatenated.
All terms are in increasing order.

			Triangle T(n,k) begins:
:            0;
:            1;
:           12, 21;
:          132, 213, 231, 312;
:         1324, 1342, 2143, 2413,  2431,    3124,  3142, 3412, 4213, 4231;
:        15324, 15342, 21453, 24153,    ...,    42513, 45213, 51324, 51342;
:       153264, 153426, 153462, 153624, ..., 624153, 624315, 624351, 624513;
:      1532764, 1537264, 1537426,       ...,       7351462, 7351624, 7356124;
:     15327648, 15327684, 15372648,     ...,     84627351, 84672315, 84672351;
:    195327648, 195327684, 195372648,   ...,   915738462, 915783426, 915783462;
:   1090503020710060408,                ...,               10020608090401050703;
:  109050302110710060408,               ...,              1103070910010502060804;
: 10905031107021006041208,              ...,             120408100206110307090105;

Alois P. Heinz, Rows n = 0..14, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Cf. A003407, A030299, A055642, A088370.

T:= proc(n) option remember; local b, l, c; b, l, c:=
      proc(s, p) local ok, i, j, k;
        if nops(s) = 0 then l:= [l[], parse(p)]
      else for j in s do ok, i, k:= true, j-1, j+1;
             while ok and i>0 and k<=n do ok, i, k:=
               not i in s xor k in s, i-1, k+1 od;
             `if`(ok, b(s minus {j}, cat(p, 0$(c-length(j)), j)), 0)
           od
        fi
      end, [], length(n); b({$1..n}, "0"): sort(l)[]
    end:
seq(T(n), n=0..6);

cp's OEIS Frontend

A088371 Position where n is inserted into the n-th row of triangle A088370, where the n-th row differs from the prior row only by the presence of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A131966 Interspersion associated with the Cantor fractal sequence, A088370.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A309371 a(n) = Sum_{k=1..n} k * A088370(n,k).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A053644 Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Scala

Formula

A049773 Triangular array T read by rows: if row n is r(1),...,r(m), then row n+1 is 2r(1)-1,...,2r(m)-1,2r(1),...,2r(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

A292523 Decimal encoding T(n,k) of the k-th non-averaging permutation of [n]; triangle T(n,k), n >= 0, k = 1..A003407(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple