|
| |
|
|
A001317
|
|
Sierpiński's triangle (Pascal's triangle mod 2) converted to decimal.
(Formerly M2495 N0988)
|
|
98
|
|
|
|
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
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]
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
Limit_{n->oo} log(a(n))/n = log(2). - Bret Mulvey, May 17 2008
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 the number of 0's in the binary representation of n. - Vladimir Shevelev, Nov 29 2010
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 a binary fraction, seems to be equal to 2^k / a(k). - Katarzyna Matylla, Mar 12 2011
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) = Product_{i=0..n-1} F_i^(alpha_i), alpha_i in {0, 1},
this implies
a(2^n+k) = Product_{i=0..n-1} F_i^(alpha_i) * F_n, alpha_i in {0, 1}.
(Cf. OEIS Wiki links below.) (End)
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
|
|
|
REFERENCES
|
Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, 2003, p. 113.
Henry Wadsworth Gould, Exponential Binomial Coefficient Series, Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sept. 1961.
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
|
Gary W. Adamson and N. J. A. Sloane, Correspondence, May 1994, including Adamson's MSS "Algorithm for Generating nth Row of Pascal's Triangle, mod 2, from n", and "The Tower of Hanoi Wheel".
|
|
|
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) = 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
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
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) = Product_{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)^{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
(End)
|
|
|
EXAMPLE
|
Given a(5)=51, a(6)=85 since a(5) XOR 2*a(5) = 51 XOR 102 = 85.
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)
(PARI) a=1; for(n=0, 66, print1(a, ", "); a=bitxor(a, a<<1) ); \\ Joerg Arndt, Mar 27 2013
(PARI) a(n) = subst(lift(Mod(1+'x, 2)^n), 'x, 2); \\ Gheorghe Coserea, Nov 09 2017
(Haskell)
a001317 = foldr (\u v-> 2*v + u) 0 . map toInteger . a047999_row
(Scheme, with memoization-macro definec, two variants)
(definec (A001317 n) (if (zero? n) 1 (A048720bi 3 (A001317 (- n 1))))) ;; Where A048720bi implements the dyadic function given in A048720.
(Magma) [&+[(Binomial(n, i) mod 2)*2^i: i in [0..n]]: n in [0..41]]; // Vincenzo Librandi, Feb 12 2016
(Python)
from sympy import binomial
def a(n): return sum([(binomial(n, i)%2)*2**i for i in range(n + 1)]) # Indranil Ghosh, Apr 11 2017
(Python)
def A001317(n): return int(''.join(str(int(not(~n&k))) for k in range(n+1)), 2) # Chai Wah Wu, Feb 04 2022
|
|
|
CROSSREFS
|
Cf. A000079, A000215 (Fermat numbers), A047999, A048720, A054432, A173019, A177882, A177897, A177960, A193231, A230116, A247282, A249184, A268391.
Cf. A038183 (odd bisection, 1D Cellular Automata Rule 90).
Iterates of A048724 (starting from 1).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
