login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001317 Sierpinski's triangle (Pascal's triangle mod 2) converted to decimal.
(Formerly M2495 N0988)
65
1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295, 4294967297, 12884901891, 21474836485, 64424509455, 73014444049, 219043332147, 365072220245, 1095216660735, 1103806595329, 3311419785987 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

The members are all palindromic in binary, i.e., a subset of A006995. - Ralf Stephan, Sep 28 2004

a(2n+1) = 3 * a(2n), as follows from a(n)=product_{k in K} (1+2^(2^k)), where K is the set of integers such that n=sum_{k in K} 2^k. - Emmanuel Ferrand, Sep 28 2004

J. H. Conway writes (in Math Forum): at least the first 31 numbers give odd-sided constructible polygons. See also A047999. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005

Decimal number generated by the binary bits of the n-th generation of the Rule 60 elementary cellular automaton. Thus: 1; 0, 1, 1; 0, 0, 1, 0, 1; 0, 0, 0, 1, 1, 1, 1; 0, 0, 0, 0, 1, 0, 0, 0, 1; .. - Eric W. Weisstein, Apr 08 2006

One can generate this sequence using simple bitwise operations: a(n) = a(n-1) XOR (2a(n-1)), a(0)=1 where XOR is bitwise XOR. - Joel Madigan (dochoncho(AT)gmail.com), Dec 03 2007. Corrected by Dmitry Kamenetsky, Jun 08 2010

limit(n->inf) log(a(n)-1)/log(3) = n*log(2)/log(3). - Bret Mulvey, May 17 2008

Equals row sums of triangle A166548; e.g., 17 = (2 + 4 + 6 + 4 + 1). - Gary W. Adamson, Oct 16 2009

Equals row sums of triangle A166555. - Gary W. Adamson, Oct 17 2009

For n>=1, all terms are in A001969. - Vladimir Shevelev, Oct 25 2010

Let n,m>=0 be such that no carries occur when adding them. Then a(n+m)=a(n)*a(m). - Vladimir Shevelev, Nov 28 2010

Let phi_a(n) be the number of a(k)<=a(n) and respectively prime to a(n) (i.e., totient function over {a(n)}). Then, for n>=1, phi_a(n)= 2^(v(n)), where v(n) is number of 0's in the binary representation of n. - Vladimir Shevelev, Nov 29 2010

Trisection of this sequence gives rows of A008287 mod 2 converted to decimal. See also A177897, A177960. - Vladimir Shevelev, Jan 02 2011

Converting the rows of the powers of the k-nomial (k=2^e where e>=1) term-wise to binary and reading the concatenation as binary number gives every (k-1)st term of this sequence.  Similarly with powers p^k of any prime.  It might be interesting to study how this fails for powers of composites. - Joerg Arndt, Jan 07 2011

This sequence appears in Pascal's triangle mod 2 in another way, too. If we write it as

1111111...

10101010...

11001100...

10001000...

we get (taking the period part in each row):

.(1) (base 2) = 1

.(10) = 2/3

.(1100) = 12/15 = 4/5

.(1000) = 8/15

The k-th row, treated as binary fraction, seems to be equal to 2^k / a(k). - Katarzyna Matylla, Mar 12 2011

From Daniel Forgues, Jun 16-17-18 2011:  (Start)

Since there are 5 known Fermat primes, there are 32 products of distinct Fermat primes (thus there are 31 constructible odd-sided polygons, since a polygon has at least 3 sides.) a(0)=1 (empty product) and a(1) to a(31) are those 31 non-products of distinct Fermat primes.

It can be proved by induction that all terms of this sequence are products of distinct Fermat numbers (A000215):

a(0)=1 (empty product) are products of distinct Fermat numbers in { };

a(2^n+k) = a(k) * (2^(2^n)+1) = a(k) * F_n, n >= 0, 0 <= k <= 2^n - 1.

Thus for n >= 1, 0 <= k <= 2^n - 1, and

  a(k) = prod_(i=0..n-1) F_i^(alpha_i), alpha_i in {0, 1},

this implies

  a(2^n+k) = prod_(i=0..n-1) F_i^(alpha_i) * F_n, alpha_i in {0, 1}.

(Cf. OEIS Wiki links below.)  (End)

REFERENCES

J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p 113

C. Cobeli and A. Zaharescu, Promenade around Pascal Triangle-Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104) No. 1, 2013, 73-98; http://rms.unibuc.ro/bulletin/pdf/56-1/PromenadePascalPart1.pdf. - From N. J. A. Sloane, Feb 16 2013

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

R. K. Guy, The second strong law of small numbers. Math. Mag. 63 (1990), no. 1, 3-20.

D. Hewgill, A relationship between Pascal's triangle and Fermat numbers, Fib. Quart., 15 (1977), 183-184.

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

J. F. Sweeney, Clifford Clock and the Moolakaprithi Cube, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.404.5350&rep=rep1&type=pdf, 2014. See p. 26. - N. J. A. Sloane, Mar 20 2014

LINKS

T. D. Noe and Tilman Piesk, Table of n, a(n) for n = 0..1023 (first 300 terms by T. D. Noe)

Index entries for sequences related to cellular automata

Dr. Math, Regular polygon formulas

Eric Weisstein's World of Mathematics, Rule 60

Eric Weisstein's World of Mathematics, Rule 102

V. Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2

OEIS Wiki, Sierpinski's triangle

OEIS Wiki, Constructible odd-sided polygons

FORMULA

a(n+1) = a(n) XOR 2*a(n), where XOR is binary exclusive OR operator. - Paul D. Hanna, Apr 27 2003

a(n)=prod(e(j, n)=1, 2^(2^j)+1) where e(j, n) is the j-th least significant digit in the binary representation of n (Roberts: see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004

a(2*n+1) = 3*a(2*n). Proof: Since a(n)=product_{k in K} (1+2^(2^k)), where K is the set of integers such that n=sum_{k in K} 2^k, clearly K(2*n+1) = K(2*n) union {0}, hence a(2*n+1)=(1+2^(2^0))*a(2*n)=3*a(2*n). - Emmanuel Ferrand and Ralf Stephan, Sep 28 2004

a(32*n) = 3 ^ (32 * n * log(2) / log(3)) + 1. - Bret Mulvey, May 17 2008

For n>=1, A000120(a(n))=2^A000120(n). - Vladimir Shevelev, Oct 25 2010

a(2^n)=A000215(n); a(2^n-1)=a(2^n)-2; for n>=1,m>=0,

a(2^(n-1)-1)*a(2^n*m+2^(n-1))= 3*a(2^(n-1))*a(2^n*m+2^(n-1)-2). - Vladimir Shevelev, Nov 28 2010

Sum{k>=0} 1/a(k) = Prod{n>=0} (1+1/F_n), where F_n=A000215(n);

Sum{k>=0} (-1)^(m(k))/a(k) = 1/2, where {m(n)} is Thue-Morse sequence (A010060).

If F_n is defined by F_n(z)=z^(2^n)+1 and a(n) by (1/2)*Sum{i>=0}(1-(-1)^{binom(n,i)})*z^i, then, for z>1, the latter two identities hold as well with the replacement 1/2 in the right hand side of the 2nd one by 1-1/z. - Vladimir Shevelev, Nov 29 2010

G.f.: Product_{k>=0} ( 1 + z^(2^k) + (2*z)^(2^k) ). - conjectured by Shamil Shakirov, proved by Vladimir Shevelev

a(n) = A000225(n+1) - A219843(n). - Reinhard Zumkeller, Nov 30 2012

EXAMPLE

Given a(5)=51, a(6)=85 since a(5) XOR 2*a(5) = 51 XOR 102 = 85.

From Daniel Forgues, Jun 18 2011: (Start)

  a(0) = 1 (empty product);

  a(1) = 3 = 1 * F_0 = a(2^0+0) = a(0) * F_0;

  a(2) = 5 = 1 * F_1 = a(2^1+0) = a(0) * F_1;

  a(3) = 15 = 3 * 5 = F_0 * F_1 = a(2^1+1) = a(1) * F_1;

  a(4) = 17 = 1 * F_2 = a(2^2+0) = a(0) * F_2;

  a(5) = 51 = 3 * 17 = F_0 * F_2 = a(2^2+1) = a(1) * F_2;

  a(6) = 85 = 5 * 17 = F_1 * F_2 = a(2^2+2) = a(2) * F_2;

  a(7) = 255 = 3 * 5 * 17 = F_0 * F_1 * F_2 = a(2^2+3) = a(3) * F_2;

  ... (End)

MAPLE

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

MATHEMATICA

f[n_] := Nest[ BitXor[#, BitShiftLeft[#, 1]] &, 1, n]; Array[f, 42, 0] - Joel Madigan (dochoncho(AT)gmail.com), Dec 03 2007

f[n_] := FromDigits[ Table[ Mod[ Binomial[n, k], 2], {k, 0, n}], 2]; Array[f, 42, 0] (* Robert G. Wilson v *)

PROG

(PARI) a(n)=sum(i=0, n, (binomial(n, i)%2)*2^i)

(Haskell)

a001317 = foldr (\u v-> 2*v + u) 0 . map toInteger . a047999_row

-- Reinhard Zumkeller, Nov 24 2012

(PARI) a=1; for(n=0, 66, print1(a, ", "); a=bitxor(a, a<<1) ); /* Joerg Arndt, Mar 27 2013 */

CROSSREFS

Cf. A000215 (Fermat numbers).

Odd-numbered terms give A038183 (1D Cellular Automata Rule 90, "sigma minus")

Not the same as A053576 nor as A045544.

Cf. A047999, A054432, A177882, A177897, A177960, A227434, A230116.

Sequence in context: A003527 A004729 A045544 * A053576 A197818 A077406

Adjacent sequences:  A001314 A001315 A001316 * A001318 A001319 A001320

KEYWORD

nonn,base,easy,nice,hear

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 23 16:07 EDT 2014. Contains 248468 sequences.