|
%I M2495 N0988 #279 Sep 17 2023 21:40:31
%S 1,3,5,15,17,51,85,255,257,771,1285,3855,4369,13107,21845,65535,65537,
%T 196611,327685,983055,1114129,3342387,5570645,16711935,16843009,
%U 50529027,84215045,252645135,286331153,858993459,1431655765,4294967295,4294967297,12884901891,21474836485,64424509455,73014444049,219043332147,365072220245,1095216660735,1103806595329,3311419785987
%N Sierpiński's triangle (Pascal's triangle mod 2) converted to decimal.
%C The members are all palindromic in binary, i.e., a subset of A006995. - _Ralf Stephan_, Sep 28 2004
%C 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 [This observation was also made in 1982 by N. L. White (see letter). - _N. J. A. Sloane_, Jun 15 2015]
%C 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
%C Limit_{n->oo} log(a(n))/n = log(2). - _Bret Mulvey_, May 17 2008
%C Equals row sums of triangle A166548; e.g., 17 = (2 + 4 + 6 + 4 + 1). - _Gary W. Adamson_, Oct 16 2009
%C Equals row sums of triangle A166555. - _Gary W. Adamson_, Oct 17 2009
%C For n >= 1, all terms are in A001969. - _Vladimir Shevelev_, Oct 25 2010
%C 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
%C 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 the number of 0's in the binary representation of n. - _Vladimir Shevelev_, Nov 29 2010
%C Trisection of this sequence gives rows of A008287 mod 2 converted to decimal. See also A177897, A177960. - _Vladimir Shevelev_, Jan 02 2011
%C 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
%C This sequence appears in Pascal's triangle mod 2 in another way, too. If we write it as
%C 1111111...
%C 10101010...
%C 11001100...
%C 10001000...
%C we get (taking the period part in each row):
%C .(1) (base 2) = 1
%C .(10) = 2/3
%C .(1100) = 12/15 = 4/5
%C .(1000) = 8/15
%C The k-th row, treated as a binary fraction, seems to be equal to 2^k / a(k). - _Katarzyna Matylla_, Mar 12 2011
%C From _Daniel Forgues_, Jun 16-18 2011: (Start)
%C 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.
%C It can be proved by induction that all terms of this sequence are products of distinct Fermat numbers (A000215):
%C a(0)=1 (empty product) are products of distinct Fermat numbers in { };
%C a(2^n+k) = a(k) * (2^(2^n)+1) = a(k) * F_n, n >= 0, 0 <= k <= 2^n - 1.
%C Thus for n >= 1, 0 <= k <= 2^n - 1, and
%C a(k) = Product_{i=0..n-1} F_i^(alpha_i), alpha_i in {0, 1},
%C this implies
%C a(2^n+k) = Product_{i=0..n-1} F_i^(alpha_i) * F_n, alpha_i in {0, 1}.
%C (Cf. OEIS Wiki links below.) (End)
%C The bits in the binary expansion of a(n) give the coefficients of the n-th power of polynomial (X+1) in ring GF(2)[X]. E.g., 3 ("11" in binary) stands for (X+1)^1, 5 ("101" in binary) stands for (X+1)^2 = (X^2 + 1), and so on. - _Antti Karttunen_, Feb 10 2016
%D Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, 2003, p. 113.
%D Henry Wadsworth Gould, Exponential Binomial Coefficient Series, Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sept. 1961.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Amiram Eldar, <a href="/A001317/b001317.txt">Table of n, a(n) for n = 0..3321</a> (terms 0..300 from T. D. Noe, terms 301..1023 from Tilman Piesk)
%H Gary W. Adamson, <a href="/A001317/a001317.pdf">Letter to N. J. A. Sloane, Apr 29 1994, and MS "Algorithm for the Chinese Remainder Theorem"</a>.
%H Gary W. Adamson and N. J. A. Sloane, <a href="/A001317/a001317_2.pdf">Correspondence, May 1994</a>, including Adamson's MSS "Algorithm for Generating nth Row of Pascal's Triangle, mod 2, from n", and "The Tower of Hanoi Wheel".
%H Cristian Cobeli and Alexandru Zaharescu, <a href="https://www.jstor.org/stable/43679285">Promenade around Pascal Triangle-Number Motives</a>, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104), No. 1 (2013), pp. 73-98; <a href="http://rms.unibuc.ro/bulletin/pdf/56-1/PromenadePascalPart1.pdf">alternative link</a>.
%H Richard K. Guy, <a href="http://www.jstor.org/stable/2691503">The Second Strong Law of Small Numbers</a>, Math. Mag, Vol. 63, No. 1 (1990), pp. 3-20. [<a href="/A005347/a005347.pdf">Annotated scanned copy</a>]
%H Richard K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.
%H Denton Hewgill, <a href="http://www.fq.math.ca/Scanned/15-2/hewgill.pdf">A relationship between Pascal's triangle and Fermat numbers</a>, Fib. Quart., Vol. 15, No. 2 (1977), pp. 183-184.
%H A. J. Macfarlane, <a href="http://www.damtp.cam.ac.uk/user/ajm/Papers2016/GFsForCAsOfEvenRuleNo.ps">Generating functions for integer sequences defined by the evolution of cellular automata with even rule numbers</a>, Fig. 4.
%H Dr. Math, <a href="http://www.mathforum.org/dr.math/faq/formulas/faq/regpoly.html">Regular polygon formulas</a>.
%H P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, <a href="https://arxiv.org/abs/2201.06636">On digital sequences associated with Pascal's triangle</a>, arXiv:2201.06636 [math.NT], 2022.
%H OEIS Wiki, <a href="/wiki/Constructible_odd-sided_polygons">Constructible odd-sided polygons</a> and <a href="/wiki/Sierpinski's_triangle">Sierpinski's triangle</a>.
%H Vladimir Shevelev, <a href="http://www.scientificadvances.co.in/artical/3/91">On Stephan's conjectures concerning Pascal triangle modulo 2</a>, J. Alg. Number Theory, Vol. 7, No. 1 (2012) pp. 11-29, <a href="http://arxiv.org/abs/1011.6083">preprint</a>, arXiv:1011.6083 [math.NT], 2010-2012.
%H John Frederick Sweeney, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.404.5350&rep=rep1&type=pdf">Clifford Clock and the Moolakaprithi Cube</a>, 2014. See p. 26. - _N. J. A. Sloane_, Mar 20 2014
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rule60.html">Rule 60</a> and <a href="http://mathworld.wolfram.com/Rule102.html">Rule 102</a>.
%H Neil L. White, <a href="/A001317/a001317_3.pdf">Letter to N. J. A. Sloane, Apr 15 1982</a>.
%H R. G. Wilson, V, <a href="/A007117/a007117.pdf">Letter to N. J. A. Sloane, Aug. 1993</a>.
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%H <a href="/index/Ge#GF2X">Index entries for sequences operating on polynomials in ring GF(2)[X]</a>
%F a(n+1) = a(n) XOR 2*a(n), where XOR is binary exclusive OR operator. - _Paul D. Hanna_, Apr 27 2003
%F a(n) = Product_{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
%F 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
%F a(32*n) = 3 ^ (32 * n * log(2) / log(3)) + 1. - _Bret Mulvey_, May 17 2008
%F For n >= 1, A000120(a(n)) = 2^A000120(n). - _Vladimir Shevelev_, Oct 25 2010
%F a(2^n) = A000215(n); a(2^n-1) = a(2^n)-2; for n >= 1, m >= 0,
%F 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
%F Sum_{k>=0} 1/a(k) = Product_{n>=0} (1 + 1/F_n), where F_n=A000215(n);
%F Sum_{k>=0} (-1)^(m(k))/a(k) = 1/2, where {m(n)} is Thue-Morse sequence (A010060).
%F If F_n is defined by F_n(z) = z^(2^n) + 1 and a(n) by (1/2)*Sum_{i>=0}(1-(-1)^{binomial(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
%F G.f.: Product_{k>=0} ( 1 + z^(2^k) + (2*z)^(2^k) ). - conjectured by _Shamil Shakirov_, proved by _Vladimir Shevelev_
%F a(n) = A000225(n+1) - A219843(n). - _Reinhard Zumkeller_, Nov 30 2012
%F From _Antti Karttunen_, Feb 10 2016: (Start)
%F a(0) = 1, and for n > 1, a(n) = A048720(3, a(n-1)) = A048724(a(n-1)).
%F a(n) = A048723(3,n).
%F a(n) = A193231(A000079(n)).
%F For all n >= 0: A268389(a(n)) = n.
%F (End)
%e Given a(5)=51, a(6)=85 since a(5) XOR 2*a(5) = 51 XOR 102 = 85.
%e From _Daniel Forgues_, Jun 18 2011: (Start)
%e a(0) = 1 (empty product);
%e a(1) = 3 = 1 * F_0 = a(2^0+0) = a(0) * F_0;
%e a(2) = 5 = 1 * F_1 = a(2^1+0) = a(0) * F_1;
%e a(3) = 15 = 3 * 5 = F_0 * F_1 = a(2^1+1) = a(1) * F_1;
%e a(4) = 17 = 1 * F_2 = a(2^2+0) = a(0) * F_2;
%e a(5) = 51 = 3 * 17 = F_0 * F_2 = a(2^2+1) = a(1) * F_2;
%e a(6) = 85 = 5 * 17 = F_1 * F_2 = a(2^2+2) = a(2) * F_2;
%e a(7) = 255 = 3 * 5 * 17 = F_0 * F_1 * F_2 = a(2^2+3) = a(3) * F_2;
%e ... (End)
%p A001317 := proc(n) local k; add((binomial(n,k) mod 2)*2^k, k=0..n); end;
%t f[n_] := Nest[ BitXor[#, BitShiftLeft[#, 1]] &, 1, n]; Array[f, 42, 0] (* Joel Madigan (dochoncho(AT)gmail.com), Dec 03 2007 *)
%t f[n_] := FromDigits[ Table[ Mod[ Binomial[n, k], 2], {k, 0, n}], 2]; Array[f, 42, 0] (* _Robert G. Wilson v_ *)
%t NestList[BitXor[#,2#]&,1,50] (* _Harvey P. Dale_, Aug 02 2021 *)
%o (PARI) a(n)=sum(i=0,n,(binomial(n,i)%2)*2^i)
%o (PARI) a=1; for(n=0, 66, print1(a,", "); a=bitxor(a,a<<1) ); \\ _Joerg Arndt_, Mar 27 2013
%o (PARI) A001317(n,a=1)={for(k=1,n,a=bitxor(a,a<<1));a} \\ _M. F. Hasler_, Jun 06 2016
%o (PARI) a(n) = subst(lift(Mod(1+'x,2)^n), 'x, 2); \\ _Gheorghe Coserea_, Nov 09 2017
%o (Haskell)
%o a001317 = foldr (\u v-> 2*v + u) 0 . map toInteger . a047999_row
%o -- _Reinhard Zumkeller_, Nov 24 2012
%o (Scheme, with memoization-macro definec, two variants)
%o (definec (A001317 n) (if (zero? n) 1 (A048724 (A001317 (- n 1)))))
%o (definec (A001317 n) (if (zero? n) 1 (A048720bi 3 (A001317 (- n 1))))) ;; Where A048720bi implements the dyadic function given in A048720.
%o ;; _Antti Karttunen_, Feb 10 2016
%o (Magma) [&+[(Binomial(n, i) mod 2)*2^i: i in [0..n]]: n in [0..41]]; // _Vincenzo Librandi_, Feb 12 2016
%o (Python)
%o from sympy import binomial
%o def a(n): return sum([(binomial(n, i)%2)*2**i for i in range(n + 1)]) # _Indranil Ghosh_, Apr 11 2017
%o (Python)
%o def A001317(n): return int(''.join(str(int(not(~n&k))) for k in range(n+1)),2) # _Chai Wah Wu_, Feb 04 2022
%Y Cf. A000079, A000215 (Fermat numbers), A047999, A048720, A054432, A173019, A177882, A177897, A177960, A193231, A230116, A247282, A249184, A268391.
%Y Cf. A038183 (odd bisection, 1D Cellular Automata Rule 90).
%Y Iterates of A048724 (starting from 1).
%Y Row 3 of A048723.
%Y Positions of records in A268389.
%Y Positions of ones in A268669 and A268384 (characteristic function).
%Y Not the same as A045544 nor as A053576.
%Y Cf. A045544.
%K nonn,base,easy,nice,hear
%O 0,2
%A _N. J. A. Sloane_
| 