A135517 -id:A135517 - cp's OEIS frontend

A290693 Triangle read by rows, coefficients of the polynomials P(n, x) = A135517(n) *(Euler(n, x) - Euler(n, 1)).

0, -1, 1, 0, -1, 1, 1, 0, -3, 2, 0, 1, 0, -2, 1, -2, 0, 5, 0, -5, 2, 0, -3, 0, 5, 0, -3, 1, 17, 0, -42, 0, 35, 0, -14, 4, 0, 17, 0, -28, 0, 14, 0, -4, 1, -62, 0, 153, 0, -126, 0, 42, 0, -9, 2, 0, -155, 0, 255, 0, -126, 0, 30, 0, -5, 1

Offset: 0

Peter Luschny, Aug 09 2017

			   0;
  -1,  1;
   0, -1,  1;
   1,  0, -3,  2;
   0,  1,  0, -2,  1;
  -2,  0,  5,  0, -5, 2;

Cf. A135517.

c := n -> `if`(n=1 or n mod 2 = 0, 1, 2*c(iquo(n, 2))):
P := (n,x) -> (euler(n, x) - euler(n, 1))*c(n):
seq(seq(coeff(P(n,x), x, k), k=0..n), n=0..9);

A135416 a(n) = A036987(n)*(n+1)/2.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, based on a message from Guy Steele and Don Knuth, Mar 01 2008

nonn

Guy Steele defines a family of 36 integer sequences, denoted here by GS(i,j) for 1 <= i, j <= 6, as follows. a[1]=1; a[2n] = i-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}; a[2n+1] = j-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}. The present sequence is GS(1,5).
The full list of 36 sequences:
GS(1,1) = A000007
GS(1,2) = A000035
GS(1,3) = A036987
GS(1,4) = A007814
GS(1,5) = A135416 (the present sequence)
GS(1,6) = A135481
GS(2,1) = A135528
GS(2,2) = A000012
GS(2,3) = A000012
GS(2,4) = A091090
GS(2,5) = A135517
GS(2,6) = A135521
GS(3,1) = A036987
GS(3,2) = A000012
GS(3,3) = A000012
GS(3,4) = A000120
GS(3,5) = A048896
GS(3,6) = A038573
GS(4,1) = A135523
GS(4,2) = A001511
GS(4,3) = A008687
GS(4,4) = A070939
GS(4,5) = A135529
GS(4,6) = A135533
GS(5,1) = A048298
GS(5,2) = A006519
GS(5,3) = A080100
GS(5,4) = A087808
GS(5,5) = A053644
GS(5,6) = A000027
GS(6,1) = A135534
GS(6,2) = A038712
GS(6,3) = A135540
GS(6,4) = A135542
GS(6,5) = A054429
GS(6,6) = A003817
(with a(0)=1): Moebius transform of A038712.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to binary expansion of n

Equals A048298(n+1)/2. Cf. A036987, A182660.

GS:=proc(i,j,M) local a,n; a:=array(1..2*M+1); a[1]:=1;
for n from 1 to M do
a[2*n] :=[0,1,a[n],a[n]+1,2*a[n],2*a[n]+1][i];
a[2*n+1]:=[0,1,a[n],a[n]+1,2*a[n],2*a[n]+1][j];
od: a:=convert(a,list); RETURN(a); end;
GS(1,5,200):

i = 1; j = 5; Clear[a]; a[1] = 1; a[n_?EvenQ] := a[n] = {0, 1, a[n/2], a[n/2]+1, 2*a[n/2], 2*a[n/2]+1}[[i]]; a[n_?OddQ] := a[n] = {0, 1, a[(n-1)/2], a[(n-1)/2]+1, 2*a[(n-1)/2], 2*a[(n-1)/2]+1}[[j]]; Array[a, 105] (* Jean-François Alcover, Sep 12 2013 *)

A048298(n) = if(!n,0,if(!bitand(n,n-1),n,0));
A135416(n) = (A048298(n+1)/2); \\ Antti Karttunen, Jul 22 2018

def A135416(n): return int(not(n&(n+1)))*(n+1)>>1 # Chai Wah Wu, Jul 06 2022

G.f.: sum{k>=1, 2^(k-1)*x^(2^k-1) }.

Recurrence: a(2n+1) = 2a(n), a(2n) = 0, starting a(1) = 1.

Formulae and comments by Ralf Stephan, Jun 20 2014

A091090 In binary representation: number of editing steps (delete, insert, or substitute) to transform n into n + 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2

Offset: 0

Reinhard Zumkeller, Dec 19 2003

Apparently, one less than the number of cyclotomic factors of the polynomial x^n - 1. - Ralf Stephan, Aug 27 2013

Let the binary expansion of n >= 1 end with m >= 0 1's. Then a(n) = m if n = 2^m-1 and a(n) = m+1 if n > 2^m-1. - Vladimir Shevelev, Aug 14 2017

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 11.
Michael Gilleland, Levenshtein Distance [broken link] [It has been suggested that this algorithm gives incorrect results sometimes. - _N. J. A. Sloane_]
Ryota Inagaki, Tanya Khovanova, and Austin Luo, On Chip-Firing on Undirected Binary Trees, Ann. Comb. (2025). See p. 22.
Frank Ruskey and Chris Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009), Article 09.4.3.
Vladimir Shevelev, On a Luschny question, arXiv:1708.08096 [math.NT], 2017.
Eric Weisstein's World of Mathematics, Binary.
Eric Weisstein's World of Mathematics, Binary Carry Sequence.
WikiBooks: Algorithm Implementation, Levenshtein distance.
Index entries for sequences related to binary expansion of n.

Cf. A007088, A135517.

This is Guy Steele's sequence GS(2, 4) (see A135416).

a091090 n = a091090_list !! n
a091090_list = 1 : f [1,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])
-- Same list generator function as for a036987_list, cf. A036987.
-- Reinhard Zumkeller, Mar 13 2011

a091090' n = levenshtein (show $ a007088 (n + 1)) (show $ a007088 n) where
  levenshtein :: (Eq t) => [t] -> [t] -> Int
  levenshtein us vs = last $ foldl transform [0..length us] vs where
    transform xs@(x:xs') c = scanl compute (x+1) (zip3 us xs xs') where
      compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
-- Reinhard Zumkeller, Jun 09 2015

-- following Vladeta Jovovic's formula
import Data.List (transpose)
a091090'' n = vjs !! n where
   vjs = 1 : 1 : concat (transpose [[1, 1 ..], map (+ 1) $ tail vjs])
-- Reinhard Zumkeller, Jun 09 2015

A091090 := proc(n)
    if n = 0 then
        1;
    else
        A007814(n+1)+1-A036987(n) ;
    end if;
end proc:
seq(A091090(n),n=0..100); # R. J. Mathar, Sep 07 2016
# Alternatively, explaining the connection with A135517:
a := proc(n) local count, k; count := 1; k := n;
while k <> 1 and k mod 2 <> 0 do count := count + 1; k := iquo(k, 2) od:
count end: seq(a(n), n=0..101); # Peter Luschny, Aug 10 2017

a[n_] := a[n] = Which[n==0, 1, n==1, 1, EvenQ[n], 1, True, a[(n-1)/2] + 1]; Array[a, 102, 0] (* Jean-François Alcover, Aug 12 2017 *)

a(n)=my(m=valuation(n+1,2)); if(n>>m, m+1, max(m, 1)) \\ Charles R Greathouse IV, Aug 15 2017

def A091090(n): return (~(n+1)&n).bit_length()+bool(n&(n+1)) if n else 1 # Chai Wah Wu, Sep 18 2024

a(n) = LevenshteinDistance(A007088(n), A007088(n + 1)).
a(n) = A007814(n + 1) + 1 - A036987(n).
a(n) = A152487(n + 1, n). - Reinhard Zumkeller, Dec 06 2008
a(A004275(n)) = 1. - Reinhard Zumkeller, Mar 13 2011
From Vladeta Jovovic, Aug 25 2004, fixed by Reinhard Zumkeller, Jun 09 2015: (Start)
a(2*n) = 1, a(2*n + 1) = a(n) + 1 for n > 0.
G.f.: 1 + Sum_{k > 0} x^(2^k - 1)/(1 - x^(2^(k - 1))). (End)
Let T(x) be the g.f., then T(x) - x*T(x^2) = x/(1 - x). - Joerg Arndt, May 11 2010
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 2. - Amiram Eldar, Sep 29 2023
a(n) = A000120(n) + A070939(n) - A000120(n+1) - A070939(n+1) + 2. - Chai Wah Wu, Sep 18 2024

A363827 Highest power of 2 dividing n which is <= sqrt(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4

Offset: 1

Ilya Gutkovskiy, Oct 19 2023

Cf. A006519, A033676, A135517, A363828.

Cf. A007814, A102572.

Table[Last[Select[Divisors[n], # <= Sqrt[n] && IntegerQ[Log[2, #]] &]], {n, 100}]
a[n_] := 2^Min[IntegerExponent[n, 2], Floor[Log2[n]/2]]; Array[a, 100] (* Amiram Eldar, Oct 19 2023 *)

a(n) = if (n==1, 1, vecmax(select(x->((x^2 <= n) && (2^logint(x,2)==x)), divisors(n)))); \\ Michel Marcus, Oct 19 2023

a(n) = 2^min(A007814(n), A102572(n)). - Kevin Ryde, Oct 20 2023

A363828 Highest power of 2 dividing n which is < sqrt(n), for n >= 2; a(1) = 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4

Offset: 1

Ilya Gutkovskiy, Oct 19 2023

nonn

Cf. A006519, A033676, A135517, A363827.

Join[{1}, Table[Last[Select[Divisors[n], # < Sqrt[n] && IntegerQ[Log[2, #]] &]], {n, 2, 100}]]
a[n_] := 2^Min[IntegerExponent[n, 2], Ceiling[Log2[n]/2] - 1]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Oct 19 2023 *)

a(n) = if (n==1, 1, vecmax(select(x->((x^2 < n) && (2^logint(x,2)==x)), divisors(n)))); \\ Michel Marcus, Oct 19 2023

cp's OEIS Frontend

A290693 Triangle read by rows, coefficients of the polynomials P(n, x) = A135517(n) *(Euler(n, x) - Euler(n, 1)).

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A135416 a(n) = A036987(n)*(n+1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A091090 In binary representation: number of editing steps (delete, insert, or substitute) to transform n into n + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Haskell

Haskell

Maple

Mathematica

PARI

Python

Formula

A363827 Highest power of 2 dividing n which is <= sqrt(n).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A363828 Highest power of 2 dividing n which is < sqrt(n), for n >= 2; a(1) = 1.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI