A246960 -id:A246960 - cp's OEIS frontend

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 4, 5, 6, 5, 4, 5

Offset: 0

N. J. A. Sloane, Jeffrey Shallit, Simon Plouffe

Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.
a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...) and A014577; identical to the latter except starting 1, 1, 0, ...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g., A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson, Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - Gary W. Adamson, Jul 23 2008
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
Can be used as a binomial transform operator: Let a(n) = the n-th term in any S(n); then extract 2^k strings, adding the terms. This results in the binomial transform of S(n). Say S(n) = 1, 3, 5, ...; then we obtain the strings: (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), ...; = the binomial transform of (1, 3, 5, ...) = (1, 4, 12, 32, 80, ...). Example: the 8-bit string has a sum of 32 with a distribution of (1, 3, 3, 1) or one 1, three 3's, three 5's, and one 7; as expected. - Gary W. Adamson, Jun 21 2012
Considers all positive odd numbers as nodes of a graph. Two nodes are connected if and only if the sum of the two corresponding odd numbers is a power of 2. Then a(n) is the distance between 2n + 1 and 1. - Jianing Song, Apr 20 2019

			Considered as a triangle with 2^k terms per row, the first few rows are:
  1
  2, 1
  2, 3, 2, 1
  2, 3, 4, 3, 2, 3, 2, 1
  ...
The n-th row becomes right half of next row; left half is mirrored terms of n-th row increased by one. - _Gary W. Adamson_, Jun 20 2012

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook).
J.-P. Allouche, G.-N. Han and J. Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Danielle Cox and Karyn McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted with addendum in Donald E. Knuth, Selected Papers on Fun and Games, 2010, pages 571-614. Equation 3.2 g(n) = a(n-1).
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
P. Flajolet and Lyle Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142-158.
Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
Sara Kropf and S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, arXiv preprint arXiv:1608.03700 [math.CO], 2016.
Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
Helmut Prodinger and Friedrich J. Urbanek, Infinite 0-1-Sequences Without Long Adjacent Identical Blocks, Discrete Mathematics, volume 28, issue 3, 1979, pages 277-289. Also first author's copy. Their "variation" v(k) at definition 3.4 is a(k).
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Index entries for "core" sequences.
Index entries for sequences related to binary expansion of n.

Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs), A173318 (partial sums).
Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.
Partial sums of A112347. Recursion depth of A035327.
Cf. A000120, A003188.

import Data.List (group)
a005811 0 = 0
a005811 n = length $ group $ a030308_row n
a005811_list = 0 : f [1] where
   f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Feb 16 2013, Mar 07 2011

A005811 := proc(n)
    local i, b, ans;
    if n = 0 then
        return 0 ;
    end if;
    ans := 1;
    b := convert(n, base, 2);
    for i from nops(b)-1 to 1 by -1 do
        if b[ i+1 ]<>b[ i ] then
            ans := ans+1
        fi
    od;
    return ans ;
end proc:
seq(A005811(i), i=1..50) ;
# second Maple program:
a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 01 2023

Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
a[n_] := DigitCount[BitXor[n, Floor[n/2]], 2, 1]; Array[a, 100, 0] (* Amiram Eldar, Jul 11 2024 *)

a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))

a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ Benoit Cloitre, Jan 20 2014

a(n) = hammingweight(bitxor(n, n>>1));  \\ Gheorghe Coserea, Sep 03 2015

def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017

a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller, Aug 14 2001
a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).
a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - Ralf Stephan, May 02 2003
Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson, Oct 19 2003
a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(n) = Sum_{k=1..n} (-1)^((k/2^A007814(k)-1)/2) = Sum_{k=1..n} (-1)^A025480(k-1). - Ralf Stephan, Oct 29 2003
a(n) = A069010(n) + A033264(n). - Ralf Stephan, Oct 29 2003
a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - Benoit Cloitre, Jan 20 2014
a(n) = A037834(n) + 1.
a(n) = A000120(A003188(n)). - Amiram Eldar, Jul 11 2024

Additional description from Wouter Meeussen

A278219 Filter-sequence related to base-2 run-length encoding: a(n) = A046523(A243353(n)).

Original entry on oeis.org

1, 2, 4, 2, 4, 8, 6, 2, 4, 12, 16, 8, 6, 12, 6, 2, 4, 12, 36, 12, 16, 32, 24, 8, 6, 30, 24, 12, 6, 12, 6, 2, 4, 12, 36, 12, 36, 72, 60, 12, 16, 48, 64, 32, 24, 72, 24, 8, 6, 30, 60, 30, 24, 48, 60, 12, 6, 30, 24, 12, 6, 12, 6, 2, 4, 12, 36, 12, 36, 72, 60, 12, 36, 180, 144, 72, 60, 180, 60, 12, 16, 48, 144, 48, 64, 128, 96, 32, 24, 120, 216, 72, 24, 72

Offset: 0

Antti Karttunen, Nov 16 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..65537

Cf. A003188, A046523, A075157, A243353, A278220.
Other base-2 related filter sequences: A278217, A278222.
Sequences that (seem to) partition N into same or coarser equivalence classes are at least these: A005811, A136004, A033264, A037800, A069010, A087116, A090079 and many others like A105500, A106826, A166242, A246960, A277561, A037834, A225081 although these have not been fully checked yet.

