A037800 -id:A037800 - cp's OEIS frontend

A156552 Unary-encoded compressed factorization of natural numbers.

0, 1, 2, 3, 4, 5, 8, 7, 6, 9, 16, 11, 32, 17, 10, 15, 64, 13, 128, 19, 18, 33, 256, 23, 12, 65, 14, 35, 512, 21, 1024, 31, 34, 129, 20, 27, 2048, 257, 66, 39, 4096, 37, 8192, 67, 22, 513, 16384, 47, 24, 25, 130, 131, 32768, 29, 36, 71, 258, 1025, 65536, 43, 131072, 2049, 38, 63, 68, 69, 262144

Offset: 1

Leonid Broukhis, Feb 09 2009

The primes become the powers of 2 (2 -> 1, 3 -> 2, 5 -> 4, 7 -> 8); the composite numbers are formed by taking the values for the factors in the increasing order, multiplying them by the consecutive powers of 2, and summing. See the Example section.
From Antti Karttunen, Jun 27 2014: (Start)
The odd bisection (containing even terms) halved gives A244153.
The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.
(End)
Question: Are there any other solutions that would satisfy the recurrence r(1) = 0; and for n > 1, r(n) = Sum_{d|n, d>1} 2^A033265(r(d)), apart from simple variants 2^k * A156552(n)? See also A297112, A297113. - Antti Karttunen, Dec 30 2017

			For 84 = 2*2*3*7 -> 1*1 + 1*2 + 2*4 + 8*8 =  75.
For 105 = 3*5*7 -> 2*1 + 4*2 + 8*4 = 42.
For 137 = p_33 -> 2^32 = 4294967296.
For 420 = 2*2*3*5*7 -> 1*1 + 1*2 + 2*4 + 4*8 + 8*16 = 171.
For 147 = 3*7*7 = p_2 * p_4 * p_4 -> 2*1 + 8*2 + 8*4 = 50.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1024 terms from Antti Karttunen)
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]
A puzzle by Sergey Orlov (in Russian)
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences computed from indices in prime factorization

One less than A005941.
Inverse permutation: A005940 with starting offset 0 instead of 1.
Cf. A000079, A000120, A001222, A052126, A054429, A061395, A064216, A064989, A003188, A243071, A243065-A243066, A244153, A243354, A112798, A125106, A056239, A161511.
Cf. also A297106, A297112 (Möbius transform), A297113, A153013, A290308, A300827, A323243, A323244, A323247, A324201, A324812 (n for which a(n) is a square), A324813, A324822, A324823, A324398, A324713, A324815, A324819, A324865, A324866, A324867.
Other related permutations: A253551, A253792, A253564, A253791, A277195, A297163, A297164, A297165, A297166, A302023, A305418, A322863, A322864.

Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[ Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ n]], {n, 67}] (* Michael De Vlieger, Sep 08 2016 *)

a(n) = {my(f = factor(n), p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res}; \\ David A. Corneth, Mar 08 2019

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A156552(n) = if(1==n, 0, if(!(n%2), 1+(2*A156552(n/2)), 2*A156552(A064989(n)))); \\ (based on the given recurrence) - Antti Karttunen, Mar 08 2019

# Program corrected per instructions from Leonid Broukhis. - Antti Karttunen, Jun 26 2014
# However, it gives correct answers only up to n=136, before corruption by a wrap-around effect.
# Note that the correct answer for n=137 is A156552(137) = 4294967296.
$max = $ARGV[0];
$pow = 0;
foreach $i (2..$max) {
@a = split(/ /, `factor $i`);
shift @a;
$shift = 0;
$cur = 0;
while ($n = int shift @a) {
$prime{$n} = 1 << $pow++ if !defined($prime{$n});
$cur |= $prime{$n} << $shift++;
}
print "$cur, ";
}
print "\n";
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library, two different implementations)
(definec (A156552 n) (cond ((= n 1) 0) (else (+ (A000079 (+ -2 (A001222 n) (A061395 n))) (A156552 (A052126 n))))))
(definec (A156552 n) (cond ((= 1 n) (- n 1)) ((even? n) (+ 1 (* 2 (A156552 (/ n 2))))) (else (* 2 (A156552 (A064989 n))))))
;; Antti Karttunen, Jun 26 2014

from sympy import primepi, factorint
def A156552(n): return sum((1<Chai Wah Wu, Mar 10 2023

From Antti Karttunen, Jun 26 2014: (Start)
a(1) = 0, a(n) = A000079(A001222(n)+A061395(n)-2) + a(A052126(n)).
a(1) = 0, a(2n) = 1+2*a(n), a(2n+1) = 2*a(A064989(2n+1)). [Compare to the entanglement recurrence A243071].
For n >= 0, a(2n+1) = 2*A244153(n+1). [Follows from the latter clause of the above formula.]
a(n) = A005941(n) - 1.
As a composition of related permutations:
a(n) = A003188(A243354(n)).
a(n) = A054429(A243071(n)).
For all n >= 1, A005940(1+a(n)) = n and for all n >= 0, a(A005940(n+1)) = n. [The offset-0 version of A005940 works as an inverse for this permutation.]
This permutations also maps between the partition-lists A112798 and A125106:
A056239(n) = A161511(a(n)). [The sums of parts of each partition (the total sizes).]
A003963(n) = A243499(a(n)). [And also the products of those parts.]
(End)
From Antti Karttunen, Oct 09 2016: (Start)
A161511(a(n)) = A056239(n).
A029837(1+a(n)) = A252464(n). [Binary width of terms.]
A080791(a(n)) = A252735(n). [Number of nonleading 0-bits.]
A000120(a(n)) = A001222(n). [Binary weight.]
For all n >= 2, A001511(a(n)) = A055396(n).
For all n >= 2, A000120(a(n))-1 = A252736(n). [Binary weight minus one.]
A252750(a(n)) = A252748(n).
a(A250246(n)) = A252754(n).
a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
A085357(a(n)) = A008966(n). [Ditto for their characteristic functions.]
For all n >= 0:
a(A276076(n)) = A277012(n).
a(A276086(n)) = A277022(n).
a(A260443(n)) = A277020(n).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
For n > 1, a(n) = Sum_{d|n, d>1} 2^A033265(a(d)). [See comments.]
More linking formulas:
A106737(a(n)) = A000005(n).
A290077(a(n)) = A000010(n).
A069010(a(n)) = A001221(n).
A136277(a(n)) = A181591(n).
A132971(a(n)) = A008683(n).
A106400(a(n)) = A008836(n).
A268411(a(n)) = A092248(n).
A037011(a(n)) = A010052(n) [conjectured, depends on the exact definition of A037011].
A278161(a(n)) = A046951(n).
A001316(a(n)) = A061142(n).
A277561(a(n)) = A034444(n).
A286575(a(n)) = A037445(n).
A246029(a(n)) = A181819(n).
A278159(a(n)) = A124859(n).
A246660(a(n)) = A112624(n).
A246596(a(n)) = A069739(n).
A295896(a(n)) = A053866(n).
A295875(a(n)) = A295297(n).
A284569(a(n)) = A072411(n).
A286574(a(n)) = A064547(n).
A048735(a(n)) = A292380(n).
A292272(a(n)) = A292382(n).
A244154(a(n)) = A048673(n), a(A064216(n)) = A244153(n).
A279344(a(n)) = A279339(n), a(A279338(n)) = A279343(n).
a(A277324(n)) = A277189(n).
A037800(a(n)) = A297155(n).
For n > 1, A033265(a(n)) = 1+A297113(n).
(End)
From Antti Karttunen, Mar 08 2019: (Start)
a(n) = A048675(n) + A323905(n).
a(A324201(n)) = A000396(n), provided there are no odd perfect numbers.
The following sequences are derived from or related to the base-2 expansion of a(n):
A000265(a(n)) = A322993(n).
A002487(a(n)) = A323902(n).
A005187(a(n)) = A323247(n).
A324288(a(n)) = A324116(n).
A323505(a(n)) = A323508(n).
A079559(a(n)) = A323512(n).
A085405(a(n)) = A323239(n).
The following sequences are obtained by applying to a(n) a function that depends on the prime factorization of its argument, which goes "against the grain" because a(n) is the binary code of the factorization of n, which in these cases is then factored again:
A000203(a(n)) = A323243(n).
A033879(a(n)) = A323244(n) = 2*a(n) - A323243(n),
A294898(a(n)) = A323248(n).
A000005(a(n)) = A324105(n).
A000010(a(n)) = A324104(n).
A083254(a(n)) = A324103(n).
A001227(a(n)) = A324117(n).
A000593(a(n)) = A324118(n).
A001221(a(n)) = A324119(n).
A009194(a(n)) = A324396(n).
A318458(a(n)) = A324398(n).
A192895(a(n)) = A324100(n).
A106315(a(n)) = A324051(n).
A010052(a(n)) = A324822(n).
A053866(a(n)) = A324823(n).
A001065(a(n)) = A324865(n) = A323243(n) - a(n),
A318456(a(n)) = A324866(n) = A324865(n) OR a(n),
A318457(a(n)) = A324867(n) = A324865(n) XOR a(n),
A318458(a(n)) = A324398(n) = A324865(n) AND a(n),
A318466(a(n)) = A324819(n) = A323243(n) OR 2*a(n),
A318467(a(n)) = A324713(n) = A323243(n) XOR 2*a(n),
A318468(a(n)) = A324815(n) = A323243(n) AND 2*a(n).
(End)

More terms from Antti Karttunen, Jun 28 2014

A069010 Number of runs of 1's in the binary representation of n.

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Apr 02 2002

a(n) is also the number of distinct parts in the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 24 2017

Positions of first occurrences of k are A002450(k). - John Keith, Aug 30 2021

			a(11) = 2 since 11 is 1011 in binary with two runs of 1's.
a(12) = 1 since 12 is 1100 in binary with one run of 1's.

Tilman Piesk (terms 0..9999) & Antti Karttunen, Table of n, a(n) for n = 0..16384
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 148.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A000035, A000120, A005811, A014081, A033264, A037800.
Cf. A268411 (parity of the terms), A268412 (positions of even terms), A268415 (of odd terms).
Cf. A002450 (positions of record highs).
Cf. also A227349, A246588.

f:= proc(n) option remember; if n::even then procname(n/2)
elif n mod 4 = 1 then 1 + procname((n-1)/2) else  procname((n-1)/2) fi end proc:
f(0):= 0:
map(f, [$0..1000]); # Robert Israel, Sep 06 2015

Count[Split@ IntegerDigits[#, 2], n_ /; First@ n == 1] & /@ Range[0, 120] (* Michael De Vlieger, Sep 05 2015 *)

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

def A069010(n):
    return sum(1 for d in bin(n)[2:].split('0') if len(d)) # Chai Wah Wu, Nov 04 2016

(define (A069010 n) (/ (+ (A005811 n) (A000035 n)) 2)) ;; Antti Karttunen, Feb 05 2016

a(n) = ceiling(A005811(n)/2) = A005811(n) - A033264(n). If 2^k <= n < 3*2^(k-1) then a(n) = a(n-2^k)+1; if 3*2^(k-1) <= n < 2^(k+1) then a(n) = a(n-2^k).
a(2n) = a(n), a(2n+1) = a(n) + [n is even]. - Ralf Stephan, Aug 20 2003
G.f.: (1/(1-x)) * Sum_{k>=0} (t/(1+t))/(1+t^2), where t=x^2^k. - Ralf Stephan, Sep 07 2003
a(n) = A000120(n) - A014081(n) = A037800(n) + 1, n>0. - Ralf Stephan, Sep 10 2003

A297330 Total variation of base-10 digits of n; see Comments.

Original entry on oeis.org

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

Offset: 1

Clark Kimberling, Jan 17 2018

Suppose that a number n has base-b digits b(m), b(m-1), ..., b(0).  The base-b down-variation of n is the sum DV(n,b) of all d(i)-d(i-1) for which d(i) > d(i-1); the base-b up-variation of n is the sum UV(n,b) of all d(k-1)-d(k) for which d(k) < d(k-1).  The total base-b variation of n is the sum TV(n,b) = DV(n,b) + UV(n,b).  Guide to related sequences and partitions of the natural numbers:
***
Base b     {DV(n,b)}   {UV(n,b)}    {TV(n,b)}
         A033264     A037800      A037834
         A037853     A037844      A037835
         A037854     A037845      A037836
         A037855     A037846      A037837
         A037856     A037847      A037838
         A037857     A037848      A037839
         A037858     A037849      A037840
         A037859     A037850      A037841
        A037860     A037851      A297330
        A297231     A297232      A297233
        A297234     A297235      A297236
        A297237     A297238      A297239
        A297240     A297241      A297242
        A297243     A297244      A297245
        A297246     A297247      A297247
For each b, let u = {n : UV(n,b) < DV(n,b)}, e = {n : UV(n,b) = DV(n,b)}, and d = {n : UV(n,b) > DV(n,b)}.  The sets u,e,d partition the natural numbers.  A guide to the matching sequences for u, e, d follows:
***
Base b    Sequence u   Sequence e   Sequence d
         A005843      A005408      (none)
         A297249      A297250      A297251
         A297252      A297253      A297254
         A297255      A297256      A297257
         A297258      A297259      A297260
         A297261      A297262      A297263
         A297264      A297265      A297266
         A297267      A297268      A297269
        A297270      A297271      A297272
        A297273      A297274      A297275
        A297276      A297277      A297278
        A297279      A297280      A297281
        A297282      A297283      A297284
        A297285      A297286      A297287
        A297288      A297289      A297290
Not a duplicate of A151950: e.g., a(100)=1 but A151950(100)=11. - Robert Israel, Feb 06 2018

			13684632 has DV = 8-4 + 6-3 + 3-2 = 8 and has UV = 3-1 + 6-3 + 8-6 + 6-4 = 9, so that a(13684632) = DV + UV = 17.

Clark Kimberling, Table of n, a(n) for n = 1..10000

Cf. A037851, A297330, A297271, A297272.

f:= proc(n) local L,i; L:= convert(n,base,10);
add(abs(L[i+1]-L[i]),i=1..nops(L)-1) end proc:
map(f, [$1..100]); # Robert Israel, Feb 04 2018
# alternative
A297330 := proc(n)
    A037860(n)+A037851(n) ;
end proc: # R. J. Mathar, Sep 27 2021

b = 10; z = 120; t = Table[Total@Flatten@Map[Abs@Differences@# &, Partition[ IntegerDigits[n, b], 2, 1]], {n, z}] (* after Michael De Vlieger, e.g. A037834 *)

def A297330(n):
    s = str(n)
    return sum(abs(int(s[i])-int(s[i+1])) for i in range(len(s)-1)) # Chai Wah Wu, May 31 2022

A014081 a(n) is the number of occurrences of '11' in the binary expansion of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, 0, 0, 0, 1, 0, 0, 1, 2, 1, 1, 1, 2, 2, 2, 3, 4, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 3, 3, 3, 4, 5, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, 0, 0, 0, 1, 0, 0, 1, 2, 1, 1, 1, 2, 2, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 1

Offset: 0

Simon Plouffe

a(n) takes the value k for the first time at n = 2^(k+1)-1. Cf. A000225. - Robert G. Wilson v, Apr 02 2009

a(n) = A213629(n,3) for n > 2. - Reinhard Zumkeller, Jun 17 2012

			The binary expansion of 15 is 1111, which contains three occurrences of 11, so a(15)=3.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
John Brillhart and L. Carlitz, Note on the Shapiro Polynomials, Proceedings of the American Mathematical Society, volume 25, number 1, May 1970, pages 114-118 (see A001782 for a scanned copy), with a(n) = exponent in theorem 4.
Helmut Prodinger, Generalizing the sum of digits function, SIAM J. Algebraic Discrete Methods, Vol. 3, No. 1 (1982), pp. 35-42. MR0644955 (83f:10009). [See B_2(11,n) on p. 35. - _N. J. A. Sloane_, Apr 06 2014]
Michel Rigo and Manon Stipulanti, Revisiting regular sequences in light of rational base numeration systems, arXiv:2103.16966 [cs.FL], 2021. Mentions this sequence.
Bartosz Sobolewski and Lukas Spiegelhofer, Block occurrences in the binary expansion, arXiv:2309.00142 [math.NT], 2023.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Eric Weisstein's World of Mathematics, Digit Block.
Eric Weisstein's World of Mathematics, Rudin-Shapiro Sequence.
Index entries for sequences related to binary expansion of n

Cf. A014082, A033264, A037800, A056973, A000225, A213629, A000120, A069010, A100046.
First differences give A245194.
A245195 gives 2^a(n).

import Data.Bits ((.&.))
a014081 n = a000120 (n .&. div n 2)  -- Reinhard Zumkeller, Jan 23 2012

# To count occurrences of 11..1 (k times) in binary expansion of v:
cn := proc(v, k) local n, s, nn, i, j, som, kk;
som := 0;
kk := convert(cat(seq(1, j = 1 .. k)),string);
n := convert(v, binary);
s := convert(n, string);
nn := length(s);
for i to nn - k + 1 do
if substring(s, i .. i + k - 1) = kk then som := som + 1 fi od;
som; end; # This program no longer worked. Corrected by N. J. A. Sloane, Apr 06 2014.
[seq(cn(n,2),n=0..300)];
# Alternative:
A014081 := proc(n) option remember;
  if n mod 4 <= 1 then procname(floor(n/4))
elif n mod 4 = 2 then procname(n/2)
else 1 + procname((n-1)/2)
fi
end proc:
A014081(0):= 0:
map(A014081, [$0..1000]); # Robert Israel, Sep 04 2015

f[n_] := Count[ Partition[ IntegerDigits[n, 2], 2, 1], {1, 1}]; Table[ f@n, {n, 0, 104}] (* Robert G. Wilson v, Apr 02 2009 *)
Table[SequenceCount[IntegerDigits[n,2],{1,1},Overlaps->True],{n,0,120}] (* Harvey P. Dale, Jun 06 2022 *)

A014081(n)=sum(i=0,#binary(n)-2,bitand(n>>i,3)==3)  \\ M. F. Hasler, Jun 06 2012

a(n) = hammingweight(bitand(n, n>>1)) ;
vector(105, i, a(i-1))  \\ Gheorghe Coserea, Aug 30 2015

def a(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)]) # Indranil Ghosh, Jun 03 2017

from re import split
def A014081(n): return sum(len(d)-1 for d in split('0+', bin(n)[2:]) if d != '') # Chai Wah Wu, Feb 04 2022

a(4n) = a(4n+1) = a(n), a(4n+2) = a(2n+1), a(4n+3) = a(2n+1) + 1. - Ralf Stephan, Aug 21 2003
G.f.: (1/(1-x)) * Sum_{k>=0} t^3/((1+t)*(1+t^2)), where t = x^(2^k). - Ralf Stephan, Sep 10 2003
a(n) = A000120(n) - A069010(n). - Ralf Stephan, Sep 10 2003
Sum_{n>=1} A014081(n)/(n*(n+1)) = A100046 (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

A033264 Number of blocks of {1,0} in the binary expansion of n.

Original entry on oeis.org

0, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2

Offset: 1

Clark Kimberling

Number of i such that d(i) < d(i-1), where Sum_{d(i)*2^i: i=0,1,....,m} is base 2 representation of n.

This is the base-2 down-variation sequence; see A297330. - Clark Kimberling, Jan 18 2017

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Eric Weisstein's World of Mathematics, Digit Block.
Index entries for sequences related to binary expansion of n

Cf. A014081, A014082, A037800, A056974, A056975, A056976, A056977, A056978, A056979, A056980, A196521.
a(n) = A005811(n) - ceiling(A005811(n)/2) = A005811(n) - A069010(n).
Equals (A072219(n+1)-1)/2.
Cf. also A175047, A030308.
Essentially the same as A087116.

a033264 = f 0 . a030308_row where
   f c [] = c
   f c (0 : 1 : bs) = f (c + 1) bs
   f c (_ : bs) = f c bs
-- Reinhard Zumkeller, Feb 20 2014, Jun 17 2012

f:= proc(n) option remember; local k;
k:= n mod 4;
if k = 2 then procname((n-2)/4) + 1
elif k = 3 then procname((n-3)/4)
else procname((n-k)/2)
fi
end proc:
f(1):= 0: f(0):= q:
seq(f(i),i=1..100); # Robert Israel, Aug 31 2015

Table[Count[Partition[IntegerDigits[n, 2], 2, 1], {1, 0}], {n, 102}] (* Michael De Vlieger, Aug 31 2015, after Robert G. Wilson v at A014081 *)
Table[SequenceCount[IntegerDigits[n,2],{1,0}],{n,110}] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jan 26 2017 *)

a(n) = { hammingweight(bitand(n>>1, bitneg(n))) }; \\ Gheorghe Coserea, Aug 30 2015

def A033264(n): return ((n>>1)&~n).bit_count() # Chai Wah Wu, Jun 25 2025

G.f.: 1/(1-x) * Sum_(k>=0, t^2/(1+t)/(1+t^2), t=x^2^k). - Ralf Stephan, Sep 10 2003
a(n) = A069010(n) - (n mod 2). - Ralf Stephan, Sep 10 2003
a(4n) = a(4n+1) = a(2n), a(4n+2) = a(n)+1, a(4n+3) = a(n). - Ralf Stephan, Aug 20 2003
a(n) = A087116(n) for n > 0, since strings of 0's alternate with strings of 1's, which end in (1,0). - Jonathan Sondow, Jan 17 2016
Sum_{n>=1} a(n)/(n*(n+1)) = Pi/4 - log(2)/2 (A196521) (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

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)).

A049502 Major index of n, 2nd definition.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

a(A023758(n)) = 0; a(A101082(n)) > 0. - Reinhard Zumkeller, Jun 17 2015

			83 = 1010011 has 1's followed by 0's in positions 2 and 5 (reading from the right), so a(83)=7.

D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; cf. p. 89.

Lars Blomberg, Table of n, a(n) for n = 0..10000

Cf. A049501, A037800.

Cf. A023758, A101082.

a049502 = f 0 1 where
   f m i x = if x <= 4
                then m else f (if mod x 4 == 1
                                  then m + i else m) (i + 1) $ div x 2
-- Reinhard Zumkeller, Jun 17 2015

A049502 := proc(n)
    local a,ndgs,p ;
    a := 0 ;
    ndgs := convert(n,base,2) ;
    for p from 1 to nops(ndgs)-1 do
        if op(p,ndgs)- op(p+1,ndgs) = 1 then
            a := a+p ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 17 2012

Table[Total[Flatten[Position[Partition[Reverse[IntegerDigits[n,2]],2,1],?(#=={1,0}&)]]],{n,0,110}] (* _Harvey P. Dale, Oct 05 2013 *)
Table[Total[SequencePosition[Reverse[IntegerDigits[n,2]],{1,0}][[All,1]]],{n,0,120}] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Nov 26 2020 *)

a(n)=if(n<5, return(0)); sum(i=0,exponent(n)-1, (bittest(n,i) && !bittest(n,i+1))*(i+1)) \\ Charles R Greathouse IV, Jan 30 2023

def m(n):
    x=bin(int(n))[2:][::-1]
    s=0
    for i in range(1,len(x)):
        if x[i-1]=="1" and x[i]=="0":
            s+=i
    return s
for i in range(101):
    print(str(i)+" "+str(m(i))) # Indranil Ghosh, Dec 22 2016

Write n in binary; add positions where there are 1's followed by 0's, counting from right.

More terms from Erich Friedman, Feb 19 2000

A033265 Number of i such that d(i) >= d(i-1), where Sum_{i=0..m} d(i)*2^i is the base-2 representation of n.

Original entry on oeis.org

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

Offset: 1

Clark Kimberling

			The base-2 representation of n=4 is 100 with d(0)=0, d(1)=0, d(2)=1. There are two rise-or-equal, one from d(0) to d(1) and one from d(1) to d(2), so a(4)=2. - _R. J. Mathar_, Oct 16 2015

Antti Karttunen, Table of n, a(n) for n = 1..65537
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to binary expansion of n

Cf. A014081, A023416, A037800, A037809, A005940, A156552, A297113, A364567 [= 2^a(n)].

A033265 := proc(n)
    a := 0 ;
    dgs := convert(n,base,2);
    for i from 2 to nops(dgs) do
        if op(i,dgs)>=op(i-1,dgs) then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 16 2015

A033265(n) = { my(i=0); while(n>1, if((n%4)!=1, i++); n >>= 1); (i); }; \\ Antti Karttunen, Aug 06 2023

From Ralf Stephan, Oct 05 2003: (Start)
a(0) = 0, a(2n) = a(n) + 1, a(2n+1) = a(n) + [n odd].
a(n) = A014081(n) + A023416(n).
G.f.: 1/(1-x) * Sum_{k>=0} (t^2 + t^3 + t^4)/((1+t)*(1+t^2)), t=x^2^k. (End)
a(n) = -1 + A297113(A005940(1+n)). - Antti Karttunen, Dec 30 2017

A297155 a(1) = a(2) = 0, after which, a(n) = 1+a(n/2) if n is of the form 4k+2, otherwise a(n) = a(A252463(n)).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 0, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 1, 1, 1, 2, 0, 1, 0, 1, 0, 2, 1, 1, 1, 1, 0, 2, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 2, 0, 1, 2

Offset: 1

Antti Karttunen, Dec 27 2017

nonn

Consider the binary tree illustrated in A005940: If we start from any vertex containing n, computing successive iterations of A252463 until 1 is reached, a(n) gives the number of the numbers of the form 4k+2 (with k >= 1) encountered on the path (i.e., excluding 2 from the count but including the starting n if it is of the form 4k+2).

Antti Karttunen, Table of n, a(n) for n = 1..12000
Index entries for sequences computed from indices in prime factorization

Cf. A001221, A005940, A037800, A156552, A252463, A252464, A297113.

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A297155(n) = if(n<=2,0,if(n%2,A297155(A064989(n)),(2==(n%4))+A297155(n/2)));

;; With memoization-macro definec.
(definec (A297155 n) (cond ((<= n 2) 0) ((= 2 (modulo n 4)) (+ 1 (A297155 (/ n 2)))) (else (A297155 (A252463 n)))))

a(n) = A252464(n) - A297113(n).
a(n) = A037800(A156552(n)).
a(n) = A001221(n) - 1 for all n > 1. - Velin Yanev, Mar 26 2019

A385817 Irregular triangle read by rows listing the lengths of maximal runs (sequences of consecutive elements increasing by 1) of binary indices, duplicate rows removed.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jul 14 2025

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

This is the triangle A245563, except all duplicates after the first instance of each composition are removed. It lists all compositions in order of their first appearance as a row of A245563.

			The binary indices of 53 are {1,3,5,6}, with maximal runs ((1),(3),(5,6)), with lengths (1,1,2). After removing duplicates, this is our row 16.
Triangle begins:
   0: .
   1: 1
   2: 2
   3: 1 1
   4: 3
   5: 2 1
   6: 1 2
   7: 4
   8: 1 1 1
   9: 3 1
  10: 2 2
  11: 1 3
  12: 5
  13: 2 1 1
  14: 1 2 1
  15: 4 1
  16: 1 1 2
  17: 3 2
  18: 2 3
  19: 1 4
  20: 6
  21: 1 1 1 1

In the following references, "before" is short for "before removing duplicate rows".
Positions of singleton rows appear to be A000071 = A000045-1, before A023758.
Positions of firsts appearances appear to be A001629.
Positions of rows of the form (1,1,...) appear to be A055588 = A001906+1.
First term of each row appears to be A083368.
Row sums appear to be A200648, before A000120.
Row lengths after the first row appear to be A200650+1, before A069010 = A037800+1.
Before the removals we had A245563 (except first term), see A245562, A246029, A328592.
For anti-run ranks we have A385816, before A348366, firsts A052499.
Standard composition numbers of rows are A385818, before A385889.
For anti-runs we have A385886, before A384877, firsts A384878.
Cf. A044813, A048793, A164707, A200649, A242882, A243815, A384175, A384890.

DeleteDuplicates[Table[Length/@Split[Join@@Position[Reverse[IntegerDigits[n,2]],1],#2==#1+1&],{n,0,100}]]

cp's OEIS Frontend

A156552 Unary-encoded compressed factorization of natural numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Perl

Python

Formula

Extensions

A069010 Number of runs of 1's in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Scheme

Formula

A297330 Total variation of base-10 digits of n; see Comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A014081 a(n) is the number of occurrences of '11' in the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A033264 Number of blocks of {1,0} in the binary expansion of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Links