A088705 -id:A088705 - cp's OEIS frontend

A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.

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

Offset: 1

John Tromp, Dec 11 1996

This sequence is an exception to my usual rule that when every other term of a sequence is 0 then those 0's should be omitted. In this case we would get A001511. - N. J. A. Sloane
To construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc. - Benoit Cloitre, Mar 06 2003
The sequence is invariant under the following two transformations: increment every element by one (1, 2, 1, 3, 1, 2, 1, 4, ...), put a zero in front and between adjacent elements (0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...). The intermediate result is A001511. - Ralf Hinze (ralf(AT)informatik.uni-bonn.de), Aug 26 2003
Fixed point of the morphism 0->01, 1->02, 2->03, 3->04, ..., n->0(n+1), ..., starting from a(1) = 0. - Philippe Deléham, Mar 15 2004
Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - Joerg Arndt, Apr 29 2014
a(n) is also the number of times to repeat a step on an even number in the hailstone sequence referenced in the Collatz conjecture. - Alex T. Flood (whiteangelsgrace(AT)gmail.com), Sep 22 2006
Let F(n) be the n-th Fermat number (A000215). Then F(a(r-1)) divides F(n)+2^k for r = k mod 2^n and r != 1. - T. D. Noe, Jul 12 2007
The following relation holds: 2^A007814(n)*(2*A025480(n-1)+1) = A001477(n) = n. (See functions hd, tl and cons in [Paul Tarau 2009].)
a(n) is the number of 0's at the end of n when n is written in base 2.
a(n+1) is the number of 1's at the end of n when n is written in base 2. - M. F. Hasler, Aug 25 2012
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 0). That is, A003188(n) XOR A003188(n+1) == 2^A007814(n). - Russ Cox, Dec 04 2010
The sequence is squarefree (in the sense of not containing any subsequence of the form XX) [Allouche and Shallit]. Of course it contains individual terms that are squares (such as 4). - Comment expanded by N. J. A. Sloane, Jan 28 2019
a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - T. D. Noe, Mar 01 2011
Lemma: For n < m with r = a(n) = a(m) there exists n < k < m with a(k) > r. Proof: We have n=b2^r and m=c2^r with b < c both odd; choose an even i between them; now a(i2^r) > r and n < i2^r < m. QED. Corollary: Every finite run of consecutive integers has a unique maximum 2-adic valuation. - Jason Kimberley, Sep 09 2011
a(n-2) is the 2-adic valuation of A000166(n) for n >= 2. - Joerg Arndt, Sep 06 2014
a(n) = number of 1's in the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} p_j-th prime (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24)=3; indeed, the partition having Heinz number 24 = 2*2*2*3  is [1,1,1,2]. - Emeric Deutsch, Jun 04 2015
a(n+1) is the difference between the two largest parts in the integer partition having viabin number n (0 is assumed to be a part). Example: a(20) = 2. Indeed, we have 19 = 10011_2, leading to the Ferrers board of the partition [3,1,1]. For the definition of viabin number see the comment in A290253. - Emeric Deutsch, Aug 24 2017
Apart from being squarefree, as noted above, the sequence has the property that every consecutive subsequence contains at least one number an odd number of times. - Jon Richfield, Dec 20 2018
a(n+1) is the 2-adic valuation of Sum_{e=0..n} u^e = (1 + u + u^2 + ... + u^n), for any u of the form 4k+1 (A016813). - Antti Karttunen, Aug 15 2020
{a(n)} represents the "first black hat" strategy for the game of countably infinitely many hats, with a probability of success of 1/3; cf. the Numberphile link below. - Frederic Ruget, Jun 14 2021
a(n) is the least nonnegative integer k for which there does not exist i+j=n and a(i)=a(j)=k (cf. A322523). - Rémy Sigrist and Jianing Song, Aug 23 2022

			2^3 divides 24, so a(24)=3.
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
  0;
  1,0;
  2,0,1,0;
  3,0,1,0,2,0,1,0;
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
  6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,...
