|
| |
|
|
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.
|
|
227
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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
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
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 = mod(k,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 [Allouche and Shallit]
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
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.
K. Atanassov, On the 37-th and the 38-th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers (2009) http://arxiv.org/abs/0901.1397. Discrete Math., 309 (2009), 6245-6254. [N. J. A. Sloane, Nov 27 2009]
C. Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160. [N. J. A. Sloane, Jan 31 2012]
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.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..10000
K. Atanassov, On Some of Smarandache's Problems
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ć, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 61. Book's website
V. Shevelev, Several results on sequences which are similar to the positive integers [Vladimir Shevelev, Apr 15 2009]
F. Smarandache, Only Problems, Not Solutions!.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Wikipedia, P-adic_order.
Eric Weisstein's World of Mathematics, Binary Carry Sequence
Eric Weisstein's World of Mathematics, Double-Free Set
Eric Weisstein's World of Mathematics, Binary
|
|
|
FORMULA
|
a(n) = A001511(n)-1
a(2*n) = A050603(2*n) = A001511(n)
a(n) = A091090(n-1) + A036987(n-1) - 1
a(n) = if n is odd then 0 else 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, infinity, x^(2^k)/(1-x^(2^k))). - Ralf Stephan, Apr 10 2002
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
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: a007814(k) = c(0) + c(0).c(1) + c(0).c(1).c(2) + ... + c(0).c(1)...c(n-1); a007814(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 DELEHAM, 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} \frac{r}{2^{r+1}} sum_{k=0..2^{r+1}-1} e^{\frac{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
|
|
|
EXAMPLE
|
2^3 divides 24, so a(24)=3.
Contribution 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)
|
|
|
MAPLE
|
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: seq(ord(n), n=1..111);
A007814 := n -> padic[ordp](n, 2): seq(A007814(n), n=1..111); # [Peter Luschny, Nov 26 2010]
|
|
|
MATHEMATICA
|
Table[IntegerExponent[n, 2], {n, 64}] (Eric W. Weisstein)
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]
|
|
|
PROG
|
(PARI) A007814(n)=valuation(n, 2);
(Haskell)
a007814 n = length $ takeWhile ((== 0) . (mod n)) $ iterate (* 2) 2
-- Reinhard Zumkeller, May 14 2011, Apr 08 2011
(Haskell)
a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)
(Matlab)
%Input:
% n: an integer
%Output:
% m: max power of 2 such that 2^m divides n
% M: 1-by-K matrix where M(i) is the max power of 2 such that 2^M(i) divides n
function [m, M] = Omega2(n)
M = NaN*zeros(1, n);
M(1)=0; M(2)=1;
for k=3:n
if M(k-2)~=0
M(k)=M(k-k/2)+1;
else
M(k)=0;
end
end
m=M(end);
end
% Redjan Shabani, July 17 2012
|
|
|
CROSSREFS
|
A053398(1,n).
Column/row 1 of table A050602.
First differences of A011371. Bisection of A050605 and |A088705|.
Cf. A122840, A122841, A007949 (3-adic), A112765 (5-adic), A214411 (7-adic).
See A050603 and A136480 for a(n) + a(n+1).
This is Guy Steele's sequence GS(1, 4) (see A135416).
Cf. A006519, A002487, A063787, A000079, A051064, A055457, A220466.
Sequence in context: A162590 A191258 A191255 * A225345 A083280 A060689
Adjacent sequences: A007811 A007812 A007813 * A007815 A007816 A007817
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
John Tromp
|
|
|
EXTENSIONS
|
Formula index adapted to the offset of A025480 - R. J. Mathar, Jul 20 2010
|
|
|
STATUS
|
approved
|
| |
|
|
