A007814 - OEIS

%I #497 Oct 02 2024 20:04:40

%S 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,

%T 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,

%U 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

%N 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.

%C 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_

%C 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

%C 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

%C 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

%C Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - _Joerg Arndt_, Apr 29 2014

%C 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

%C 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

%C 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].)

%C a(n) is the number of 0's at the end of n when n is written in base 2.

%C 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

%C 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

%C 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

%C a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - _T. D. Noe_, Mar 01 2011

%C 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

%C a(n-2) is the 2-adic valuation of A000166(n) for n >= 2. - _Joerg Arndt_, Sep 06 2014

%C 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

%C 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

%C 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

%C 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

%C {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

%C 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

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.

%D 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.

%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

%H T. D. Noe, <a href="/A007814/b007814.txt">Table of n, a(n) for n = 1..10000</a>

%H Joerg Arndt, <a href="http://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014.

%H K. Atanassov, <a href="http://www.gallup.unm.edu/~smarandache/Atanassov-SomeProblems.pdf">On Some of Smarandache's Problems</a>

%H Alain Connes, Caterina Consani, and Henri Moscovici, <a href="https://arxiv.org/abs/2310.18423">Zeta zeros and prolate wave operators</a>, arXiv:2310.18423 [math.NT], 2023.

%H Dario T. de Castro, <a href="http://math.colgate.edu/~integers/w61/w61.pdf">P-adic Order of Positive Integers via Binomial Coefficients</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 22, Paper A61, 2022.

%H Mathieu Guay-Paquet and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/j.disc.2009.06.004">Avoiding Squares and Overlaps Over the Natural Numbers</a>, (2009) Discrete Math., 309 (2009), 6245-6254.

%H Mathieu Guay-Paquet and Jeffrey Shallit, <a href="http://arxiv.org/abs/0901.1397">Avoiding Squares and Overlaps Over the Natural Numbers</a>, arXiv:0901.1397 [math.CO], 2009.

%H M. Hassani, <a href="http://jipam.vu.edu.au/article.php?sid=498">Equations and inequalities involving v_p(n!)</a>, J. Inequ. Pure Appl. Math. 6 (2005) vol. 2, #29.

%H A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 61. <a href="http://tohbook.info">Book's website</a>

%H R. Hinze, <a href="https://www.cs.ox.ac.uk/people/ralf.hinze/publications/CSC.pdf">Concrete stream calculus: An extended study</a>, J. Funct. Progr. 20 (5-6) (2010) 463-535, <a href="https://doi.org/10.1017/S0956796810000213">doi</a>, Section 3.2.3.

%H Clark Kimberling, <a href="https://doi.org/10.1016/S0012-365X(03)00085-2">Affinely recursive sets and orderings of languages</a>, Discrete Math., 274 (2004), 147-160.

%H Francis Laclé, <a href="https://hal.archives-ouvertes.fr/hal-03201180v2">2-adic parity explorations of the 3n+ 1 problem</a>, hal-03201180v2 [cs.DM], 2021.

%H Shuo Li, <a href="https://arxiv.org/abs/2007.08317">Palindromic length sequence of the ruler sequence and of the period-doubling sequence</a>, arXiv:2007.08317 [math.CO], 2020.

%H Nicolas Mallet, <a href="http://arxiv.org/abs/1507.05039">Trial for a proof of the Syracuse conjecture</a>, arXiv preprint arXiv:1507.05039 [math.GM], 2015.

%H S. Mazzanti, <a href="https://doi.org/10.1002/1521-3870(200201)48:1%3C93::AID-MALQ93%3E3.0.CO;2-8">Plain Bases for Classes of Primitive Recursive Functions</a>, Mathematical Logic Quarterly, 48 (2002).

%H Matthew Andres Moreno, Luis Zaman, and Emily Dolson, <a href="https://arxiv.org/abs/2409.06199">Structured Downsampling for Fast, Memory-efficient Curation of Online Data Streams</a>, arXiv:2409.06199 [cs.DS], 2024. See p. 5.

%H Sascha Mücke, <a href="https://mlai.cs.uni-bonn.de/lecturenotes/lamarr-qubo-bruteforce.pdf">Coding Nuggets Faster QUBO Brute-Force Solving</a>, TU Dortmund Univ. (Germany 2023).

%H S. Northshield, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Northshield/north4.html">An Analogue of Stern's Sequence for Z[sqrt(2)]</a>, Journal of Integer Sequences, 18 (2015), #15.11.6.

%H Numberphile, <a href="https://www.youtube.com/watch?v=laAtv310pyk">Hat Problems - Numberphile</a>

%H Giovanni Pighizzini, <a href="https://doi.org/10.1007/978-3-030-23247-4_4">Limited Automata: Properties, Complexity and Variants</a>, 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.

%H Simon Plouffe, <a href="http://arxiv.org/abs/1310.7195">On the values of the functions ... [zeta and Gamma] ...</a>, arXiv preprint arXiv:1310.7195 [math.NT], 2013.

%H A. Postnikov (MIT) and B. Sagan, <a href="http://arxiv.org/abs/math/0601339">What power of two divides a weighted Catalan number?</a>, arXiv:math/0601339 [math.CO], 2006.

%H Lara Pudwell and Eric Rowland, <a href="http://arxiv.org/abs/1510.02807">Avoiding fractional powers over the natural numbers</a>, arXiv:1510.02807 [math.CO] (2015). Also Electronic Journal of Combinatorics, Volume 25(2) (2018), #P2.27. See Section 2.

%H Ville Salo, <a href="http://arxiv.org/abs/1411.6644">Decidability and Universality of Quasiminimal Subshifts</a>, arXiv preprint arXiv:1411.6644 [math.DS], 2014.

%H Vladimir Shevelev, <a href="http://arXiv.org/abs/0904.2101">Several results on sequences which are similar to the positive integers</a>, arXiv:0904.2101 [math.NT], 2014.

%H F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Paul Tarau, <a href="http://scholar.google.com/scholar?cluster=284705751770513453">A Groupoid of Isomorphic Data Transformations</a>. Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.

%H P. M. B. Vitanyi, <a href="http://dx.doi.org/10.1137/0214001">An optimal simulation of counter machines</a>, SIAM J. Comput, 14:1(1985), 1-33.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Binary.html">Binary</a>, <a href="http://mathworld.wolfram.com/BinaryCarrySequence.html">Binary Carry Sequence</a>, and <a href="http://mathworld.wolfram.com/Double-FreeSet.html">Double-Free Set</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/P-adic_order">P-adic order</a>.

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = A001511(n) - 1.

%F a(2*n) = A050603(2*n) = A001511(n).

%F a(n) = A091090(n-1) + A036987(n-1) - 1.

%F a(n) = 0 if n is odd, otherwise 1 + a(n/2). - _Reinhard Zumkeller_, Aug 11 2001

%F Sum_{k=1..n} a(k) = n - A000120(n). - _Benoit Cloitre_, Oct 19 2002

%F G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - _Ralf Stephan_, Apr 10 2002

%F 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

%F Totally additive with a(p) = 1 if p = 2, 0 otherwise.

%F Dirichlet g.f.: zeta(s)/(2^s-1). - _Ralf Stephan_, Jun 17 2007

%F 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

%F a(n) = floor(A002487(n - 1) / A002487(n)). - _Reikku Kulon_, Oct 05 2008

%F Sum_{k=1..n} (-1)^A000120(n-k)*a(k) = (-1)^(A000120(n)-1)*(A000120(n) - A000035(n)). - _Vladimir Shevelev_, Mar 17 2009

%F a(A001147(n) + A057077(n-1)) = a(2*n). - _Vladimir Shevelev_, Mar 21 2009

%F For n>=1, a(A004760(n+1)) = a(n). - _Vladimir Shevelev_, Apr 15 2009

%F 2^(a(n)) = A006519(n). - _Philippe Deléham_, Apr 22 2009

%F a(n) = A063787(n) - A000120(n). - _Gary W. Adamson_, Jun 04 2009

%F a(C(n,k)) = A000120(k) + A000120(n-k) - A000120(n). - _Vladimir Shevelev_, Jul 19 2009

%F a(n!) = n - A000120(n). - _Vladimir Shevelev_, Jul 20 2009

%F 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

%F a(n) mod 2 = A096268(n-1). - _Robert G. Wilson v_, Jan 18 2012

%F 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

%F a((2*n-1)*2^p) = p, p >= 0 and n >= 1. - _Johannes W. Meijer_, Feb 04 2013

%F a(n) = A067255(n,1). - _Reinhard Zumkeller_, Jun 11 2013

%F a(n) = log_2(n - (n AND n-1)). - _Gary Detlefs_, Jun 13 2014

%F a(n) = 1 + A000120(n-1) - A000120(n), where A000120 is the Hamming weight function. - _Stanislav Sykora_, Jul 14 2014

%F 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

%F a((2*x-1)*2^n) = a((2*y-1)*2^n) for positive n, x and y. - _Juri-Stepan Gerasimov_, Aug 04 2016

%F a(n) = A285406(n) - A281264(n). - _Ralf Steiner_, Apr 18 2017

%F a(n) = A000005(n)/(A000005(2*n) - A000005(n)) - 1. - conjectured by _Velin Yanev_, Jun 30 2017, proved by _Nicholas Stearns_, Sep 11 2017

%F 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

%F a(n)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - _Gary Detlefs_, Feb 16 2019

%F Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - _Amiram Eldar_, Jul 11 2020

%F 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

%F a(n) = A070939(n) - A070939(A030101(n)). - _Andrew T. Porter_, Dec 16 2022

%F 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

%F a(n) = 1 - A088705(n). - _Chai Wah Wu_, Sep 18 2024

%e 2^3 divides 24, so a(24)=3.

%e From _Omar E. Pol_, Jun 12 2009: (Start)

%e Triangle begins:

%e   0;

%e   1,0;

%e   2,0,1,0;

%e   3,0,1,0,2,0,1,0;

%e   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;

%e   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;

%e   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,...

%e (End)

%p 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);

%p A007814 := n -> padic[ordp](n,2): seq(A007814(n), n=1..111); # _Peter Luschny_, Nov 26 2010

%t Table[IntegerExponent[n, 2], {n, 64}] (* _Eric W. Weisstein_ *)

%t IntegerExponent[Range[64], 2] (* _Eric W. Weisstein_, Feb 01 2024 *)

%t p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]

%t 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 *)

%t Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)

%t Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* _Robert G. Wilson v_, Jan 17 2011 *)

%o (PARI) A007814(n)=valuation(n,2);

%o (Haskell)

%o a007814 n = if m == 0 then 1 + a007814 n' else 0

%o             where (n', m) = divMod n 2

%o -- _Reinhard Zumkeller_, Jul 05 2013, May 14 2011, Apr 08 2011

%o (Haskell)

%o a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)

%o --  _Walt Rorie-Baety_, Mar 22 2013

%o (R) sapply(1:100,function(x) sum(gmp::factorize(x)==2)) # _Christian N. K. Anderson_, Jun 20 2013

%o (Magma) [Valuation(n, 2): n in [1..120]]; // _Bruno Berselli_, Aug 05 2013

%o (Python)

%o import math

%o def a(n): return int(math.log(n - (n & n - 1), 2)) # _Indranil Ghosh_, Apr 18 2017

%o (Python)

%o def A007814(n): return (~n & n-1).bit_length() # _Chai Wah Wu_, Jul 01 2022

%o (Scheme) (define (A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; _Antti Karttunen_, Oct 06 2017

%Y Cf. A011371 (partial sums), A094267 (first differences), A346070 (mod 4).

%Y Bisection of A050605 and |A088705|. Pairwise sums are A050603 and A136480. Difference of A285406 and A281264.

%Y This is Guy Steele's sequence GS(1, 4) (see A135416). Cf. A053398(1,n). Column/row 1 of table A050602.

%Y Cf. A007949 (3-adic), A112765 (5-adic), A122841 (6-adic), A214411 (7-adic), A122840 (10-adic).

%Y Cf. A000079, A002487, A006519, A051064, A055457, A063787, A215366, A220466.

%Y Cf. A086463 (Dgf at s=2).

%K nonn,nice,easy

%O 1,4

%A _John Tromp_, Dec 11 1996

%E Formula index adapted to the offset of A025480 by _R. J. Mathar_, Jul 20 2010

%E Edited by _Ralf Stephan_, Feb 08 2014