A159913 -id:A159913

Search: a159913 -id:a159913

Displaying 1-3 of 3 results found.

page 1

A159912

Partial sums of A159913(k) = 2^bitcount(2k+1)-1 = A038573(2k+1), bitcount=A000120.

+20
5

0, 1, 4, 7, 14, 17, 24, 31, 46, 49, 56, 63, 78, 85, 100, 115, 146, 149, 156, 163, 178, 185, 200, 215, 246, 253, 268, 283, 314, 329, 360, 391, 454, 457, 464, 471, 486, 493, 508, 523, 554, 561, 576, 591, 622, 637, 668, 699, 762, 769, 784, 799, 830, 845, 876, 907

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

More precisely, a(n)=sum(i<n, A159913(i)), since we want the sequence to start with a(0)=0 and not with A159913(0)=1.

a(n) is also the total number of ON cells after n generations in the outward corner version of the Ulam-Warburton cellular automaton of A147562, and a(n) is also the total number of Y-toothpicks after n generations in the outward corner version of the Y-toothpick structure of A160120. - David Applegate and Omar E. Pol, Jan 24 2016

LINKS

Paolo Xausa, Table of n, a(n) for n = 0..10000

David Applegate, The movie version

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 6, 30.

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Index entries for sequences related to cellular automata

Index entries for sequences related to toothpick sequences

FORMULA

a(n) = sum( i=0...n-1, A159913(i)) = sum(i=0..n-1, 2^A000120(i))*2-n

a(n) = n + (A160720(n) - 1)/2 = n + 2*(A266532(n) - 1)/3 = n + 2*A267700(n-1), n >= 1. - Omar E. Pol, Jan 25 2016

MATHEMATICA

Accumulate@ Table[2^(DigitCount[n, 2][[1]] + 1) - 1, {n, 0, 54}] (* Michael De Vlieger, Jan 25 2016 *)

PROG

(PARI) A159912(n)=sum(i=0, n-1, 1<<norml2(binary(i)))*2-n

CROSSREFS

Cf. A000120, A038573, A147562, A159913, A160120, A160720, A266532, A267700.

KEYWORD

nonn

AUTHOR

M. F. Hasler, May 03 2009

STATUS

approved

A001316

Gould's sequence: a(n) = Sum_{k=0..n} (binomial(n,k) mod 2); number of odd entries in row n of Pascal's triangle (A007318); a(n) = 2^A000120(n).
(Formerly M0297 N0109)

+10
199

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Also called Dress's sequence.

This sequence might be better called Glaisher's sequence, since James Glaisher showed that odd binomial coefficients are counted by 2^A000120(n) in 1899. - Eric Rowland, Mar 17 2017 [However, the name "Gould's sequence" is deeply entrenched in the literature. - N. J. A. Sloane, Mar 17 2017] [Named after the American mathematician Henry Wadsworth Gould (b. 1928). - Amiram Eldar, Jun 19 2021]

All terms are powers of 2. The first occurrence of 2^k is at n = 2^k - 1; e.g., the first occurrence of 16 is at n = 15. - Robert G. Wilson v, Dec 06 2000

a(n) is the highest power of 2 dividing binomial(2n,n) = A000984(n). - Benoit Cloitre, Jan 23 2002

Also number of 1's in n-th row of triangle in A070886. - Hans Havermann, May 26 2002. Equivalently, number of live cells in generation n of a one-dimensional cellular automaton, Rule 90, starting with a single live cell. - Ben Branman, Feb 28 2009. Ditto for Rule 18. - N. J. A. Sloane, Aug 09 2014. This is also the odd-rule cellular automaton defined by OddRule 003 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015

Also number of numbers k, 0<=k<=n, such that (k OR n) = n (bitwise logical OR): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080098. - Reinhard Zumkeller, Jan 28 2003

