Displaying 1-10 of 41 results found.
Algebraic degree of cos(Pi/n) for constructible n-gons ( A003401).
+20
3
1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 128, 128, 128, 128, 128, 128, 128, 128, 128, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 512, 512, 512, 512, 512, 512, 512, 512, 512
COMMENTS
a(n) is always a power of 2.
It would appear that a(n) <= a(n+1) and that for a(n)=2^k, the count for k beginning with 0 is 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ...; or that the count for k is k+2 for k > 0. - Robert G. Wilson v, Jul 31 2014 Apparently v_2(a(n)) = A052146(n-1) for n >= 2 where v_2 is the 2-adic valuation. - Joerg Arndt, Jul 29 2014 [incorrect for n >= 561, Joerg Arndt, Mar 03 2019]
MATHEMATICA
f[n_] := Exponent[MinimalPolynomial[Cos[Pi/n]][x], x]; Table[ f@ n, {n, Select[ Range@ 1300, IntegerQ[ Log[2, EulerPhi[#]]] &]}] (* Robert G. Wilson v, Jul 28 2014 *) A092506 = {2, 3, 5, 17, 257, 65537}; s = Sort[Times @@@ Subsets@ A092506]; mx = 2500; t = Union@ Flatten@ Table[(2^n)*s[[i]], {i, 64}, {n, 0, Log2[mx/s[[i]]]}]; f[n_] := EulerPhi[ 2n]/2; f[1] = 1; f@# & /@ t (* Robert G. Wilson v, Jul 28 2014 *)
1, 1, 2, 2, 4, 2, 4, 4, 4, 8, 8, 16, 8, 8, 8, 16, 16, 16, 16, 32, 16, 32, 32, 32, 64, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 128, 128, 256, 128, 128, 128, 128, 128, 128, 128, 256, 256, 256, 256, 256, 256, 512, 256, 256, 256, 512, 512, 512, 512, 1024, 512, 512, 512, 512
MATHEMATICA
Do[If[IntegerQ[Log[2, EulerPhi[n]]], Print[n]; ta[[u]]=n; u=u+1], {n, 1, 10000}] EulerPhi[ta]
PROG
(PARI) for(n=1, 1000, my(i=eulerphi(n)); if(omega(2*i)==1, print1(i, “, “))) \\ Jianing Song, Sep 28 2018
Algebraic degree of cos(2*Pi/n) for constructible n-gons ( A003401).
+20
1
1, 1, 1, 1, 2, 1, 2, 2, 2, 4, 4, 8, 4, 4, 4, 8, 8, 8, 8, 16, 8, 16, 16, 16, 32, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 64, 64, 128, 64, 64, 64, 64, 64, 64, 64, 128, 128, 128, 128, 128, 128, 256, 128, 128, 128, 256, 256, 256, 256, 512, 256, 256, 256, 256, 256, 256, 512
a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k-(k/p), where p is the largest prime factor of k.
+10
65
0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 2, 0, 1, 2, 3, 1, 3, 2, 3, 1, 2, 2, 3, 2, 3, 2, 3, 0, 3, 1, 3, 2, 3, 3, 3, 1, 2, 3, 4, 2, 3, 3, 4, 1, 4, 2, 2, 2, 3, 3, 3, 2, 4, 3, 4, 2, 3, 3, 4, 0, 3, 3, 4, 1, 4, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 1, 4, 2, 3, 3, 2, 4, 4, 2, 3, 3, 4, 3, 4, 4, 4, 1, 2, 4, 4, 2
COMMENTS
Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^ A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/ A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime). Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.
The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences. For any n, A333787(n) is either the nearest power of 2 reached (= 2^ A064415(n)), or occurs on some of the paths from n to there. (End)
LINKS
Michael De Vlieger, Annotated fan style binary tree labeling the index n, with a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value in a(n) for n = 1..16383.
FORMULA
a(1) = a(2) = 0; and for n > 2, a(p) = 1 + a(p-1) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [This is otherwise equal to the definition of A064097, except here we have a different initial condition, with a(2) = 0]. a(p) = 1+a(p-1), for all odd primes p.
If A209229(n) == 1 [when n is a power of 2], a(n) = 0, Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/ A078701(n))), or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
(End)
(End)
EXAMPLE
The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
Considering all possible paths from 15 to 1 nondeterministic map k -> k-(k/p), where p can be any prime factor of k, we obtain the following graph:
15
/ \
/ \
10 12
/ \ / \
/ \ / \
5 8 6
\__ | __/|
\_|_/ |
4 3
\ /
\ /
2
|
1.
It can be seen that there's also alternative route to 8 via 10 (with 10 = 15-(15/3), where 3 is not the largest prime factor of 15), but it's not any shorter than the route via 12.
(End)
MATHEMATICA
a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]
PROG
(PARI)
up_to = 2^24;
A329697list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2, up_to, v[n] = if(!bitand(n, n-1), 0, 1+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
v329697 = A329697list(up_to);
CROSSREFS
Cf. A000265, A003401, A005087, A052126, A053575, A054725, A064097, A064415, A078701, A087436, A147545, A171462, A209229, A333123, A333787, A333790, A334107, A334109, A335875, A334204, A335880, A335881, A336396, A336466, A336469 [= a(phi(n))], A336928 [= a(sigma(n))], A336470, A336477, A339970. Cf. A334099 (a right inverse, positions of the first occurrence of each n).
Prime numbers of the form 2^n + 1.
+10
47
COMMENTS
2 together with the Fermat primes A019434. Obviously if 2^n + 1 is a prime then either n = 0 or n is a power of 2. - N. J. A. Sloane, Apr 07 2004 Numbers m > 1 such that 2^(m-2) divides (m-1)! and m divides (m-1)! + 1. - Thomas Ordowski, Nov 25 2014 Also primes p such that sigma(p-1) = 2p - 3.
Also primes of the form 2^n + 3*(-1)^n - 2 for n >= 0 because for odd n, 2^n - 5 is divisible by 3.
Also primes of the form 2^n + 6*(-1)^n - 5 for n >= 0 because for odd n, 2^n - 11 is divisible by 3.
Also primes of the form 2^n + 15*(-1)^n - 14 for n >= 0 because for odd n, 2^n - 29 is divisible by 3. (End)
Exactly the set of primes p such that any number congruent to a primitive root (mod p) must have at least one prime divisor that is also congruent to a primitive root (mod p). See the links for a proof. - Rafay A. Ashary, Oct 13 2016 For n > 1, if 2^n + 1 divides 3^(2^(n-1)) + 1, then 2^n + 1 is a prime. - Jinyuan Wang, Oct 13 2018
PROG
(GAP) Filtered(List([1..20], n->2^n+1), IsPrime); # Muniru A Asiru, Oct 25 2018
CROSSREFS
A019434 is the main entry for these numbers.
XOR difference triangle of the powers of 2, read by rows; Square array A(row,col): A(0,col) = 2^col, A(row,col) = A048724(A(row-1, col)) for row > 0, read by descending antidiagonals.
+10
36
1, 2, 3, 4, 6, 5, 8, 12, 10, 15, 16, 24, 20, 30, 17, 32, 48, 40, 60, 34, 51, 64, 96, 80, 120, 68, 102, 85, 128, 192, 160, 240, 136, 204, 170, 255, 256, 384, 320, 480, 272, 408, 340, 510, 257, 512, 768, 640, 960, 544, 816, 680, 1020, 514, 771, 1024, 1536, 1280, 1920
COMMENTS
Define an "XOR difference triangle" for a sequence A by the following process. Start with A in the leftmost column. Generate the next column by performing the XOR operation between adjacent terms of the prior column. Repeat this process to generate the XOR difference triangle for A. Further, we define the "XOR BINOMIAL transform" of A as the main diagonal in the XOR difference triangle for A. The XOR BINOMIAL transform is its self-inverse. Let a sequence B be the XOR BINOMIAL transform of A, then we may express B by: B(n) = SumXOR_{k=0..n} A047999(n,k)*A(k), which is equivalent to: B(n) = (C(n,0)mod 2)*A(0) XOR (C(n,1)mod 2)*A(1) XOR (C(n,2)mod 2)*A(2) XOR ... XOR (X(n,n)mod 2)*A(n), where the coefficients are C(n,k)(mod 2) = A047999(n,k). This sequence is a rearrangement of the numbers which are 2^k times distinct Fermat numbers (numbers of the form 2^(2^m) + 1). This matches the sizes of polygons constructible with compass and straightedge ( A003401) up to 2^32+1, which is the first nonprime Fermat number. - Franklin T. Adams-Watters, Jun 16 2006
FORMULA
T(n, k) = 2^(n-k)* A001317(k). T(n, n) = A001317(n) = SumXOR_{k=0..n} A047999(n, k)*2^k, where SumXOR is the analog of summation under the binary XOR operation. When viewed as a square array A(row,col), with row >= 0, col >= 0, the following recurrences and formulas are valid:
A(0,col) = A000079(col), for row > 0, A(row,col) = A048724(A(row-1, col)). A(row,0) = A001317(row), for col > 0, A(row,col) = 2*A(row,col-1). (End)
EXAMPLE
The main diagonal equals A001317 (Pascal's triangle mod 2 in decimal): {1,3,5,15,17,51,85,255,257,771,1285,3855,...}, and defines the XOR BINOMIAL transform of the powers of 2.
Rows begin:
1;
2, 3;
4, 6, 5;
8, 12, 10, 15;
16, 24, 20, 30, 17;
32, 48, 40, 60, 34, 51;
64, 96, 80, 120, 68, 102, 85;
128, 192, 160, 240, 136, 204, 170, 255;
256, 384, 320, 480, 272, 408, 340, 510, 257;
512, 768, 640, 960, 544, 816, 680, 1020, 514, 771;
1024, 1536, 1280, 1920, 1088, 1632, 1360, 2040, 1028, 1542, 1285;
2048, 3072, 2560, 3840, 2176, 3264, 2720, 4080, 2056, 3084, 2570, 3855;
...
Viewed as a square array, the top left corner looks like this:
1, 2, 4, 8, 16, 32, 64, 128
3, 6, 12, 24, 48, 96, 192, 384
5, 10, 20, 40, 80, 160, 320, 640
15, 30, 60, 120, 240, 480, 960, 1920
17, 34, 68, 136, 272, 544, 1088, 2176
51, 102, 204, 408, 816, 1632, 3264, 6528
85, 170, 340, 680, 1360, 2720, 5440, 10880
255, 510, 1020, 2040, 4080, 8160, 16320, 32640
257, 514, 1028, 2056, 4112, 8224, 16448, 32896
771, 1542, 3084, 6168, 12336, 24672, 49344, 98688
1285, 2570, 5140, 10280, 20560, 41120, 82240, 164480
3855, 7710, 15420, 30840, 61680, 123360, 246720, 493440
4369, 8738, 17476, 34952, 69904, 139808, 279616, 559232
...
(End)
The square array shown above can be viewed as a subtable of a multiplication table with particular relevance to the carryless multiplication defined by A048720, as the first column gives the A048720 powers of 3 (and the first row gives powers of 2, which are the same as in standard arithmetic). - Peter Munn, Jan 13 2020
MATHEMATICA
a[n_]:= Sum[Mod[Binomial[n, i], 2]*2^i, {i, 0, n}]; T[n_, k_]:=2^(n - k)a[k]; Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten (* Indranil Ghosh, Apr 11 2017 *)
PROG
(PARI) {T(n, k)=local(B); B=0; for(i=0, k, B=bitxor(B, binomial(k, i)%2*2^(n-i))); B}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))
(Scheme)
;; Then use either this recurrence:
(define (A099884bi row col) (if (zero? row) ( A000079 col) ( A048724 (A099884bi (- row 1) col)))) ;; or this one:
(define (A099884bi row col) (if (zero? col) ( A001317 row) (* 2 (A099884bi row (- col 1))))) (Python)
from sympy import binomial
def a(n):
return sum((binomial(n, i)%2)*2**i for i in range(n + 1))
def T(n, k): return 2**(n - k)*a(k)
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Apr 11 2017
CROSSREFS
Cf. A000079 (first column of triangular table, the topmost row of square array). Cf. A001317 (the rightmost diagonal of triangular table, the leftmost column of square array).
EXTENSIONS
Square array interpretation added as a second, alternative description by Antti Karttunen, Sep 19 2016
1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 5, 1, 3, 3, 1, 1, 1, 3, 9, 1, 3, 5, 11, 1, 5, 3, 9, 3, 7, 1, 15, 1, 5, 1, 3, 3, 9, 9, 3, 1, 5, 3, 21, 5, 3, 11, 23, 1, 21, 5, 1, 3, 13, 9, 5, 3, 9, 7, 29, 1, 15, 15, 9, 1, 3, 5, 33, 1, 11, 3, 35, 3, 9, 9, 5, 9, 15, 3, 39, 1, 27, 5, 41, 3, 1, 21, 7, 5, 11, 3, 9, 11, 15, 23
COMMENTS
This is not necessarily the squarefree kernel. E.g., for n=19, phi(19)=18 is divisible by 9, an odd square. Values at which this kernel is 1 correspond to A003401 (polygons constructible with ruler and compass).
FORMULA
Let n" be the odd part of n, S be the odd squarefree kernel of n and p_i {i = 1..z} be all the prime factors of S. Then the sequence can be constructed by the following:
a(1) = 1;
a(n) = (n-1)" when n is prime; and
a(n) = Product_{i = 1..z} a(p_i)*n"/S when n is composite (see Examples).
(End)
(End)
EXAMPLE
n = 70 = 2*5*7, phi(70) = 24 = 8*3, so the odd kernel of phi(70) is a(70)=3. [corrected by Bob Selcoe, Aug 22 2017] a(89) = 88/8 = 11.
For n = 8820, 8820 = 2^2*3^2*5*7^2; S = 3*5*7 = 105, n" = 3^2*5*7^2 = 2205. a(3)*a(5)*a(7) = 1*1*3 = 3; a(8820) = 3*2205/105 = 63.
(End)
MAPLE
a:= n-> (t-> t/2^padic[ordp](t, 2))(numtheory[phi](n)):
MATHEMATICA
Array[NestWhile[Ceiling[#/2] &, EulerPhi@ #, EvenQ] &, 94] (* Michael De Vlieger, Aug 22 2017 *) (* or *) t=Array[EulerPhi, 94]; t/2^IntegerExponent[t, 2] (* Giovanni Resta, Aug 23 2017 *)
Smallest number whose Euler totient is divisible by 2^n.
+10
23
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, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776
COMMENTS
n = 32 is the first place where this differs from A001317, since 2^32 + 1 is not prime. - Mitch Harris, May 02 2007 a(8589934592) is the first unknown term; it is 2^8589934593 if F(33) = 2^(2^33)+1 is composite or F(33) otherwise. - Charles R Greathouse IV, Jul 15 2013 a(n) is the only odd element of the set phi-1(2^n), the totient inverses of 2^n. All other elements are 2*a(n), and the even elements of phi-1(2^(n-1)) * 2. - Torlach Rush, Sep 05 2017
EXAMPLE
1,2,4,8,...,131072 divide phi of 2,3,5,15,...,196611 = 3*65537 respectively.
MATHEMATICA
With[{s = Array[EulerPhi, 10^6]}, Table[FirstPosition[s, _?(Divisible[#, 2^n] &)][[1]], {n, 0, 19}]] (* Michael De Vlieger, Sep 05 2017 *)
PROG
(PARI) a(n)={
if(n >= 8589934592 && valuation(n>>5, 2)>27,
warning("Result is conjectural on the nonexistence of Fermat primes >= F(33).")
);
if(n>31,
return(2<<n)
);
n=binary(n);
prod(i=1, #n, (2^2^(i-1)+1)^n[#n+1-i])
Decimal expansion of 2*sin(Pi/5).
+10
21
1, 1, 7, 5, 5, 7, 0, 5, 0, 4, 5, 8, 4, 9, 4, 6, 2, 5, 8, 3, 3, 7, 4, 1, 1, 9, 0, 9, 2, 7, 8, 1, 4, 5, 5, 3, 7, 1, 9, 5, 3, 0, 4, 8, 7, 5, 2, 8, 6, 2, 9, 1, 9, 8, 2, 1, 4, 4, 5, 4, 4, 9, 6, 1, 5, 1, 4, 5, 5, 6, 9, 4, 8, 3, 2, 4, 7, 0, 3, 9, 1, 5, 0, 1, 7, 0, 0
COMMENTS
The golden ratio phi is the real part of 2*exp(i*Pi/5), while this constant c is the corresponding imaginary part. It is handy, for example, in simplifying metric expressions for Platonic solids (particularly for regular icosahedron and dodecahedron).
Edge length of a regular pentagon with unit circumradius. - Stanislav Sykora, May 07 2014 This is a constructible number (see A003401 for more details). Moreover, since phi is also constructible, (2^k)*exp(i*Pi/5), for any integer k, is a constructible complex number. - Stanislav Sykora, May 02 2016 rms(c, phi) := sqrt((c^2+phi^2)/2) = sqrt(2) = A002193.
LINKS
Eric Weisstein's World of Mathematics, Pentagon.
EXAMPLE
1.1755705045849462583374119...
MATHEMATICA
RealDigits[2*Sin[Pi/5], 10, 120][[1]] (* Harvey P. Dale, Sep 29 2012 *)
PROG
(Magma) SetDefaultRealField(RealField(100)); R:= RealField(); 2*Sin(Pi(R)/5); // G. C. Greubel, Nov 02 2018
Divisors of 2^32 - 1 (for a(1) to a(31), the 31 regular polygons with an odd number of sides constructible with ruler and compass).
+10
15
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
COMMENTS
The 32 divisors of the product of the 5 known Fermat primes.
The only known odd numbers whose totient is a power of 2. - Labos Elemer, Dec 06 2000 Omitting the first term a(0)=1 gives A045544 (the number of sides of constructible odd-sided regular polygons.)
REFERENCES
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, New York, 1996; see p. 140.
CROSSREFS
Cf. A000010, A000215, A001317, A003401, A003527, A004169, A004729, A019434, A045544, A047999, A053576, A054432.
KEYWORD
nonn,fini,full,easy,changed
Search completed in 0.026 seconds
|