(End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.
K. Atanassov, On the 37th and the 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

T. D. Noe, Table of n, a(n) for n = 1..10000
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
K. Atanassov, On Some of Smarandache's Problems
Alain Connes, Caterina Consani, and Henri Moscovici, Zeta zeros and prolate wave operators, arXiv:2310.18423 [math.NT], 2023.
Dario T. de Castro, P-adic Order of Positive Integers via Binomial Coefficients, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 22, Paper A61, 2022.
Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers, (2009) Discrete Math., 309 (2009), 6245-6254.
Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers, arXiv:0901.1397 [math.CO], 2009.
M. Hassani, Equations and inequalities involving v_p(n!), J. Inequ. Pure Appl. Math. 6 (2005) vol. 2, #29.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 61. Book's website
R. Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.3.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160.
Francis Laclé, 2-adic parity explorations of the 3n+ 1 problem, hal-03201180v2 [cs.DM], 2021.
Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
Nicolas Mallet, Trial for a proof of the Syracuse conjecture, arXiv preprint arXiv:1507.05039 [math.GM], 2015.
S. Mazzanti, Plain Bases for Classes of Primitive Recursive Functions, Mathematical Logic Quarterly, 48 (2002).
Matthew Andres Moreno, Luis Zaman, and Emily Dolson, Structured Downsampling for Fast, Memory-efficient Curation of Online Data Streams, arXiv:2409.06199 [cs.DS], 2024. See p. 5.
Sascha Mücke, Coding Nuggets Faster QUBO Brute-Force Solving, TU Dortmund Univ. (Germany 2023).
S. Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, 18 (2015), #15.11.6.
Numberphile, Hat Problems - Numberphile
Giovanni Pighizzini, Limited Automata: Properties, Complexity and Variants, International Conference on Descriptional Complexity of Formal Systems (DCFS 2019) Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science (LNCS, Vol. 11612) Springer, Cham, 57-73.
Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195 [math.NT], 2013.
A. Postnikov (MIT) and B. Sagan, What power of two divides a weighted Catalan number?, arXiv:math/0601339 [math.CO], 2006.
Lara Pudwell and Eric Rowland, Avoiding fractional powers over the natural numbers, arXiv:1510.02807 [math.CO] (2015). Also Electronic Journal of Combinatorics, Volume 25(2) (2018), #P2.27. See Section 2.
Ville Salo, Decidability and Universality of Quasiminimal Subshifts, arXiv preprint arXiv:1411.6644 [math.DS], 2014.
Vladimir Shevelev, Several results on sequences which are similar to the positive integers, arXiv:0904.2101 [math.NT], 2014.
F. Smarandache, Only Problems, Not Solutions!.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Paul Tarau, A Groupoid of Isomorphic Data Transformations. Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
P. M. B. Vitanyi, An optimal simulation of counter machines, SIAM J. Comput, 14:1(1985), 1-33.
Eric Weisstein's World of Mathematics, Binary, Binary Carry Sequence, and Double-Free Set.
Wikipedia, P-adic order.
Index entries for sequences that are fixed points of mappings
Index entries for sequences related to binary expansion of n

Cf. A011371 (partial sums), A094267 (first differences), A001511 (bisection), A346070 (mod 4).
Bisection of A050605 and |A088705|. Pairwise sums are A050603 and A136480. Difference of A285406 and A281264.
This is Guy Steele's sequence GS(1, 4) (see A135416). Cf. A053398(1,n). Column/row 1 of table A050602.
Cf. A007949 (3-adic), A235127 (4-adic), A112765 (5-adic), A122841 (6-adic), A214411 (7-adic), A244413 (8-adic), A122840 (10-adic).
Cf. A000079, A002487, A006519, A051064, A055457, A063787, A215366, A220466.
Cf. A086463 (Dgf at s=2).

a007814 n = if m == 0 then 1 + a007814 n' else 0
            where (n', m) = divMod n 2
-- Reinhard Zumkeller, Jul 05 2013, May 14 2011, Apr 08 2011

a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)
--  Walt Rorie-Baety, Mar 22 2013

[Valuation(n, 2): n in [1..120]]; // Bruno Berselli, Aug 05 2013

ord := proc(n) local i,j; if n=0 then return 0; fi; i:=0; j:=n; while j mod 2 <> 1 do i:=i+1; j:=j/2; od: i; end proc: seq(ord(n), n=1..111);
A007814 := n -> padic[ordp](n,2): seq(A007814(n), n=1..111); # Peter Luschny, Nov 26 2010

Table[IntegerExponent[n, 2], {n, 64}] (* Eric W. Weisstein *)
IntegerExponent[Range[64], 2] (* Eric W. Weisstein, Feb 01 2024 *)
p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]
DigitCount[BitXor[x, x - 1], 2, 1] - 1; a different version based on the same concept: Floor[Log[2, BitXor[x, x - 1]]] (* Jaume Simon Gispert (jaume(AT)nuem.com), Aug 29 2004 *)
Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)
Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 17 2011 *)