To construct the sequence, start with 1 and use the rule: If k >= 0 and a(0),a(1),...,a(2^k-1) are the first 2^k terms, then the next 2^k terms are 2*a(0),2*a(1),...,2*a(2^k-1). - Benoit Cloitre, Jan 30 2003

Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Mar 03 2004

The odd entries in Pascal's triangle form the Sierpiński Gasket (a fractal). - Amarnath Murthy, Nov 20 2004

Row sums of Sierpiński's Gasket A047999. - Johannes W. Meijer, Jun 05 2011

Fixed point of the morphism "1" -> "1,2", "2" -> "2,4", "4" -> "4,8", ..., "2^k" -> "2^k,2^(k+1)", ... starting with a(0) = 1; 1 -> 12 -> 1224 -> = 12242448 -> 122424482448488(16) -> ... . - Philippe Deléham, Jun 18 2005

a(n) = number of 1's of stage n of the one-dimensional cellular automaton with Rule 90. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 01 2006

a(33)..a(63) = A117973(1)..A117973(31). - Stephen Crowley, Mar 21 2007

Or the number of solutions of the equation: A000120(x) + A000120(n-x) = A000120(n). - Vladimir Shevelev, Jul 19 2009

For positive n, a(n) equals the denominator of the permanent of the n X n matrix consisting entirely of (1/2)'s. - John M. Campbell, May 26 2011

Companions to A001316 are A048896, A105321, A117973, A151930 and A191488. They all have the same structure. We observe that for all these sequences a((2*n+1)*2^p-1) = C(p)*A001316(n), p >= 0. If C(p) = 2^p then a(n) = A001316(n), if C(p) = 1 then a(n) = A048896(n), if C(p) = 2^p+2 then a(n) = A105321(n+1), if C(p) = 2^(p+1) then a(n) = A117973(n), if C(p) = 2^p-2 then a(n) = (-1)*A151930(n) and if C(p) = 2^(p+1)+2 then a(n) = A191488(n). Furthermore for all a(2^p - 1) = C(p). - Johannes W. Meijer, Jun 05 2011

a(n) = number of zeros in n-th row of A219463 = number of ones in n-th row of A047999. - Reinhard Zumkeller, Nov 30 2012

This is the Run Length Transform of S(n) = {1,2,4,8,16,...} (cf. A000079). The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Sep 05 2014

A105321(n+1) = a(n+1) + a(n). - Reinhard Zumkeller, Nov 14 2014

a(n) = A261363(n,n) = number of distinct terms in row n of A261363 = number of odd terms in row n+1 of A261363. - Reinhard Zumkeller, Aug 16 2015

From Gary W. Adamson, Aug 26 2016: (Start)

A production matrix for the sequence is lim_{k->infinity} M^k, the left-shifted vector of M:

1, 0, 0, 0, 0, ...

2, 0, 0, 0, 0, ...

0, 1, 0, 0, 0, ...

0, 2, 0, 0, 0, ...

0, 0, 1, 0, 0, ...

0, 0, 2, 0, 0, ...

0, 0, 0, 1, 0, ...

...

The result is equivalent to the g.f. of Apr 06 2003: Product_{k>=0} (1 + 2*z^(2^k)). (End)

Number of binary palindromes of length n for which the first floor(n/2) symbols are themselves a palindrome (Ji and Wilf 2008). - Jeffrey Shallit, Jun 15 2017

REFERENCES

Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, p. 75ff.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 145-151.

James W. L. Glaisher, On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quarterly Journal of Pure and Applied Mathematics, Vol. 30 (1899), pp. 150-156.

H. W. Gould, Exponential Binomial Coefficient Series. Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sep 1961.

Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram, Algebraic properties of cellular automata, Comm. Math. Physics, Vol. 93 (1984), pp. 219-258. Reprinted in Theory and Applications of Cellular Automata, S Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113

Manfred R. Schroeder, Fractals, Chaos, Power Laws, W. H. Freeman, NY, 1991, page 383.

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

Andrew Wuensche, Exploring Discrete Dynamics, Luniver Press, 2011. See Fig. 2.3.

LINKS

Indranil Ghosh, Table of n, a(n) for n = 0..50000 (terms 0..1000 from T. D. Noe)

David Applegate, Omar E. Pol, and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]

Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.

Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.

George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.

Christina Talar Bekaroğlu, Analyzing Dynamics of Larger than Life: Impacts of Rule Parameters on the Evolution of a Bug's Geometry, Master's thesis, Calif. State Univ. Northridge (2023). See pp. 91-92.

Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Transactions (2021) Vol. 1, No. 1, Article 1.

Neil J. Calkin, Eunice Y. S. Chan, Robert M. Corless, David J. Jeffrey, and Piers W. Lawrence, A Fractal Eigenvector, arXiv:2104.01116 [math.DS], 2021.

Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.

Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory, Vol. 117 (2006), pp. 191-215.

Philippe Dumas, Diviser pour régner Comportement asymptotique.

Philippe Dumas, Diviser pour régner Comportement asymptotique. (has many references)

Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.

Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.

Steven R. Finch, Stolarsky-Harborth Constant. [Broken link]

Steven R. Finch, Stolarsky-Harborth Constant. [From the Wayback machine]

Michael Gilleland, Some Self-Similar Integer Sequences.

Po-Yi Huang and Wen-Fong Ke, Sequences Derived from The Symmetric Powers of {1, 2, ..., k}, arXiv:2307.07733 [math.CO], 2023.

Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, Amer. Math. Monthly, Vol. 115, No. 5 (2008), pp. 447-451.

Alan J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata....

Hans Montanus and Ron Westdijk, Cellular Automation and Binomials, Green Blue Mathematics (2022), p. 57.

Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.

Tomaz Pisanski and Thomas W. Tucker, Growth in Repeated Truncations of Maps, Atti Sem. Mat. Fis. Univ. Modena, Vol. 49 (2001), suppl., pp. 167-176.

David G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., Vol. 67, No. 5 (1994), pp. 323-344.

Joseph M. Shunia, A Polynomial Ring Connecting Central Binomial Coefficients and Gould's Sequence, arXiv:2312.00302 [math.GM], 2023.

N. J. A. Sloane, Illustration of first 20 generations of Rule 90.

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.

Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of two, arXiv:1710.10884 [math.NT], 2017.

Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 12.

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.

Stephen Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., Vol. 55 (1983), pp. 601-644.

Stephen Wolfram, Geometry of Binomial Coefficients, Amer. Math. Monthly, Vol. 91, No. 9 (November 1984), pp. 566-571.

Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv preprint arXiv:1610.06166 [math.CO], 2016.

Zhujun Zhang, A Note on Counting Binomial Heaps, ResearchGate (2019).

Index entries for sequences related to cellular automata

Index entries for sequences that are fixed points of mappings

Index entries for sequences computed with run length transform

FORMULA

a(n) = 2^A000120(n).

a(0) = 1; for n > 0, write n = 2^i + j where 0 <= j < 2^i; then a(n) = 2*a(j).

a(n) = 2*a(n-1)/A006519(n) = A000079(n)*A049606(n)/A000142(n).

a(n) = A038573(n) + 1.

G.f.: Product_{k>=0} (1+2*z^(2^k)). - Ralf Stephan, Apr 06 2003

a(n) = Sum_{i=0..2*n} (binomial(2*n, i) mod 2)*(-1)^i. - Benoit Cloitre, Nov 16 2003

a(n) mod 3 = A001285(n). - Benoit Cloitre, May 09 2004

a(n) = 2^n - 2*Sum_{k=0..n} floor(binomial(n, k)/2). - Paul Barry, Dec 24 2004

a(n) = Product_{k=0..log_2(n)} 2^b(n, k), b(n, k) = coefficient of 2^k in binary expansion of n. - Paul D. Hanna

Sum_{k=0..n-1} a(k) = A006046(n).

a(n) = n/2 + 1/2 + (1/2)*Sum_{k=0..n} (-(-1)^binomial(n,k)). - Stephen Crowley, Mar 21 2007

G.f. for a(n)/A156769(n): (1/2)*z^(1/2)*sinh(2*z^(1/2)). - Johannes W. Meijer, Feb 20 2009

Equals infinite convolution product of [1,2,0,0,0,0,0,0,0] aerated (A000079 - 1) times, i.e., [1,2,0,0,0,0,0,0,0] * [1,0,2,0,0,0,0,0,0] * [1,0,0,0,2,0,0,0,0]. - Mats Granvik, Gary W. Adamson, Oct 02 2009

a(n) = f(n, 1) with f(x, y) = if x = 0 then y otherwise f(floor(x/2), y*(1 + x mod 2)). - Reinhard Zumkeller, Nov 21 2009

a(n) = 2^(number of 1's in binary form of (n-1)). - Gabriel C. Benamy, Dec 08 2009

a((2*n+1)*2^p-1) = (2^p)*a(n), p >= 0. - Johannes W. Meijer, Jun 05 2011

a(n) = A000120(A001317(n)). - Reinhard Zumkeller, Nov 24 2012

a(n) = A226078(n,1). - Reinhard Zumkeller, May 25 2013

a(n) = lcm(n!, 2^n) / n!. - Daniel Suteu, Apr 28 2017

a(n) = A061142(A005940(1+n)). - Antti Karttunen, May 29 2017

a(0) = 1, a(2*n) = a(n), a(2*n+1) = 2*a(n). - Daniele Parisse, Feb 15 2024

EXAMPLE

Has a natural structure as a triangle:

.1,

.2,

.2,4,

.2,4,4,8,

.2,4,4,8,4,8,8,16,

.2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,

.2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32,64,

....

The rows converge to A117973.

From Omar E. Pol, Jun 07 2009: (Start)

Also, triangle begins:

.1;

.2,2;

.4,2,4,4;

.8,2,4,4,8,4,8,8;

16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16;

32,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32;

64,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,...

(End)

G.f. = 1 + 2*x + 2*x^2 + 4*x^3 + 2*x^4 + 4*x^5 + 4*x^6 + 8*x^7 + 2*x^8 + ...

MAPLE

A001316 := proc(n) local k; add(binomial(n, k) mod 2, k=0..n); end;

S:=[1]; S:=[op(S), op(2*s)]; # repeat ad infinitum!

a := n -> 2^add(i, i=convert(n, base, 2)); # Peter Luschny, Mar 11 2009

MATHEMATICA

Table[ Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ], {n, 0, 100} ]

Nest[ Join[#, 2#] &, {1}, 7] (* Robert G. Wilson v, Jan 24 2006 and modified Jul 27 2014 *)

Map[Function[Apply[Plus, Flatten[ #1]]], CellularAutomaton[90, {{1}, 0}, 100]] (* Produces counts of ON cells. N. J. A. Sloane, Aug 10 2009 *)

ArrayPlot[CellularAutomaton[90, {{1}, 0}, 20]] (* Illustration of first 20 generations. - N. J. A. Sloane, Aug 14 2014 *)

Table[2^(RealDigits[n - 1, 2][[1]] // Total), {n, 1, 100}] (* Gabriel C. Benamy, Dec 08 2009 *)

CoefficientList[Series[Exp[2*x], {x, 0, 100}], x] // Numerator (* Jean-François Alcover, Oct 25 2013 *)

Count[#, _?OddQ]&/@Table[Binomial[n, k], {n, 0, 90}, {k, 0, n}] (* Harvey P. Dale, Sep 22 2015 *)

PROG

(PARI) {a(n) = if( n<0, 0, numerator(2^n / n!))};

(PARI) A001316(n)=1<<norml2(binary(n)) \\ M. F. Hasler, May 03 2009

(PARI) a(n)=2^hammingweight(n) \\ Charles R Greathouse IV, Jan 04 2013

(Haskell)

import Data.List (transpose)

a001316 = sum . a047999_row -- Reinhard Zumkeller, Nov 24 2012

a001316_list = 1 : zs where

zs = 2 : (concat $ transpose [zs, map (* 2) zs])

-- Reinhard Zumkeller, Aug 27 2014, Sep 16 2011

(Sage, Python)

from functools import cache

@cache

def A001316(n):

if n <= 1: return n+1

return A001316(n//2) << n%2

print([A001316(n) for n in range(88)]) # Peter Luschny, Nov 19 2012

(Python)

def A001316(n):

return 2**bin(n)[2:].count("1") # Indranil Ghosh, Feb 06 2017

(Scheme) (define (A001316 n) (let loop ((n n) (z 1)) (cond ((zero? n) z) ((even? n) (loop (/ n 2) z)) (else (loop (/ (- n 1) 2) (* z 2)))))) ;; Antti Karttunen, May 29 2017

CROSSREFS

Equals left border of triangle A166548. - Gary W. Adamson, Oct 16 2009

For generating functions Product_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.

For partial sums see A006046. For first differences see A151930.

This is the numerator of 2^n/n!, while A049606 gives the denominator.

Cf. A051638, A048967, A007318, A094959, A048896, A117973, A008977, A139541, A048883, A102376, A038573, A159913, A000079, A166548, A006047, A089898, A105321, A061142.

Cf. A047999, A261363, A261366.

If we subtract 1 from the terms we get a pair of essentially identical sequences, A038573 and A159913.

A163000 and A163577 count binomial coefficients with 2-adic valuation 1 and 2. A275012 gives a measure of complexity of these sequences. - Eric Rowland, Mar 15 2017

Cf. A286575 (run-length transform), A368655 (binomial transform), also A037445.

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Henry Bottomley, Mar 12 2001

Further comments from N. J. A. Sloane, May 30 2009

STATUS

approved

A038573

a(n) = 2^A000120(n) - 1.

+10
39

0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 7, 3, 7, 7, 15, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 3, 7, 7, 15, 7, 15, 15, 31, 7, 15, 15, 31, 15, 31, 31, 63, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 3, 7, 7, 15, 7, 15, 15, 31

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Essentially the same sequence as A001316, which has much more information, and also A159913. - N. J. A. Sloane, Jun 05 2009

Smallest number with same number of 1's in its binary expansion as n.

Fixed point of the morphism 0 -> 01, 1 -> 13, 3 -> 37, ... = k -> k, 2k+1, ... starting from a(0) = 0; 1 -> 01 -> 0113 -> 01131337 -> 011313371337377(15) -> ..., . - Robert G. Wilson v, Jan 24 2006

From Gary W. Adamson, Jun 04 2009: (Start)

As an infinite string, 2^n terms per row starting with "1": (1; 1,3; 1,3,3,7; 1,3,3,7,3,7,7,15; 1,3,3,7,3,7,7,15,3,7,7,15,7,15,15,31;...)

Row sums of that triangle = A027649: (1, 4, 14, 46, 454, ...); where the next row sum = current term of A027649 + next term in finite difference row of A027649, i.e., (1, 3, 10, 32, 100, 308, ...) = A053581. (End)

From Omar E. Pol, Jan 24 2016: (Start)

Partial sums give A267700.

a(n) is also the number of cells turned ON at n-th generation of the cellular automaton of A267700 in a 90-degree sector on the square grid.

a(n) is also the number of Y-toothpicks added at n-th generation of the structure of A267700 in a 120-degree sector on the triangular grid. (End)

Row sums of A090971. - Nikolaos Pantelidis, Nov 23 2022

LINKS

Seiichi Manyama, Table of n, a(n) for n = 0..8191 (terms 0..1023 from T. D. Noe)

David Applegate, The movie version

Michael Gilleland, Some Self-Similar Integer Sequences

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Index entries for sequences related to cellular automata

Index entries for sequences related to toothpick sequences

Index entries for sequences that are fixed points of mappings

FORMULA

a(2n) = a(n), a(2n+1) = 2*a(n)+1, a(0) = 0. a(n) = A001316(n)-1 = 2^A000120(n) - 1. - Daniele Parisse

a(n) = number of positive integers k < n such that n XOR k = n-k (cf. A115378). - Paul D. Hanna, Jan 21 2006

a(n) = f(n, 1) with f(x, y) = if x = 0 then y - 1 else f(floor(x/2), y*(1 + x mod 2)). - Reinhard Zumkeller, Nov 21 2009

a(n) = (n mod 2 + 1) * a(floor(n/2)) + n mod 2. - Reinhard Zumkeller, Oct 10 2012

a(n) = Sum_{i=1..n} C(n,i) mod 2. - Wesley Ivan Hurt, Nov 17 2017

G.f.: -1/(1 - x) + Product_{k>=0} (1 + 2*x^(2^k)). - Ilya Gutkovskiy, Aug 20 2019

G.f. A(x) = x + x^2*A(x) + (1 + 2*x)*(1 - x^2)*A(x^2). - Michael Somos, Jul 24 2023

EXAMPLE

9 = 1001 -> 0011 -> 3, so a(9)=3.

From Gary W. Adamson, Jun 04 2009: (Start)

Triangle read by rows:

1, 3;

1, 3, 3, 7;

1, 3, 3, 7, 3, 7, 7, 15;

1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31;

...

Row sums: (1, 4, 14, 46, ...) = A027649 = last row terms + new set of terms such that row 3 = (1, 3, 3, 7,) + (3, 7, 7, 15) = 14 + 32 = A027649(2) + A053581(3). (End)

The rows of this triangle converge to A159913. - N. J. A. Sloane, Jun 05 2009

G.f. = x + x^2 + 3*x^3 + x^4 + 3*x^5 + 3*x^6 + 7*x^7 + x^8 + 3*x^9 + 3*x^10 + 7*x^11 + ... - Michael Somos, Jul 24 2023

MAPLE

seq(2^convert(convert(n, base, 2), `+`)-1, n=0..100); # Robert Israel, Jan 24 2016

MATHEMATICA

Array[ 2^Count[ IntegerDigits[ #, 2 ], 1 ]-1&, 100 ]

Nest[ Flatten[ # /. a_Integer -> {a, 2a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 24 2006 *)

PROG

(PARI) {a(n) = 2^subst(Pol(binary(n)), x, 1) - 1};

(PARI) a(n) = 2^hammingweight(n)-1; \\ Michel Marcus, Jan 24 2016

(Haskell)

a038573 0 = 0

a038573 n = (m + 1) * (a038573 n') + m where (n', m) = divMod n 2

-- Reinhard Zumkeller, Oct 10 2012, Feb 07 2011

(Python 3.10+)

def A038573(n): return (1<<n.bit_count())-1 # Chai Wah Wu, Nov 15 2022

CROSSREFS

Cf. A007313, A115378, A073138.

This is Guy Steele's sequence GS(3, 6) (see A135416).

Cf. also A000079, A001316, A027649, A053581, A159913, A267700.

Write n in b-ary, sort digits into increasing order: this sequence (b=2), A038574 (b=3), A319652 (b=4), A319653 (b=5), A319654 (b=6), A319655 (b=7), A319656 (b=8), A319657 (b=9), A004185 (b=10).

Column k=0 of A340666.

KEYWORD

nonn,easy,nice

AUTHOR

Marc LeBrun

EXTENSIONS

More terms from Erich Friedman

New definition from N. J. A. Sloane, Mar 01 2008

STATUS

approved

page 1

Search completed in 0.008 seconds