| Displaying 1-8 of 8 results found.
page
1
Column 3 of A050600: a(n) = add1c(n,3).
+20
3
1, 3, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 3, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 3, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 3, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 6, 6, 1, 3, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1
FORMULA
a(4n) = 1, a(4n+1)-2 = a(4n+2)-1 = a(4n+3)-1 = A001511(n) for all n >= 0. - M. F. Hasler, Feb 25 2019
PROG
(PARI) A050604(n)=if((n=divrem(n, 4))[2], valuation(n[1]+1, 2)+2+(n[2]<2), 1) \\ M. F. Hasler, Feb 25 2019
The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.
(Formerly M0127 N0051)
+10
464
1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1
COMMENTS
Number of 2's dividing 2*n.
a(n) is equivalently the exponent of the smallest power of 2 which does not divide n. - David James Sycamore, Oct 02 2023 a(n) - 1 is the number of trailing zeros in the binary expansion of n.
If you are counting in binary and the least significant bit is numbered 1, the next bit is 2, etc., a(n) is the bit that is incremented when increasing from n-1 to n. - Jud McCranie, Apr 26 2004 Number of steps to reach an integer starting with (n+1)/2 and using the map x -> x*ceiling(x) (cf. A073524). a(n) is the number of the disk to be moved at the n-th step of the optimal solution to Towers of Hanoi problem (comment from Andreas M. Hinz). Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 1). This is essentially equivalent to Hinz's comment. - Adam Kertesz, Jul 28 2001 a(n) is the Hamming distance between n and n-1 (in binary). This is equivalent to Kertesz's comments above. - Tak-Shing Chan (chan12(AT)alumni.usc.edu), Feb 25 2003
Let S(0) = {1}, S(n) = {S(n-1), S(n-1)-{x}, x+1} where x = last term of S(n-1); sequence gives S(infinity). - Benoit Cloitre, Jun 14 2003 The sum of all terms up to and including the first occurrence of m is 2^m-1. - Donald Sampson (marsquo(AT)hotmail.com), Dec 01 2003
m appears every 2^m terms starting with the 2^(m-1)th term. - Donald Sampson (marsquo(AT)hotmail.com), Dec 08 2003
Relation to C(n) = Collatz function iteration using only odd steps: a(n) is the number of right bits set in binary representation of A004767(n) (numbers of the form 4*m+3). So for m= A004767(n) it follows that there are exactly a(n) recursive steps where m<C(m). - Lambert Klasen (lambert.klasen(AT)gmx.de), Jan 23 2005 Between every two instances of any positive integer m there are exactly m distinct values (1 through m-1 and one value greater than m). - Franklin T. Adams-Watters, Sep 18 2006 Every prefix up to (but not including) the first occurrence of some k >= 2 is a palindrome. - Gary W. Adamson, Sep 24 2008 1 interleaved with (2 interleaved with (3 interleaved with ( ... ))). - Eric D. Burgess (ericdb(AT)gmail.com), Oct 17 2009
Given A000041, P(x) = A(x)/A(x^2) with P(x) = (1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + ...), A(x) = (1 + x + 3x^2 + 4x^3 + 10x^4 + 13x^5 + ...), A(x^2) = (1 + x^2 + 3x^4 + 4x^6 + 10x^8 + ...), where A092119 = (1, 1, 3, 4, 10, ...) = Euler transform of the ruler sequence, A001511. - Gary W. Adamson, Feb 11 2010 Subtracting 1 from every term and deleting any 0's yields the same sequence, A001511. - Ben Branman, Dec 28 2011 In the listing of the compositions of n as lists in lexicographic order, a(k) is the last part of composition(k) for all k <= 2^(n-1) and all n, see example. - Joerg Arndt, Nov 12 2012 According to Hinz, et al. (see links), this sequence was studied by Louis Gros in his 1872 pamphlet "Théorie du Baguenodier" and has therefore been called the Gros sequence.
First n terms comprise least squarefree word of length n using positive integers, where "squarefree" means that the word contains no consecutive identical subwords; e.g., 1 contains no square; 11 contains a square but 12 does not; 121 contains no square; both 1211 and 1212 have squares but 1213 does not; etc. - Clark Kimberling, Sep 05 2013 Length of 0-run starting from 2 (10, 100, 110, 1000, 1010, ...), or length of 1-run starting from 1 (1, 11, 101, 111, 1001, 1011, ...) of every second number, from right to left in binary representation. - Armands Strazds, Apr 13 2017 a(n) is also the frequency of the largest part 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 As A000005(n) equals the number of even divisors of 2n and A001227(n) = A001227(2n), the formula A001511(n) = A000005(n)/ A001227(n) might be read as "The number of even divisors of 2n is always divisible by the number of odd divisors of 2n" (where number of divisors means sum of zeroth powers of divisors). Conjecture: For any nonnegative integer k, the sum of the k-th powers of even divisors of n is always divisible by the sum of the k-th powers of odd divisors of n. - Ivan N. Ianakiev, Jul 06 2019 To construct the sequence, start from 1's separated by a place 1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,...
Then put the 2's in every other remaining place
1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,...
Then the 3's in every other remaining place
1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,...
Then the 4's in every other remaining place
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,4,1,2,1,...
By iterating this process, we get the ruler function 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,... (End)
a(n) is the smallest positive integer that does not occur in the coincidences of the sequence so far a(1..n-1) and its reverse. - Neal Gersh Tolunsky, Jan 18 2023
REFERENCES
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 2nd ed., 2001-2003; see Dim- and Dim+ on p. 98; Dividing Rulers, on pp. 436-437; The Ruler Game, pp. 469-470; Ruler Fours, Fives, ... Fifteens on p. 470.
L. Gros, Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E22.
A. M. Hinz, The Tower of Hanoi, in Algebras and combinatorics (Hong Kong, 1997), 277-289, Springer, Singapore, 1999.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589.
Andrew Schloss, "Towers of Hanoi" composition, in The Digital Domain. Elektra/Asylum Records 9 60303-2, 1983. Works by Jaffe (Finale to "Silicon Valley Breakdown"), McNabb ("Love in the Asylum"), Schloss ("Towers of Hanoi"), Mattox ("Shaman"), Rush, Moorer ("Lions are Growing") and others.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
J. C. Lagarias and N. J. A. Sloane, Approximate squaring ( pdf, ps), Experimental Math., 13 (2004), 113-128. Joseph Rosenbaum, Elementary Problem E319, American Mathematical Monthly, volume 45, number 10, December 1938, pages 694-696. (The A indices in P at equations 1 and 2.)
FORMULA
Multiplicative with a(p^e) = e+1 if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001 For any real x > 1/2: lim_{N->infinity} (1/N)*Sum_{n=1..N} x^(-a(n)) = 1/(2*x-1); also lim_{N->infinity} (1/N)*Sum_{n=1..N} 1/a(n) = log(2). - Benoit Cloitre, Nov 16 2001 s(n) = Sum_{k=1..n} a(k) is asymptotic to 2*n since s(n) = 2*n - A000120(n). - Benoit Cloitre, Aug 31 2002 For any n >= 0, for any m >= 1, a(2^m*n + 2^(m-1)) = m. - Benoit Cloitre, Nov 24 2002 a(n) = Sum_{d divides n and d is odd} mu(d)*tau(n/d). - Vladeta Jovovic, Dec 04 2002 G.f.: A(x) = Sum_{k>=0} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Dec 24 2002 a(1) = 1; for n > 1, a(n) = a(n-1) + (-1)^n*a(floor(n/2)). - Vladeta Jovovic, Apr 25 2003 A fixed point of the mapping 1->12; 2->13; 3->14; 4->15; 5->16; ... . - Philippe Deléham, Dec 13 2003 Ordinal transform of A003602. - Franklin T. Adams-Watters, Aug 28 2006 (The ordinal transform of a sequence b_0, b_1, b_2, ... is the sequence a_0, a_1, a_2, ... where a_n is the number of times b_n has occurred in {b_0 ... b_n}.) Could be extended to n <= 0 using a(-n) = a(n), a(0) = 0, a(2*n) = a(n)+1 unless n=0. - Michael Somos, Sep 30 2006 Sequence = A129360 * A000005 = M*V, where M = an infinite lower triangular matrix and V = d(n) as a vector: [1, 2, 2, 3, 2, 4, ...]. - Gary W. Adamson, Apr 15 2007 Dirichlet g.f.: zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007 a(n) = -Sum_{d divides n} mu(2*d)*tau(n/d). - Benoit Cloitre, Jun 21 2007 G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n*( 1 - x^n ). - Paul D. Hanna, Jun 22 2007 With S(n): 2^n - 1 first elements of the sequence then S(0) = {} (empty list) and if n > 0, S(n) = S(n-1), n, S(n-1). - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
a(n+1) = 1 + Sum_{j=0..ceiling(log_2(n+1))} (j * (1 - abs(sign((n mod 2^(j + 1)) - 2^j + 1)))). - Enrico Borba, Oct 01 2015 a(n) = log_2((Xor(2*n,2*n-1)+1)/2). - Gary Detlefs, Dec 13 2018 (2^(a(n)-1)-1)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Dec 14 2018 a(n) = Sum_{j=1..r} (j/2^j)*(Product_{k=1..j} (1 - (-1)^floor( (n+2^(j-1))/2^(k-1) ))), for n < a predefined 2^r. - Adriano Caroli, Sep 30 2019
EXAMPLE
For example, 2^1|2, 2^2|4, 2^1|6, 2^3|8, 2^1|10, 2^2|12, ... giving the initial terms 1, 2, 1, 3, 1, 2, ...
Triangle begins:
1;
2,1;
3,1,2,1;
4,1,2,1,3,1,2,1;
5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,...
(End)
S(0) = {} S(1) = 1 S(2) = 1, 2, 1 S(3) = 1, 2, 1, 3, 1, 2, 1 S(4) = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
The 16 compositions of 5 as lists in lexicographic order:
[ n] a(n) composition
[ 1] [ 1] [ 1 1 1 1 1 ]
[ 2] [ 2] [ 1 1 1 2 ]
[ 3] [ 1] [ 1 1 2 1 ]
[ 4] [ 3] [ 1 1 3 ]
[ 5] [ 1] [ 1 2 1 1 ]
[ 6] [ 2] [ 1 2 2 ]
[ 7] [ 1] [ 1 3 1 ]
[ 8] [ 4] [ 1 4 ]
[ 9] [ 1] [ 2 1 1 1 ]
[10] [ 2] [ 2 1 2 ]
[11] [ 1] [ 2 2 1 ]
[12] [ 3] [ 2 3 ]
[13] [ 1] [ 3 1 1 ]
[14] [ 2] [ 3 2 ]
[15] [ 1] [ 4 1 ]
[16] [ 5] [ 5 ]
a(n) is the last part in each list.
(End)
Also written as a triangle in which the right border gives A000027 and row lengths give A011782 and row sums give A000079 the sequence begins: 1;
2;
1,3;
1,2,1,4;
1,2,1,3,1,2,1,5;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7;
(End)
G.f. = x + 2*x^2 + x^3 + 3*x^4 + x^5 + 2*x^6 + x^7 + 4*x^8 + x^9 + 2*x^10 + ...
MAPLE
# This is the binary logarithm of the denominator of (256^n-1)B_{8n}/n, in Maple parlance a := n -> log[2](denom((256^n-1)*bernoulli(8*n)/n)). - Peter Luschny, May 31 2009 a:= n-> ilog2((Bits[Xor](2*n, 2*n-1)+1)/2): seq(a(n), n=1..50); # Gary Detlefs, Dec 13 2018
MATHEMATICA
Array[ If[ Mod[ #, 2] == 0, FactorInteger[ # ][[1, 2]], 0] &, 105] + 1 (* or *)
Nest[ Flatten[ # /. a_Integer -> {1, a + 1}] &, {1}, 7] (* Robert G. Wilson v, Mar 04 2005 *) myHammingDistance[n_, m_] := Module[{g = Max[m, n], h = Min[m, n]}, b1 = IntegerDigits[g, 2]; b2 = IntegerDigits[h, 2, Length[b1]]; HammingDistance[b1, b2]] (* Vladimir Shevelev A206853 *) Table[ myHammingDistance[n, n - 1], {n, 111}] (* Robert G. Wilson v, Apr 05 2012 *) Table[Position[Reverse[IntegerDigits[n, 2]], 1, 1, 1], {n, 110}]//Flatten (* Harvey P. Dale, Aug 18 2017 *)
PROG
(PARI) a(n) = sum(k=0, floor(log(n)/log(2)), floor(n/2^k)-floor((n-1)/2^k)) /* Ralf Stephan */ (PARI) a(n)=if(n%2, 1, factor(n)[1, 2]+1) /* Jon Perry, Jun 06 2004 */ (PARI) {a(n) = if( n, valuation(n, 2) + 1, 0)}; /* Michael Somos, Sep 30 2006 */ (PARI) {a(n)=if(n==1, 1, polcoeff(x-sum(k=1, n-1, a(k)*x^k*(1-x^k)*(1-x+x*O(x^n))), n))} /* Paul D. Hanna, Jun 22 2007 */ (Haskell)
a001511 n = length $ takeWhile ((== 0) . (mod n)) a000079_list
(Haskell) a001511 n | odd n = 1 | otherwise = 1 + a001511 (n `div` 2)
(Sage) [valuation(2*n, 2) for n in (1..105)] # Bruno Berselli, Nov 23 2015 (Magma) [Valuation(2*n, 2): n in [1..105]]; // Bruno Berselli, Nov 23 2015 (MATLAB) nmax=5; r=1; for n=2:nmax; r=[r n r]; end % Adriano Caroli, Feb 26 2016 (Python)
def a(n): return bin(n)[2:][::-1].index("1") + 1 # Indranil Ghosh, May 11 2017 (Python)
(Scheme) (define ( A001511 n) (let loop ((n n) (e 1)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017
CROSSREFS
This is Guy Steele's sequence GS(4, 2) (see A135416). Cf. A000005, A000041, A000079, A003188, A003278, A003602, A007949, A018238, A047999, A051731, A054525, A054852, A065176, A089080, A092119, A117303, A129360, A130093, A173238, A181988, A220466.
KEYWORD
mult, nonn, nice, easy, core, hear, changed
n appears n+1 times. Also the array A(n,k) = n+k (n >= 0, k >= 0) read by antidiagonals. Also inverse of triangular numbers.
+10
362
0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12
COMMENTS
Also triangle read by rows: T(n,k), n>=0, k>=0, in which n appears n+1 times in row n. - Omar E. Pol, Jul 15 2012 The PARI functions t1, t2 can be used to read a triangular array T(n,k) (n >= 0, 0 <= k <= n-1) by rows from left to right: n -> T(t1(n), t2(n)). - Michael Somos, Aug 23 2002 Number of terms in partition of n with greatest number of distinct terms. - Amarnath Murthy, May 20 2001 Summation table for (x+y) = (0+0),(0+1),(1+0),(0+2),(1+1),(2+0), ...
Also the number of triangular numbers less than or equal to n, not counting 0 as triangular. - Robert G. Wilson v, Oct 21 2005 Also the maximum number of 1's contained in the list of hook-lengths of a partition of n. E.g., a(4)=2 because hooks of partitions of n=4 comprise {4,3,2,1}, {4,2,1,1}, {3,2,2,1}, {4,1,2,1}, {4,3,2,1} where the number of 1's in each is 1,2,1,2,1. Hence the maximum is 2. - T. Amdeberhan, Jun 03 2012 Fan, Yang, and Yu (2012) prove a conjecture of Amdeberhan on the generating function of a(n). - Jonathan Sondow, Dec 17 2012 Also the number of partitions of n into distinct parts p such that max(p) - min(p) <= length(p). - Clark Kimberling, Apr 18 2014 Also the maximum number of occurrences of any single value among the previous terms. - Ivan Neretin, Sep 20 2015 Also number of peaks in the largest Dyck path of the symmetric representation of sigma(n), n >= 1. Cf. A237593. - Omar E. Pol, Dec 19 2016
FORMULA
a(n) = floor(-1/2 + sqrt(2*n+b)) with 1/4 <= b < 9/4 or a(n) = floor((sqrt(8*n+b)-1)/2) with 1 <= b < 9. - Michael A. Childers (childers_moof(AT)yahoo.com), Nov 11 2001
a(n) = f(n,0) with f(n,k) = k if n <= k, otherwise f(n-k-1, k+1). - Reinhard Zumkeller, May 23 2009 G.f.: (1-x)^(-1)*Sum_{n>=1} x^(n*(n+1)/2) = (Theta_2(0,x^(1/2)) - 2*x^(1/8))/(2*x^(1/8)*(1-x)) where Theta_2 is a Jacobi Theta function. - Robert Israel, May 21 2015 a(n+1) = a(n-a(n)) + 1, a(0) = 0. - Rok Cestnik, Dec 29 2020
EXAMPLE
G.f. = x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 3*x^9 + 4*x^10 + ...
As triangle, the sequence starts
0;
1, 1;
2, 2, 2;
3, 3, 3, 3;
4, 4, 4, 4, 4;
5, 5, 5, 5, 5, 5;
6, 6, 6, 6, 6, 6, 6;
7, 7, 7, 7, 7, 7, 7, 7;
8, 8, 8, 8, 8, 8, 8, 8, 8;
...
MAPLE
a := [ 0 ]: for i from 1 to 15 do for j from 1 to i+1 do a := [ op(a), i ]; od: od: a;
floor((sqrt(1+8*n)-1)/2) ;
MATHEMATICA
f[n_] := Floor[(Sqrt[1 + 8n] - 1)/2]; Table[ f[n], {n, 0, 87}] (* Robert G. Wilson v, Oct 21 2005 *) Table[x, {x, 0, 13}, {y, 0, x}] // Flatten
T[ n_, k_] := If[ n >= k >= 0, n, 0]; (* Michael Somos, Dec 22 2016 *) Flatten[Table[PadRight[{}, n+1, n], {n, 0, 12}]] (* Harvey P. Dale, Jul 03 2021 *)
PROG
(PARI) t1(n)=floor(-1/2+sqrt(2+2*n)) /* A003056 */ (PARI) t2(n)=n-binomial(floor(1/2+sqrt(2+2*n)), 2) /* A002262 */ (Haskell)
a003056 = floor . (/ 2) . (subtract 1) .
sqrt . (+ 1) . (* 8) . fromIntegral
a003056_row n = replicate (n + 1) n
a003056_tabl = map a003056_row [0..]
a003056_list = concat $ a003056_tabl
(Python)
from math import isqrt
def A003056(n): return (k:=isqrt(m:=n+1<<1))+int((m<<2)>(k<<2)*(k+1)+1)-1 # Chai Wah Wu, Jul 26 2022
CROSSREFS
Cf. A000196, A000217, A000462, A001227, A001462, A001614, A004247 (multiplication table), A006463 (partial sums), A016655, A050600, A050602, A048645, A122797, A131507, A238005.
a(n) = (n AND floor(n/2)), where AND is bitwise and-operator ( A004198).
+10
14
0, 0, 0, 1, 0, 0, 2, 3, 0, 0, 0, 1, 4, 4, 6, 7, 0, 0, 0, 1, 0, 0, 2, 3, 8, 8, 8, 9, 12, 12, 14, 15, 0, 0, 0, 1, 0, 0, 2, 3, 0, 0, 0, 1, 4, 4, 6, 7, 16, 16, 16, 17, 16, 16, 18, 19, 24, 24, 24, 25, 28, 28, 30, 31, 0, 0, 0, 1, 0, 0, 2, 3, 0, 0, 0, 1, 4, 4, 6, 7, 0
COMMENTS
To prove that (n AND floor(n/2)) = (3n-(n XOR 2n))/4 (= A048728(n)/4), we first multiply both sides by 4, to get 2*(n AND 2n) = (3n - (n XOR 2n)) and then rearrange terms: 3n = (n XOR 2n) + 2*(n AND 2n), which fits perfectly to the identity A+B = (A XOR B) + 2*(A AND B) (given by Schroeppel in HAKMEM link). The number of 1's through 4*2^n appears to yield A000045(n+1). - Ben Burns, Jun 12 2017
FORMULA
a(n) = A048728(n)/4. (This was the original definition. AND-formula found Jan 01 2007).
MAPLE
seq(Bits:-And(n, floor(n/2)), n=0..200); # Robert Israel, Feb 29 2016
MATHEMATICA
Table[BitAnd[n, Floor[n/2]], {n, 0, 127}] (* T. D. Noe, Aug 13 2012 *)
Square array A(x,y), read by antidiagonals, where A(x,y) = 0 if (x AND y) = 0, otherwise A(x,y) = 1+A(x XOR y, 2*(x AND y)).
+10
9
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2, 3, 1, 3, 2, 3, 0, 0, 0, 2, 2, 1, 1, 2, 2, 0, 0, 0, 1, 0, 2, 1, 1, 1, 2, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 2, 1, 2, 0, 2, 1, 2, 0, 2, 1, 2, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0
COMMENTS
Array is symmetric and is read by antidiagonals: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), etc. - Antti Karttunen, Sep 04 2023 Comment from N. J. A. Sloane, Jun 21 2011: Apparently the same as the following sequence. Infinite square array read by antidiagonals, where T(m,n) = length of longest carry propagation when u and v are added in binary, for u >= 0, v >= 0. See A192054 for definition of carry propagation. For example, T(3,5) = 3, since adding 011 + 101 in binary, the initial 1 propagates three places.
EXAMPLE
The top left corner of the square array:
| 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
-----+--------------------------------------------------------
0 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1 | 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
2 | 0, 0, 1, 1, 0, 0, 2, 2, 0, 0, 1, 1, 0, 0, 3, 3,
3 | 0, 2, 1, 1, 0, 3, 2, 2, 0, 2, 1, 1, 0, 4, 3, 3,
4 | 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 2, 2, 2, 2,
5 | 0, 1, 0, 3, 1, 1, 1, 2, 0, 1, 0, 4, 2, 2, 2, 2,
6 | 0, 0, 2, 2, 1, 1, 1, 1, 0, 0, 3, 3, 2, 2, 2, 2,
7 | 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 2, 2, 2,
8 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
9 | 0, 1, 0, 2, 0, 1, 0, 4, 1, 1, 1, 2, 1, 1, 1, 3,
10 | 0, 0, 1, 1, 0, 0, 3, 3, 1, 1, 1, 1, 1, 1, 2, 2,
11 | 0, 2, 1, 1, 0, 4, 3, 3, 1, 2, 1, 1, 1, 3, 2, 2,
12 | 0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1,
13 | 0, 1, 0, 4, 2, 2, 2, 2, 1, 1, 1, 3, 1, 1, 1, 2,
14 | 0, 0, 3, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1,
15 | 0, 4, 3, 3, 2, 2, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1,
etc.
MAPLE
add3c := proc(a, b) option remember; if(0 = ANDnos(a, b)) then RETURN(0); else RETURN(1+add3c(XORnos(a, b), 2*ANDnos(a, b))); fi; end;
MATHEMATICA
a[n_, k_] := a[n, k] = If[0 == BitAnd[n, k], 0, 1 + a[BitXor[n, k], 2*BitAnd[n, k]]]; Table[a[n - k, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 16 2014, updated Mar 06 2016 after Maple *)
PROG
(PARI)
up_to = 120;
A050602sq(x, y) = if(!bitand(x, y), 0, 1+A050602sq(bitxor(x, y), 2*bitand(x, y)));
A050602list(up_to) = { my(v = vector(up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A050602sq(col, a-col))); (v); };
v050602 = A050602list(up_to);
CROSSREFS
Cf. also A072030 ( A285721) for similar arrays computed for an elementary Euclidean algorithm.
1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 5, 5, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 6, 6, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 5, 5, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 4
COMMENTS
Column 2 of A050600: a(n) = add1c(n,2). Consider the Collatz (or 3x+1) problem and the iterative sequence c(k) where c(0)=n is a positive integer and c(k+1)=c(k)/2 if c(k) is even, c(k+1)=(3*c(k)+1)/2 if c(k) is odd. Then a(n) is the minimum number of iterations in order to have c(a(n)) odd if n is even or c(a(n)) even if n is odd. - Benoit Cloitre, Nov 16 2001
FORMULA
G.f.: (1+x)/x^2 * Sum(k>=1, x^(2^k)/(1-x^(2^k))). - Ralf Stephan, Apr 12 2002 Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=0..m} a(k) = 2. - Amiram Eldar, Sep 15 2022
MATHEMATICA
With[{c=Table[Position[Reverse[IntegerDigits[n, 2]], 1, 1, 1], {n, 110}]// Flatten}, Riffle[c, c]] (* Harvey P. Dale, Dec 06 2018 *)
PROG
(PARI) {a(n) = my(A); if( n<0, 0, A = sum(k=1, length( binary(n+2)) - 1, x^(2^k) / (1 - x^(2^k)), x^3 * O(x^n)); polcoeff( A * (1 + x) / x^2, n))}; /* Michael Somos, May 11 2014 */ (Python)
T(n,k) = length of longest carry sequence when adding k to n in binary representation, 1 <= k <= n (triangular array).
+10
4
1, 0, 1, 2, 1, 1, 0, 0, 0, 1, 1, 0, 3, 1, 1, 0, 2, 2, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2, 0, 1, 0, 4, 1, 1, 0, 1, 1, 0, 0, 3, 3, 1, 1, 1, 2, 1, 1, 0, 4, 3, 3, 1, 2, 1, 1, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 4, 2, 2, 2, 2, 1, 1, 1, 3, 1, 1, 0, 3, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1
EXAMPLE
Triangle begins:
1
0 1
2 1 1
0 0 0 1
1 0 3 1 1
0 2 2 1 1 1
3 2 2 1 2 1 1
PROG
(Haskell)
import Data.Bits (xor, (.&.), shiftL)
a080080 :: Int -> Int -> Int
a080080 n k = addc n k 0 where
addc x y z | y == 0 = z - 1
| otherwise = addc (x `xor` y) (shiftL (x .&. y) 1) (z + 1)
a080080_row n = map (a080080 n) [1..n]
a080080_tabl = map a080080_row [1..]
Recursion counts for summation table A003056 with formula a(0,x) = x, a(y,0) = y, a(y,x) = a((y XOR x),2*(y AND x))
+10
2
0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 2, 1, 2, 0, 0, 1, 2, 2, 1, 0, 0, 2, 1, 1, 1, 2, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 3, 2, 3, 1, 3, 2, 3, 0, 0, 1, 3, 3, 2, 2, 3, 3, 1, 0, 0, 2, 1, 3, 2, 1, 2, 3, 1, 2, 0, 0, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 0, 0, 3, 2, 3, 1, 3, 1, 3, 1, 3, 2, 3, 0, 0, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 0, 0, 2, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 0
FORMULA
a(n) -> add2c( (n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n) )
MAPLE
add2c := proc(a, b) option remember; if((0 = a) or (0 = b)) then RETURN(0); else RETURN(1+add_c(XORnos(a, b), 2*ANDnos(a, b))); fi; end;
MATHEMATICA
trinv[n_] := Floor[(1/2)*(Sqrt[8*n + 1] + 1)];
Sum2c[a_, b_] := Sum2c[a, b] = If[0 == a || 0 == b, Return[0], Return[ Sum2c[BitXor[a, b], 2*BitAnd[a, b]] + 1]];
a[n_] := Sum2c[n - (1/2)*trinv[n]*(trinv[n] - 1), (trinv[n] - 1)*(trinv[ n]/2 + 1) - n];
Search completed in 0.080 seconds
|