PARI
```
A007814(n)=valuation(n,2);
```

import math
def a(n): return int(math.log(n - (n & n - 1), 2)) # Indranil Ghosh, Apr 18 2017

def A007814(n): return (~n & n-1).bit_length() # Chai Wah Wu, Jul 01 2022

sapply(1:100,function(x) sum(gmp::factorize(x)==2)) # Christian N. K. Anderson, Jun 20 2013

(define (A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

a(n) = A001511(n) - 1.
a(2*n) = A050603(2*n) = A001511(n).
a(n) = A091090(n-1) + A036987(n-1) - 1.
a(n) = 0 if n is odd, otherwise 1 + a(n/2). - Reinhard Zumkeller, Aug 11 2001
Sum_{k=1..n} a(k) = n - A000120(n). - Benoit Cloitre, Oct 19 2002
G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Apr 10 2002
G.f. A(x) satisfies A(x) = A(x^2) + x^2/(1-x^2). A(x) = B(x^2) = B(x) - x/(1-x), where B(x) is the g.f. for A001151. - Franklin T. Adams-Watters, Feb 09 2006
Totally additive with a(p) = 1 if p = 2, 0 otherwise.
Dirichlet g.f.: zeta(s)/(2^s-1). - Ralf Stephan, Jun 17 2007
Define 0 <= k <= 2^n - 1; binary: k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1); where b(x) are 0 or 1 for 0 <= x <= n - 1; define c(x) = 1 - b(x) for 0 <= x <= n - 1; Then: a(k) = c(0) + c(0)*c(1) + c(0)*c(1)*c(2) + ... + c(0)*c(1)...c(n-1); a(k+1) = b(0) + b(0)*b(1) + b(0)*b(1)*b(2) + ... + b(0)*b(1)...b(n-1). - Arie Werksma (werksma(AT)tiscali.nl), May 10 2008
a(n) = floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008
Sum_{k=1..n} (-1)^A000120(n-k)*a(k) = (-1)^(A000120(n)-1)*(A000120(n) - A000035(n)). - Vladimir Shevelev, Mar 17 2009
a(A001147(n) + A057077(n-1)) = a(2*n). - Vladimir Shevelev, Mar 21 2009
For n>=1, a(A004760(n+1)) = a(n). - Vladimir Shevelev, Apr 15 2009
2^(a(n)) = A006519(n). - Philippe Deléham, Apr 22 2009
a(n) = A063787(n) - A000120(n). - Gary W. Adamson, Jun 04 2009
a(C(n,k)) = A000120(k) + A000120(n-k) - A000120(n). - Vladimir Shevelev, Jul 19 2009
a(n!) = n - A000120(n). - Vladimir Shevelev, Jul 20 2009
v_{2}(n) = Sum_{r>=1} (r / 2^(r+1)) Sum_{k=0..2^(r+1)-1} e^(2(k*Pi*i(n+2^r))/(2^(r+1))). - A. Neves, Sep 28 2010, corrected Oct 04 2010
a(n) mod 2 = A096268(n-1). - Robert G. Wilson v, Jan 18 2012
a(A005408(n)) = 1; a(A016825(n)) = 3; A017113(a(n)) = 5; A051062(a(n)) = 7; a(n) = (A037227(n)-1)/2. - Reinhard Zumkeller, Jun 30 2012
a((2*n-1)*2^p) = p, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 04 2013
a(n) = A067255(n,1). - Reinhard Zumkeller, Jun 11 2013
a(n) = log_2(n - (n AND n-1)). - Gary Detlefs, Jun 13 2014
a(n) = 1 + A000120(n-1) - A000120(n), where A000120 is the Hamming weight function. - Stanislav Sykora, Jul 14 2014
A053398(n,k) = a(A003986(n-1,k-1)+1); a(n) = A053398(n,1) = A053398(n,n) = A053398(2*n-1,n) = Min_{k=1..n} A053398(n,k). - Reinhard Zumkeller, Aug 04 2014
a((2*x-1)*2^n) = a((2*y-1)*2^n) for positive n, x and y. - Juri-Stepan Gerasimov, Aug 04 2016
a(n) = A285406(n) - A281264(n). - Ralf Steiner, Apr 18 2017
a(n) = A000005(n)/(A000005(2*n) - A000005(n)) - 1. - conjectured by Velin Yanev, Jun 30 2017, proved by Nicholas Stearns, Sep 11 2017
Equivalently to above formula, a(n) = A183063(n) / A001227(n), i.e., a(n) is the number of even divisors of n divided by number of odd divisors of n. - Franklin T. Adams-Watters, Oct 31 2018
a(n)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Feb 16 2019
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - Amiram Eldar, Jul 11 2020
a(n) = 2*Sum_{j=1..floor(log_2(n))} frac(binomial(n, 2^j)*2^(j-1)/n). - Dario T. de Castro, Jul 08 2022
a(n) = A070939(n) - A070939(A030101(n)). - Andrew T. Porter, Dec 16 2022
a(n) = floor((gcd(n, 2^n)^(n+1) mod (2^(n+1)-1)^2)/(2^(n+1)-1)) (see Lemma 3.4 from Mazzanti's 2002 article). - Lorenzo Sauras Altuzarra, Mar 10 2024
a(n) = 1 - A088705(n). - Chai Wah Wu, Sep 18 2024

Formula index adapted to the offset of A025480 by R. J. Mathar, Jul 20 2010

Edited by Ralf Stephan, Feb 08 2014

A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1

Offset: 0

Vladeta Jovovic, Jan 25 2003

Differences of the Meta-Fibonacci sequence for s=0. - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
Fixed point of morphism 0-->0, 1-->110 - Joerg Arndt, Jun 07 2007
A006697(k) gives number of distinct subwords of length k, conjectured to be equal to A094913(k)+1. - M. F. Hasler, Dec 19 2007
Characteristic function for the range of A005187: a(A055938(n))=0; a(A005187(n))=1; if a(m)=1 then either a(m-1)=1 or a(m+1)=1. - Reinhard Zumkeller, Mar 18 2009
The number of zeros between successive pairs of ones in this sequence is A007814. - Franklin T. Adams-Watters, Oct 05 2011
Length of n-th run = abs(A088705) + 1. - Reinhard Zumkeller, Dec 11 2011

			a(11)=1 because we have [7,3,1].
G.f. = 1 + x + x^3 + x^4 + x^7 + x^8 + x^10 + x^11 + x^15 + x^16 + x^18 + ...
From _Omar E. Pol_, Nov 30 2009: (Start)
The sequence, displayed as irregular triangle, in which rows length are powers of 2, begins:
1;
1,0;
1,1,0,0;
1,1,0,1,1,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0;
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Gary W. Adamson, Comments on A079559
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26.5, Recursive generation and relation to a power series, page 74, figure 1.26-E and function A.
Benoit Cloitre, Fractal walk generated by the 130000 first terms (step of unit length moving to right if 0 left if 1) starting at (0,0)
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.[alt source]
Thomas M. Lewis and Fabian Salinas, Optimal pebbling of complete binary trees and a meta-Fibonacci sequence, arXiv:2109.07328 [math.CO], 2021.
F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3. [This is a later version than that in the GenMetaFib.html link]
Index entries for characteristic functions

Cf. A000929, A001511, A005187, A006697, A007814, A046699, A055938, A094913, A163988.

Cf. A035263, A066519.

a079559 = p $ tail a000225_list where
   p _      0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Dec 11 2011

a079559_list = 1 : f [1] where
   f xs = ys ++ f ys where ys = init xs ++ [1] ++ tail xs ++ [0]
-- Reinhard Zumkeller, May 05 2015

g:=product(1+x^(2^n-1),n=1..15): gser:=series(g,x=0,110): seq(coeff(gser,x,n),n=0..104); # Emeric Deutsch, Apr 06 2006
d := n -> if n=1 then 1 else A046699(n)-A046699(n-1) fi; # Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

row[1] = {1}; row[2] = {1, 0}; row[n_] := row[n] = row[n-1] /. 1 -> Sequence[1, 1, 0]; Table[row[n], {n, 1, 7}] // Flatten (* Jean-François Alcover, Jul 30 2012, after Omar E. Pol *)
CoefficientList[ Series[ Product[1 + x^(2^n - 1), {n, 6}], {x, 0, 104}], x] (* or *)
Nest[ Flatten[# /. {0 -> {0}, 1 -> {1, 1, 0}}] &, {1}, 6] (* Robert G. Wilson v, Sep 08 2014 *)

w="1,";for(i=1,5,print1(w=concat([w,w,"0,"])))

A079559(n,w=[1])=until(n<#w=concat([w,w,[0]]),);w[n+1] \\ M. F. Hasler, Dec 19 2007

{a(n) = if( n<0, 0, polcoeff( prod(k=1, #binary(n+1), 1 + x^(2^k-1), 1 + x * O(x^n)), n))} /* Michael Somos, Aug 03 2009 */

def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a043545(n):
    x=bin(n)[2:]
    return int(max(x)) - int(min(x))
l=[1]
for n in range(1, 101): l+=[a043545(n + 1)*l[n + 1 - a053644(n + 1)], ]
print(l) # Indranil Ghosh, Jun 11 2017

G.f.: Product_{n>=1} (1 + x^(2^n-1)).
a(n) = 1 if n=0, otherwise A043545(n+1)*a(n+1-A053644(n+1)). - Reinhard Zumkeller, Aug 19 2006
a(n) = p(n,1) with p(n,k) = p(n-k,2*k+1) + p(n,2*k+1) if k <= n, otherwise 0^n. - Reinhard Zumkeller, Mar 18 2009
Euler transform is sequence A111113 sequence offset -1. - Michael Somos, Aug 03 2009
G.f.: Product_{k>0} (1 - x^k)^-A111113(k+1). - Michael Somos, Aug 03 2009
a(n) = A108918(n+1) mod 2. - Joerg Arndt, Apr 06 2011
a(n) = A000035(A153000(n)), n >= 1. - Omar E. Pol, Nov 29 2009, Aug 06 2013

Edited by M. F. Hasler, Jan 03 2008

A305614 Expansion of Sum_{p prime} x^p/(1 + x^p).

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jun 06 2018

sign

a(n) is the number of prime divisors p|n such that n/p is odd, minus the number of prime divisors p|n such that n/p is even.

			The prime divisors of 12 are 2, 3. We see that 12/2 = 6, 12/3 = 4. None of those are odd, but both of them are even, so a(12) = -2.
The prime divisors of 30 are {2,3,5} with quotients {15,10,6}. One of these is odd and two are even, so a(30) = 1 - 2 = -1.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A000005, A000607, A001221, A008683, A048165, A083399, A088705, A106404, A205745, A280954.

a:= n-> -add((-1)^(n/i[1]), i=ifactors(n)[2]):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 07 2018
# Alternative
N:= 1000: # to get a(0)..a(N)
V:= Vector(N):
p:= 1:
do
  p:= nextprime(p);
  if p > N then break fi;
  R:= [seq(i,i=p..N,p)];
  W:= ;
  V[R]:= V[R]+W;
od:
[0,seq(V[i],i=1..N)]; # Robert Israel, Jun 07 2018

Table[Sum[If[PrimeQ[d], (-1)^(n/d - 1), 0], {d, Divisors[n]}], {n, 30}]

a(n) = -Sum_{p|n prime} (-1)^(n/p).
From Robert Israel, Jun 07 2018: (Start)
If n is odd, a(n) = A001221(n).
If n == 2 (mod 4), a(n) = 2 - A001221(n).
If n == 0 (mod 4) and n > 0, a(n) = -A001221(n). (End)
L.g.f.: log(Product_{k>=1} (1 + x^prime(k))^(1/prime(k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Jul 30 2018

A048165 Expansion of Product_{k > 0} 1/(1 + x^prime(k)).

Original entry on oeis.org

1, 0, -1, -1, 1, 0, 0, -1, 1, 0, 1, -2, 1, -1, 2, -2, 2, -3, 3, -3, 4, -4, 5, -6, 6, -6, 8, -9, 9, -11, 12, -13, 14, -16, 19, -19, 21, -25, 26, -28, 32, -36, 38, -41, 46, -50, 55, -60, 65, -70, 77, -85, 91, -99, 108, -116, 126, -138, 149, -160, 174, -188, 202, -219, 237, -255, 274, -296

Offset: 0

N. J. A. Sloane

sign

Seiichi Manyama, Table of n, a(n) for n = 0..10000

Cf. A000005, A000040, A000586, A000607, A001221, A008683, A083399, A088705, A280954, A305614.

nn=20;
ser=Product[1/(1+x^p),{p,Select[Range[nn],PrimeQ]}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}] (* Gus Wiseman, Jun 06 2018 *)

a(n) = A184198(n) - A184199(n). - Vaclav Kotesovec, Jan 11 2021

A106404 Number of even semiprimes dividing n.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, May 02 2005

nonn

Also the number of prime divisors p|n such that n/p is even. - Gus Wiseman, Jun 06 2018

			a(60) = #{4, 6, 10} = #{2*2, 2*3, 2*5} = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000005, A000607, A001221, A001227, A008683, A083399, A088705, A100484, A205745, A305614.

a106404 n = length [d | d <- takeWhile (<= n) a100484_list, mod n d == 0]
-- Reinhard Zumkeller, Jan 31 2012

Table[Length[Select[Divisors[n],PrimeQ[#]&&EvenQ[n/#]&]],{n,100}] (* Gus Wiseman, Jun 06 2018 *)
Table[Count[Divisors[n],?(EvenQ[#]&&PrimeOmega[#]==2&)],{n,110}] (* _Harvey P. Dale, May 04 2021 *)
a[n_] := If[EvenQ[n], PrimeNu[n/2], 0]; Array[a, 100] (* Amiram Eldar, Jun 26 2022 *)

a(n)=if(n%2,0,omega(n/2)) \\ Charles R Greathouse IV, Jan 30 2012

def A106404(n):
    return add(1-(n/d)%2 for d in divisors(n) if is_prime(d))
print([A106404(n) for n in (1..105)])  # Peter Luschny, Jan 30 2012

a(n) = A086971(n) - A106405(n).
a(A100484(n)) = 1.
a(A005408(n)) = 0.
a(A005843(n)) > 0 for n>1.
a(2n) = omega(n), a(2n+1) = 0, where omega(n) is the number of distinct prime divisors of n, A001221. - Franklin T. Adams-Watters, Jun 09 2006
a(n) = card { d | d*p = n, d even, p prime }. - Peter Luschny, Jan 30 2012
O.g.f.: Sum_{p prime} x^(2p)/(1 - x^(2p)). - Gus Wiseman, Jun 06 2018

A205745 a(n) = card { d | d*p = n, d odd, p prime }.

Original entry on oeis.org

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

Offset: 1

Peter Luschny, Jan 30 2012

nonn

Equivalently, a(n) is the number of prime divisors p|n such that n/p is odd. - Gus Wiseman, Jun 06 2018

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000005, A000607, A001221, A008683, A010051, A068050, A077761, A083399, A088705, A106404, A305614.

a205745 n = sum $ map ((`mod` 2) . (n `div`))
   [p | p <- takeWhile (<= n) a000040_list, n `mod` p == 0]
-- Reinhard Zumkeller, Jan 31 2012

a[n_] := Sum[ Boole[ OddQ[d] && PrimeQ[n/d] ], {d, Divisors[n]} ]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jun 27 2013 *)

a(n)=if(n%2,omega(n),n%4/2) \\ Charles R Greathouse IV, Jan 30 2012

def A205745(n):
    return sum((n//d) % 2 for d in divisors(n) if is_prime(d))
[A205745(n) for n in (1..105)]

O.g.f.: Sum_{p prime} x^p/(1 - x^(2p)). - Gus Wiseman, Jun 06 2018

Sum_{k=1..n} a(k) = (n/2) * (log(log(n)) + B) + O(n/log(n)), where B is Mertens's constant (A077761). - Amiram Eldar, Sep 21 2024

A286240 Compound filter: a(n) = P(A278222(n), A278222(1+n)), where P(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

2, 5, 12, 14, 23, 42, 59, 44, 23, 61, 142, 117, 109, 183, 261, 152, 23, 61, 142, 148, 601, 850, 607, 375, 109, 265, 1093, 939, 473, 765, 1097, 560, 23, 61, 142, 148, 601, 850, 607, 430, 601, 1741, 3946, 2545, 2497, 3463, 2509, 1323, 109, 265, 1093, 1117, 2497, 4525, 5707, 3153, 473, 1105, 4489, 3813, 1969, 3129, 4497, 2144, 23, 61, 142, 148, 601, 850, 607, 430, 601, 1741

Offset: 0

Antti Karttunen, May 07 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 0..16383
Eric Weisstein's World of Mathematics, Pairing Function

Cf. A000027, A278222, A286241, A286242, A286255.

Cf. A088705 (one of the matches not matched by A278222 alone. Thus also the whole A007814 (A001511) family is included).

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t }; \\ Modified from code of M. F. Hasler
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A278222(n) = A046523(A005940(1+n));
A286240(n) = (2 + ((A278222(n)+A278222(1+n))^2) - A278222(n) - 3*A278222(1+n))/2;
for(n=0, 16383, write("b286240.txt", n, " ", A286240(n)));

from sympy import prime, factorint
import math
def T(n, m): return ((n + m)**2 - n - 3*m + 2)/2
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 a278222(n): return a046523(a005940(n + 1))
def a(n): return T(a278222(n), a278222(n + 1)) # Indranil Ghosh, May 07 2017

(define (A286240 n) (* (/ 1 2) (+ (expt (+ (A278222 n) (A278222 (+ 1 n))) 2) (- (A278222 n)) (- (* 3 (A278222 (+ 1 n)))) 2)))

a(n) = (1/2)*(2 + ((A278222(n)+A278222(1+n))^2) - A278222(n) - 3*A278222(1+n)).

A114115 Inverse of number triangle A114114.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Nov 13 2005

Row sums are A088705. Product with partial sum matrix (1/(1-x),x) gives A114116.

			Triangle begins
1;
-1, 1;
2,-2, 1;
-3, 3,-2, 1;
2,-2, 2,-2, 1;
0, 0,-1, 2,-2, 1;
2,-2, 2,-2, 2,-2, 1;

A382294 Decimal expansion of the asymptotic mean of the excess of the number of Fermi-Dirac factors of k over the number of distinct prime factors of k when k runs over the positive integers.

Original entry on oeis.org

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

Offset: 0

Amiram Eldar, Mar 21 2025

Analogous to Sum_{p prime} 1/(p*(p-1)) (A136141), which is the asymptotic mean of the excess of the number of prime factors over the number of distinct prime factors (A046660).

			0.13605447049622836522998926383768997616582469083783...

Cf. A001221, A046660, A064547, A088705, A136141, A382290.

s[n_] := Module[{c = CoefficientList[Series[-x + Sum[x^(2^k)/(1+x^(2^k)), {k, 0, n}],{x, 0, 2^n}], x]},Sum[c[[i]] * PrimeZetaP[i-1], {i, 3, Length[c]-2}]]; RealDigits[s[10], 10, 120][[1]]

default(realprecision, 120); default(parisize, 10000000);
f(x, n) = -x + sum(k = 0, n, x^(2^k)/(1+x^(2^k)));
sumeulerrat(f(1/p, 8))

Equals lim_{m->oo} (1/m) * Sum_{k=1..m} A382290(k).
Equal Sum_{k>=3} A088705(k) * P(k), where P(s) is the prime zeta function.
Equals Sum_{p prime} f(1/p), where f(x) = -x + Sum_{k>=0} x^(2^k)/(1+x^(2^k)).

A089263 First differences of A080791.

Original entry on oeis.org

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

Offset: 0

Ralf Stephan, Oct 30 2003

Number of trailing zeros in the binary representation of n, minus one if n is not a power of two.

a(0) = 0 by convention. - Antti Karttunen, Sep 27 2018

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

Cf. A080791, A088705.

a(n)=if(!n,n,(valuation(n, 2)+(2^valuation(n, 2)==n)-1)); \\ Check for n=0 added by Antti Karttunen, Sep 27 2018

a(n)=if(n<1,0,if(n%2==0,a(n/2)+1,-1+(((n-1)/2)==0)))

a(0)=0, a(2n) = a(n) + 1, a(2n+1) = -1 + [n==0].
a(n) = A007814(n) + A036987(n-1) - 1.
G.f.: sum(k>=0, t^2/(1+t), t=x^2^k).
a(n) = A080791(n+1) - A080791(n). - Antti Karttunen, Sep 27 2018

Definition corrected (A023416 replaced with A080791) by Antti Karttunen, Sep 27 2018

cp's OEIS Frontend

A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

R

Scheme

Formula

Extensions

A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A305614 Expansion of Sum_{p prime} x^p/(1 + x^p).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A048165 Expansion of Product_{k > 0} 1/(1 + x^prime(k)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A106404 Number of even semiprimes dividing n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Sage

Formula

A205745 a(n) = card { d | d*p = n, d odd, p prime }.

Views

Author