f[n_, i_, x_] := Which[n == 0, x, EvenQ@ n, f[n/2, i + 1, x], True, f[(n - 1)/2, i, x Prime@ i]]; g[n_] := If[n == 1, 1, Times @@ MapIndexed[ Prime[First@ #2]^#1 &, Sort[FactorInteger[n][[All, -1]], Greater]]];
Table[g@ f[BitXor[n, Floor[n/2]], 1, 1], {n, 0, 93}] (* Michael De Vlieger, May 09 2017 *)

from sympy import prime, factorint
import math
def A(n): return n - 2**int(math.floor(math.log(n, 2)))
def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))
def a005940(n): return b(n - 1)
def P(n):
    f = factorint(n)
    return sorted([f[i] for i in f])
def a046523(n):
    x=1
    while True:
        if P(n) == P(x): return x
        else: x+=1
def a003188(n): return n^int(n/2)
def a243353(n): return a005940(1 + a003188(n))
def a(n): return a046523(a243353(n)) # Indranil Ghosh, May 07 2017

(define (A278219 n) (A046523 (A243353 n)))

a(n) = A046523(A243353(n)).
a(n) = A278222(A003188(n)).
a(n) = A278220(1+A075157(n)).

A105500 Trajectory of 1 under the morphism 1->{1,2}, 2->{3,2}, 3->{3,4}, 4->{1,4}.

Original entry on oeis.org

1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 1, 4, 3, 4, 3, 2, 3, 4, 1, 4, 1, 2, 1, 4, 3, 4, 1, 4, 3, 4, 3, 2, 3, 4, 1, 4, 1, 2, 1, 4, 1, 2, 3, 2, 1, 2, 1, 4, 3, 4, 1, 4, 1, 2, 1, 4, 3, 4, 1, 4, 3, 4, 3, 2, 3, 4, 1, 4, 1, 2, 1, 4, 1, 2, 3, 2, 1, 2, 1, 4, 1, 2, 3, 2, 3, 4, 3, 2, 1, 2, 3, 2, 1, 2, 1, 4, 3, 4, 1, 4, 1, 2, 1, 4, 1

Offset: 0

Roger L. Bagula, May 02 2005

nonn

Harter-Heighway dragon when interpreting 1, 2, 3, and 4 respectively as unit edge to right, up, left, and down. - Joerg Arndt, Jun 03 2021

The characteristic polynomial of the transition matrix is x^4-4*x^3+6*x^2-4*x = x*(x-2)*(x^2 - 2*x + 2).

Joerg Arndt, Iterate six of the Harter-Heighway dragon
F. M. Dekking, Recurrent sets, Advances in Mathematics, vol. 44, no. 1 (1982), 78-104; page 89, section 4.5.
Index entries for sequences that are fixed points of mappings

Cf. A246960 (as 0..3).

Indices of terms 1..4: A043724, A043725, A043726, A043727.

Flatten[ Nest[ Flatten[ # /. {1 -> {1, 2}, 2 -> {3, 2}, 3 -> {3, 4}, 4 -> {1, 4}} &], {1}, 7]]

def A105500(n): return ((n^(n>>1)).bit_count()&3)+1 # Chai Wah Wu, Jul 13 2024

a(n) = A246960(n) + 1. - Joerg Arndt, Jun 03 2021

A343992 Number of grid-filling curves of order n (on the square grid) with turns by +-90 degrees generated by folding morphisms that are perfect.

Original entry on oeis.org

0, 1, 0, 1, 3, 0, 0, 6, 3, 20, 0, 0, 29, 0, 0, 56, 101, 108, 0, 392

Offset: 1

N. J. A. Sloane, May 06 2021

Curves of order n generated by folding morphisms are walks on the square grid, also coded by sequences (starting with D) of n-1 U's and D's starting with D, the Up and Down folds. These are also known as n-folds. In the square grid they uniquely correspond to folding morphisms, which are a special class of morphisms sigma on the alphabet {a,b,c,d}. (There is in particular the requirement that sigma(a) = ab...). Here the letters a,b,c, and d correspond to the four possible steps of the walk. A curve C = C1 of order n generates curves Cj of order n^j by the process of iterated folding. Iterated folding corresponds to iterates of the folding morphism. Grid-filling or plane-filling means that all the points in arbitrary large balls of gridpoints are eventually visited by the Cj. Perfect means that four 90-degree rotated copies of the curves Cj started at the origin will pass exactly twice through all grid-points as j tends to infinity (except the origin itself).

It is a theorem that a(A022544(n)) = 0, and a(A001481(n)) > 0 for n>2.

			For n=2 one obtains Heighway's dragon curve, with folding morphism sigma: a -> ab, b -> cb, c -> cd, d -> ad (see A105500 or A246960).

Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted and updated in Donald E. Knuth, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614.

Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
F. M. Dekking, Paperfolding Morphisms, Planefilling Curves, and Fractal Tiles, Theoretical Computer Science, volume 414, issue 1, January 2012, pages 20-37. Also arXiv:1011.5788 [math.CO], 2010-2011.

Cf. A296148, A343990, A343991.

Renamed and rewritten by Michel Dekking, Jun 03 2021

cp's OEIS Frontend

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A278219 Filter-sequence related to base-2 run-length encoding: a(n) = A046523(A243353(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A105500 Trajectory of 1 under the morphism 1->{1,2}, 2->{3,2}, 3->{3,4}, 4->{1,4}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A343992 Number of grid-filling curves of order n (on the square grid) with turns by +-90 degrees generated by folding morphisms that are perfect.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A355459 Real part of the Heighway/harter dragon curve points which are on the real axis.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A355460 Imaginary part of the Heighway/Harter dragon curve points which are on the imaginary axis.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI