| Displaying 1-8 of 8 results found.
page
1
Only k >= 0 such that, for every odd r > 0, A093179(n) divides the generalized Fermat number ( A007117(n)^r)^(2^k) + 1.
+20
0
3, 3, 5, 3, 7, 7, 9, 8, 11, 11, 13, 10, 15, 15, 17, 16, 19, 19, 21, 19, 23, 23, 25, 24, 27, 27, 29, 25, 31, 31, 33, 32, 35, 35, 37, 35, 39, 39, 41, 40, 43, 43, 45, 42, 47, 47, 49, 48, 51, 51, 53, 51, 55, 55, 57, 56, 59, 59, 61, 56, 63, 63, 65, 64, 67, 67, 69, 67, 71, 71, 73, 72, 75, 75, 77, 74, 79
EXAMPLE
A093179(5) = 641, A007117(5) = 5 and the only k >= 0 such that, for every odd r > 0, 641 divides the generalized Fermat number (5^r)^(2^k) + 1 is 5; so a(5) = 5.
MAPLE
a:=n->n-padic:-ordp(n+2, 2):
seq(a(n), n=3..79);
PROG
(PARI) a(n) = n - valuation(n+2, 2);
Sierpiński's triangle (Pascal's triangle mod 2) converted to decimal.
(Formerly M2495 N0988)
+10
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
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
a[n_] := Nest[ BitXor[#, BitShiftLeft[#, 1]] &, 1, n]; Array[a, 42, 0] (* Joel Madigan (dochoncho(AT)gmail.com), Dec 03 2007 *)
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
nonn, base, easy, nice, hear, changed
Numbers of edges of regular polygons constructible with ruler (or, more precisely, an unmarked straightedge) and compass.
(Formerly M0505)
+10
42
1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, 48, 51, 60, 64, 68, 80, 85, 96, 102, 120, 128, 136, 160, 170, 192, 204, 240, 255, 256, 257, 272, 320, 340, 384, 408, 480, 510, 512, 514, 544, 640, 680, 768, 771, 816, 960, 1020, 1024, 1028, 1088, 1280, 1285
COMMENTS
The terms 1 and 2 correspond to degenerate polygons.
The sequence can be also defined as follows: (i) 1 is a member. (ii) Double of any member is also a member. (iii) If a member is not divisible by a Fermat prime F_k then its product with F_k is also a member. In particular, the powers of 2 ( A000079) are a subset and so are the Fermat primes ( A019434), which are the only odd prime members. The definition is too restrictive (though correct): The Georg Mohr - Lorenzo Mascheroni theorem shows that constructibility using a straightedge and a compass is equivalent to using compass only. Moreover, Jean Victor Poncelet has shown that it is also equivalent to using straightedge and a fixed ('rusty') compass. With the work of Jakob Steiner, this became part of the Poncelet-Steiner theorem establishing the equivalence to using straightedge and a fixed circle (with a known center). A further extension by Francesco Severi replaced the availability of a circle with that of a fixed arc, no matter how small (but still with a known center).
Constructibility implies that when m is a member of this sequence, the edge length 2*sin(Pi/m) of an m-gon with circumradius 1 can be written as a finite expression involving only integer numbers, the four basic arithmetic operations, and the square root. (End)
If x,y are terms, and gcd(x,y) is a power of 2 then x*y is also a term. - David James Sycamore, Aug 24 2024
REFERENCES
Albert H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 183.
Allan Clark, Elements of Abstract Algebra, Chapter 4, Galois Theory, Dover Publications, NY 1984, page 124.
Duane W. DeTemple, "Carlyle circles and the Lemoine simplicity of polygon constructions." The American Mathematical Monthly 98.2 (1991): 97-108. - N. J. A. Sloane, Aug 05 2021 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
B. L. van der Waerden, Modern Algebra. Unger, NY, 2nd ed., Vols. 1-2, 1953, Vol. 1, p. 187.
LINKS
C. F. Gauss, Disquisitiones Arithmeticae, 1801. English translation: Yale University Press, New Haven, CT, 1966, p. 463. Original (in Latin).
FORMULA
Terms from 3 onward are computable as numbers such that cototient-of-totient equals the totient-of-totient: Flatten[Position[Table[co[eu[n]]-eu[eu[n]], {n, 1, 10000}], 0]] eu[m]=EulerPhi[m], co[m]=m-eu[m]. - Labos Elemer, Oct 19 2001, clarified by Antti Karttunen, Nov 27 2017 If the well-known conjecture that there are only five prime Fermat numbers F_k=2^{2^k}+1, k=0,1,2,3,4 is true, then we have exactly: Sum_{n>=1} 1/a(n)= 2*Product_{k=0..4} (1+1/F_k) = 4869735552/1431655765 = 3.40147098978.... - Vladimir Shevelev and T. D. Noe, Dec 01 2010 log a(n) >> sqrt(n); if there are finitely many Fermat primes, then log a(n) ~ k log n for some k. - Charles R Greathouse IV, Oct 23 2015
EXAMPLE
34 is a term of this sequence because a circle can be divided into exactly 34 parts. 7 is not.
MATHEMATICA
Select[ Range[ 1300 ], IntegerQ[ Log[ 2, EulerPhi[ # ] ] ]& ] (* Olivier Gérard Feb 15 1999 *) (* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Take[ Union[ Flatten[ NestList[2# &, Times @@@ Table[ UnrankSubset[n, Join[{1}, Table[2^2^i + 1, {i, 0, 4}]]], {n, 63}], 11]]], 60] (* Robert G. Wilson v, Jun 11 2005 *) nn=10; logs=Log[2, {2, 3, 5, 17, 257, 65537}]; lim2=Floor[nn/logs[[1]]]; Sort[Reap[Do[z={i, j, k, l, m, n}.logs; If[z<=nn, Sow[2^z]], {i, 0, lim2}, {j, 0, 1}, {k, 0, 1}, {l, 0, 1}, {m, 0, 1}, {n, 0, 1}]][[2, 1]]]
A092506 = {2, 3, 5, 17, 257, 65537}; s = Sort[Times @@@ Subsets@ A092506]; mx = 1300; Union@ Flatten@ Table[(2^n)*s[[i]], {i, 64}, {n, 0, Log2[mx/s[[i]]]}] (* Robert G. Wilson v, Jul 28 2014 *)
PROG
(Haskell)
a003401 n = a003401_list !! (n-1)
a003401_list = map (+ 1) $ elemIndices 1 $ map a209229 a000010_list
(PARI) for(n=1, 10^4, my(t=eulerphi(n)); if(t/2^valuation(t, 2)==1, print1(n, ", "))); \\ Joerg Arndt, Jul 29 2014 (PARI) is(n)=n>>=valuation(n, 2); if(n<7, return(n>0)); my(k=logint(logint(n, 2), 2)); if(k>32, my(p=2^2^k+1); if(n%p, return(0)); n/=p; unknown=1; if(n%p==0, return(0)); p=0; if(is(n)==0, 0, "unknown [has large Fermat number in factorization]"), 4294967295%n==0) \\ Charles R Greathouse IV, Jan 09 2022 (PARI) is(n)=n>>=valuation(n, 2); 4294967295%n==0 \\ valid for n <= 2^2^33, conjecturally valid for all n; Charles R Greathouse IV, Jan 09 2022 (Python)
from sympy import totient
A003401_list = [n for n in range(1, 10**4) if format(totient(n), 'b').count('1') == 1]
CROSSREFS
Positions of zeros in A293516 (apart from two initial -1's), and in A336469, positions of ones in A295660 and in A336477 (characteristic function).
Numbers k such that 3*2^k + 1 is prime.
(Formerly M1318 N0506)
+10
23
1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912, 20909, 34350, 42294, 42665, 44685, 48150, 54792, 55182, 59973, 80190, 157169, 213321, 303093, 362765, 382449, 709968, 801978, 916773, 1832496, 2145353
COMMENTS
List is complete up to 3941000 according to the list of RB & WK.
So far there are only 4 primes: 2, 5, 41, 353. (End)
REFERENCES
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 614.
H. Riesel, "Prime numbers and computer methods for factorization", Progress in Mathematics, Vol. 57, Birkhauser, Boston, 1985, Chap. 4, see pp. 381-384.
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).
PROG
(PARI) A2253=[1]; A002253(n)=for(k=#A2253, n-1, my(m=A2253[k]); until(ispseudoprime(3<<m+++1), ); A2253=concat(A2253, m))+A2253[n] \\ M. F. Hasler, Mar 03 2023
EXTENSIONS
Corrected and extended according to the list of Ray Ballinger and Wilfrid Keller by Zak Seidov, Mar 08 2009 a(47) and a(48) from the Ballinger & Keller web page, Joerg Arndt, Apr 07 2013 Terms moved from Data to b-file (Links), and additional term appended to b-file, by Jeppe Stig Nielsen, Oct 30 2020
Numbers k such that 5*2^k + 1 is prime.
(Formerly M2635 N1046)
+10
15
1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313, 4687, 5947, 13165, 23473, 26607, 125413, 209787, 240937, 819739, 1282755, 1320487, 1777515
REFERENCES
H. Riesel, "Prime numbers and computer methods for factorization," Progress in Mathematics, Vol. 57, Birkhauser, Boston, 1985, Chap. 4, see pp. 381-384.
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).
EXTENSIONS
Corrected (removed incorrect term 40937) and added more terms (from http://web.archive.org/web/20161028080239/http://www.prothsearch.net/riesel.html ), Joerg Arndt, Apr 07 2013
Smallest prime factor of the n-th Fermat number F(n) = 2^(2^n) + 1.
+10
14
3, 5, 17, 257, 65537, 641, 274177, 59649589127497217, 1238926361552897, 2424833, 45592577, 319489, 114689, 2710954639361, 116928085873074369829035993834596371340386703423373313, 1214251009, 825753601, 31065037602817, 13631489, 70525124609
COMMENTS
a(14) might need to be corrected if F(14) turns out to have a smaller factor than 116928085873074369829035993834596371340386703423373313. F(20) is composite, but no explicit factor is known. - Jeppe Stig Nielsen, Feb 11 2010
EXAMPLE
F(0) = 2^(2^0) + 1 = 3, prime.
F(5) = 2^(2^5) + 1 = 4294967297 = 641*6700417.
So 3 as the 0th entry and 641 is the 5th term.
MATHEMATICA
Table[With[{k = 2^n}, FactorInteger[2^k + 1]][[1, 1]], {n, 0, 15, 1}] (* Vincenzo Librandi, Jul 23 2013 *)
PROG
(PARI) g(n)=for(x=9, n, y=Vec(ifactor(2^(2^x)+1)); print1(y[1]", ")) \\ Cino Hilliard, Jul 04 2007
CROSSREFS
Leading entries in triangle A050922.
Let b(n) = 2^n with n >= 2, and let c = k*b(n) + 1 for k >= 1; then a(n) is the smallest k such that c is prime and such that A007814(r(n)) = A007814(k) + n where r(n) is the remainder of 2^(b(n)/4) mod c, or 0 if no such k exists.
+10
1
0, 0, 1, 8, 1024, 5, 1071, 6443, 52743, 1184, 11131, 39, 7, 856079, 3363658, 9264, 3150, 1313151, 13, 33629, 555296667, 534689, 8388607, 5, 512212693, 193652, 286330, 282030, 7224372579, 1120049, 149041
PROG
(PARI) print1(0, ", "0", "); for(n=4, 32, b=2^n; k=1; t=0; while(t<1, c=k*b+1; if(isprime(c), r=Mod(2, c)^(b/4); if(lift(r/b)<=k, if(valuation(lift(r), 2)==valuation(k, 2)+n, t=1; print1(k, ", ")))); k++));
Least odd k such that k*2^n + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m, or 0 if no such value exists.
+10
0
0, 1, 1, 0, 1, 0, 0, 5, 1, 116503103764643, 0, 604944512477, 11131, 39, 7
COMMENTS
The sequence continues: a(15) = ?, 1, 17753925353, a(18) = ?, 1575, 13, 579, a(22) = ?
Search completed in 0.012 seconds
|