Displaying 1-10 of 42 results found.
1, 3, 8, 20, 49, 119, 289, 705, 1731, 4283, 10690, 26934, 68531, 176115, 457110, 1198128, 3170607, 8468277, 22818167, 61999531, 169778889, 468292663, 1300270333, 3632269293, 10202425207, 28798822159, 81652955889, 232429744843, 663969970203, 1902716831527
MAPLE
with(numtheory):
b:= proc(n) option remember; ceil(add(
phi(d)*2^(n/d)/(2*n), d=divisors(n))+
`if`(n::odd, 2^((n-1)/2), 2^(n/2-1)+2^(n/2-2)))
end:
a:= n-> add(b(n-j)*binomial(n, j), j=0..n):
MATHEMATICA
a29[n_] := If[n == 0, 1, DivisorSum[n, EulerPhi[#]*2^(n/#)&]/(2*n) + If[OddQ[n], 2^((n-1)/2), 2^(n/2-1) + 2^(n/2-2)]]; a[n_] := Sum[Binomial[n, k] * a29[k], {k, 0, n}]; Array[a, 28, 0] (* Jean-François Alcover, Jul 17 2017 *)
Inverse Moebius transform of A000029 (starting at term 0).
+20
0
1, 3, 4, 7, 7, 14, 14, 25, 34, 55, 79, 144, 225, 396, 697, 1249, 2251, 4156, 7686, 14369, 27029, 51045, 96910, 184572, 352705, 675415, 1296892, 2494126, 4806079, 9273533, 17920861, 34670851, 67159132, 130218377, 252745388, 490988774
Moebius transform of A000029 (starting at term 0).
+20
0
1, 1, 2, 2, 5, 4, 12, 14, 27, 39, 77, 116, 223, 366, 679, 1206, 2249, 4077, 7684, 14262, 26997, 50885, 96908, 184270, 352692, 674963, 1296828, 2493344, 4806077, 9272049, 17920859, 34668378, 67158970, 130213873, 252745350, 490980258
Number of distinct bracelets of length n ( A000029) that eventually result in a cycle with length 2 or greater when used as the starting conditions for a rule 18 cellular automaton in a cyclic universe of circumference n.
+20
0
0, 0, 0, 1, 4, 3, 0, 11, 35, 62, 108, 182, 273, 195, 17, 1131, 3976, 7464, 13970, 26413, 50049, 95638, 182763, 350249, 671304
EXAMPLE
For n = 4, the six bracelets are 0000, 1000, 1100, 1010, 1110, 1111. a(4)=1 because only 1100 eventually enters a cycle that is not 0000 -> 0000.
EXTENSIONS
Definition clarified and corrected by Angelo Rosso, Nov 02 2023
Number of distinct bracelets of length n ( A000029) that eventually result in a cycle with length 2 or greater when used as the starting conditions for a rule 161 cellular automaton in a cyclic universe of circumference n.
+20
0
0, 1, 0, 3, 6, 5, 0, 21, 41, 72, 123, 196, 263, 141, 18, 1440, 4096, 7653, 14251, 26900, 50771, 96743, 184329, 352548, 674886
EXAMPLE
For n = 2, the three bracelets are 00, 10, 11. Their progressions are as follows:
00 -> 11 -> 11 -> 11 -> ...
10 -> 01 -> 10 -> 01 -> ...
11 -> 11 -> 11 -> 11 -> ...
a(2)=1 because only 01 eventually enters a cycle.
Number of n-bead necklaces with 2 colors when turning over is not allowed; also number of output sequences from a simple n-stage cycling shift register; also number of binary irreducible polynomials whose degree divides n.
(Formerly M0564 N0203)
+10
161
1, 2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192, 4116, 7712, 14602, 27596, 52488, 99880, 190746, 364724, 699252, 1342184, 2581428, 4971068, 9587580, 18512792, 35792568, 69273668, 134219796, 260301176, 505294128, 981706832
COMMENTS
Also a(n)-1 is the number of 1's in the truth table for the lexicographically least de Bruijn cycle (Fredricksen).
In music, a(n) is the number of distinct classes of scales and chords in an n-note equal-tempered tuning system. - Paul Cantrell, Dec 28 2011 Also, minimum cardinality of an unavoidable set of length-n binary words (Champarnaud, Hansel, Perrin). - Jeffrey Shallit, Jan 10 2019 a(n) is even for n != 0, 2. Proof: write n = 2^e * s with odd s, then a(n) * s = Sum_{d|s} Sum_{k=0..e} phi((2^e*s)/(2^k*d)) * 2^(2^k*d-e) = Sum_{d|s} Sum_{k=0..e-1} phi(s/d) * 2^(2^k*d-k-1) + Sum_{d|s} phi(s/d) * 2^(2^e*d-e) == Sum_{k=0..e-1} 2^(2^k*s-k-1) + 2^(2^e*s-e) == Sum_{k=0..min{e-1,1}} 2^(2^k*s-k-1) (mod 2). a(n) is odd if and only if s = 1 and e-1 = 0, or n = 2.
a(n) == 2 (mod 4) if and only if n = 1, 4 or n = 2*p^e with prime p == 3 (mod 4).
a(n) == 4 (mod 8) if and only if n = 2^e, 3*2^e for e >= 3, or n = p^e, 4*p^e != 12 with prime p == 3 (mod 4), or n = 2s where s is an odd number such that phi(s) == 4 (mod 8). (End)
REFERENCES
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, pp. 120, 172.
May, Robert M. "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019 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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).
LINKS
N. J. A. Sloane, On single-deletion-correcting codes, arXiv:math/0207197 [math.CO], 2002; in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002. David Thomson, Musical Polygons, Mathematics Today, Vol. 57, No. 2 (April 2021), pp. 50-51. Eric Weisstein's World of Mathematics, Necklace
FORMULA
a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n/d) = A053635(n)/n, where phi is A000010. Warning: easily confused with A001037, which has a similar formula. a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 2^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021 a(0) = 1; a(n) = (1/n)*Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021 Dirichlet g.f.: f(s+1) * (zeta(s)/zeta(s+1)), where f(s) = Sum_{n>=1} 2^n/n^s. - Jianing Song, Nov 13 2021
EXAMPLE
For n=3 and n=4 the necklaces are {000,001,011,111} and {0000,0001,0011,0101,0111,1111}.
The analogous shift register sequences are {000..., 001001..., 011011..., 111...} and {000..., 00010001..., 00110011..., 0101..., 01110111..., 111...}.
MAPLE
with(numtheory); A000031 := proc(n) local d, s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+phi(d)*2^(n/d); od; RETURN(s/n); fi; end; [ seq( A000031(n), n=0..50) ];
MATHEMATICA
a[n_] := Sum[If[Mod[n, d] == 0, EulerPhi[d] 2^(n/d), 0], {d, 1, n}]/n
a[n_] := Fold[#1 + 2^(n/#2) EulerPhi[#2] &, 0, Divisors[n]]/n (* Ben Branman, Jan 08 2011 *) Table[Expand[CycleIndex[CyclicGroup[n], t] /. Table[t[i]-> 2, {i, 1, n}]], {n, 0, 30}] (* Geoffrey Critzer, Mar 06 2011*) a[0] = 1; a[n_] := DivisorSum[n, EulerPhi[#]*2^(n/#)&]/n; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 03 2016 *) mx=40; CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-2*x^i]/i, {i, 1, mx}], {x, 0, mx}], x] (* Herbert Kociemba, Oct 29 2016 *)
PROG
(Haskell)
a000031 0 = 1
a000031 n = (`div` n) $ sum $
zipWith (*) (map a000010 divs) (map a000079 $ reverse divs)
where divs = a027750_row n
(Python)
from sympy import totient, divisors
def A000031(n): return sum(totient(d)*(1<<n//d) for d in divisors(n, generator=True))//n if n else 1 # Chai Wah Wu, Nov 16 2022
CROSSREFS
A008965(n) = a(n) - 1 allowing different offsets.
KEYWORD
nonn,easy,nice,core,changed
EXTENSIONS
There is an error in Fig. M3860 in the 1995 Encyclopedia of Integer Sequences: in the third line, the formula for A000031 = M0564 should be (1/n) sum phi(d) 2^(n/d).
Numbers of the form 2^n or 3*2^n.
+10
110
1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864, 2097152, 3145728, 4194304
COMMENTS
This entry is a list, and so has offset 1. WARNING: However, in this entry several comments, formulas and programs seem to refer to the original version of this sequence which had offset 0. - M. F. Hasler, Oct 06 2014 Number of necklaces with n-1 beads and two colors that are the same when turned over and hence have reflection symmetry. [edited by Herbert Kociemba, Nov 24 2016] The subset {a(1),...,a(2k)} contains all proper divisors of 3*2^k. - Ralf Stephan, Jun 02 2003 Let k = any nonnegative integer and j = 0 or 1. Then n+1 = 2k + 3j and a(n) = 2^k*3^j. - Andras Erszegi (erszegi.andras(AT)chello.hu), Jul 30 2005
a(n) = a(n-1) + a(n-2) - gcd(a(n-1), a(n-2)), n >= 3, a(1)=2, a(2)=3. - Ctibor O. Zizka, Jun 06 2009 Known in numerical mathematics as "Bulirsch sequence", used in various extrapolation methods for step size control. - Peter Luschny, Oct 30 2019 For n > 1, squares of the terms can be expressed as the sum of two powers of two: 2^x + 2^y. - Karl-Heinz Hofmann, Sep 08 2022
LINKS
Spencer Daugherty, Pamela E. Harris, Ian Klein, and Matt McClinton, Metered Parking Functions, arXiv:2406.12941 [math.CO], 2024. See pp. 11, 22. Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary Two-Up Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022. John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From N. J. A. Sloane, Nov 26 2012
FORMULA
For n > 2, a(n) = 2*a(n - 2); for n > 3, a(n) = a(n - 1)*a(n - 2)/a(n - 3). G.f.: (1 + x)^2/(1 - 2*x^2). - Henry Bottomley, Jul 15 2001, corrected May 04 2007 a(0)=1, a(1)=1 and a(n) = a(n-2) * ( floor(a(n-1)/a(n-2)) + 1 ). - Benoit Cloitre, Aug 13 2002 (3/4 + sqrt(1/2))*sqrt(2)^n + (3/4 - sqrt(1/2))*(-sqrt(2))^n. a(0)=1, a(2n) = a(n-1)*a(n), a(2n+1) = a(n) + 2^floor((n-1)/2). - Ralf Stephan, Apr 16 2003 [Seems to refer to the original version with offset=0. - M. F. Hasler, Oct 06 2014] E.g.f.: (cosh(x/sqrt(2)) + sqrt(2)sinh(x/sqrt(2)))^2.
a(n) = sqrt((17 - (-1)^n)*2^(n-4)) for n >= 2. - Anton Zakharov, Jul 24 2016 a(n) = 2^(n/2) if n is even. a(n) = 3 * 2^((n-3)/2) if n is odd and for n>1. - Karl-Heinz Hofmann, Sep 08 2022
MAPLE
1, seq(op([2^i, 3*2^(i-1)]), i=1..100); # Robert Israel, Sep 23 2014
MATHEMATICA
Function[w, DeleteCases[Union@ Flatten@ w, k_ /; k > Max@ First@ w]]@ TensorProduct[{1, 3}, 2^Range[0, 22]] (* Michael De Vlieger, Nov 24 2016 *) LinearRecurrence[{0, 2}, {1, 2, 3}, 50] (* Harvey P. Dale, Jul 04 2017 *)
PROG
(PARI) a(n)=if(n%2, 3/2, 2)<<((n-1)\2)\1
(Haskell)
a029744 n = a029744_list !! (n-1)
a029744_list = 1 : iterate
(\x -> if x `mod` 3 == 0 then 4 * x `div` 3 else 3 * x `div` 2) 2
(Scheme) (define ( A029744 n) (cond ((<= n 1) n) ((even? n) (expt 2 (/ n 2))) (else (* 3 (expt 2 (/ (- n 3) 2)))))) ;; Antti Karttunen, Sep 23 2014 (Python)
if n == 1: return 1
elif n % 2 == 0: return 2**(n//2)
CROSSREFS
First differences are in A016116(n-1). The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent. There may be minor differences from (s(n)) at the start, and a shift of indices. A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A060482 (s(n)-3); A136252 (s(n)-3); A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A354785 (3*s(n)), A061776 (3*s(n)-6); A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022
EXTENSIONS
Corrected and extended by Joe Keane (jgk(AT)jgk.org), Feb 20 2000
Triangle read by rows: T(n,k) = number of bracelets (reversible necklaces) with n beads, k of which are black and n - k are white.
+10
27
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 1, 4, 5, 8, 5, 4, 1, 1, 1, 1, 4, 7, 10, 10, 7, 4, 1, 1, 1, 1, 5, 8, 16, 16, 16, 8, 5, 1, 1, 1, 1, 5, 10, 20, 26, 26, 20, 10, 5, 1, 1, 1, 1, 6, 12, 29, 38, 50, 38, 29, 12, 6, 1, 1, 1, 1, 6, 14, 35, 57, 76, 76, 57, 35, 14, 6, 1, 1
COMMENTS
Equivalently, T(n,k) is the number of orbits of k-element subsets of the vertices of a regular n-gon under the usual action of the dihedral group D_n, or under the action of Euclidean plane isometries. Note that each row of the table is symmetric and unimodal. - Austin Shapiro, Apr 20 2009 Also, the number of k-chords in n-tone equal temperament, up to (musical) transposition and inversion. Example: there are 29 tetrachords, 38 pentachords, 50 hexachords in the familiar 12-tone equal temperament. Called "Forte set-classes," after Allen Forte who first cataloged them. - Jon Wild, May 21 2004
REFERENCES
Martin Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pages 245-246.
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
LINKS
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n, k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From N. J. A. Sloane, Nov 26 2012
FORMULA
T(0,0) = 1. If n > 0, T(n,k) = binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) / 2 + Sum_{d|n, d|k} (phi(d)*binomial(n/d, k/d)) / (2*n). - Washington Bomfim, Jun 30 2012 [edited by Petros Hadjicostas, May 29 2019] T(n,k) = T(n, n-k) for each k < n (Theorem 2 of H. Gupta). (End)
G.f. for column k >= 1: (x^k/2) * ((1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m) + (1 + x)/(1 - x^2)^floor((k/2) + 1)). (This formula is due to Herbert Kociemba.) - Petros Hadjicostas, May 25 2019 Bivariate o.g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = (1/2) * ((x + 1) * (x*y + 1) / (1 - x^2 * (y^2 + 1)) + 1 - Sum_{d >= 1} (phi(d)/d) * log(1 - x^d * (1 + y^d))). - Petros Hadjicostas, Jun 13 2019
EXAMPLE
Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
1;
1, 1;
1, 1, 1;
1, 1, 1, 1;
1, 1, 2, 1, 1;
1, 1, 2, 2, 1, 1;
1, 1, 3, 3, 3, 1, 1;
1, 1, 3, 4, 4, 3, 1, 1;
1, 1, 4, 5, 8, 5, 4, 1, 1;
1, 1, 4, 7, 10, 10, 7, 4, 1, 1;
1, 1, 5, 8, 16, 16, 16, 8, 5, 1, 1;
1, 1, 5, 10, 20, 26, 26, 20, 10, 5, 1, 1;
1, 1, 6, 12, 29, 38, 50, 38, 29, 12, 6, 1, 1;
...
MAPLE
local hk, a, d;
if k = 0 then
return 1 ;
end if;
hk := k mod 2 ;
a := 0 ;
for d in numtheory[divisors](igcd(k, n)) do
a := a+ numtheory[phi](d)*binomial(n/d-1, k/d-1) ;
end do:
%/k + binomial(floor((n-hk)/2), floor(k/2)) ;
%/2 ;
MATHEMATICA
Table[If[m*n===0, 1, 1/2*If[EvenQ[n], If[EvenQ[m], Binomial[n/2, m/2], Binomial[(n-2)/2, (m-1)/2 ]], If[EvenQ[m], Binomial[(n-1)/2, m/2], Binomial[(n-1)/2, (m-1)/2]]] + 1/2*Fold[ #1 +(EulerPhi[ #2]*Binomial[n/#2, m/#2])/n &, 0, Intersection[Divisors[n], Divisors[m]]]], {n, 0, 12}, {m, 0, n}] (* Wouter Meeussen, Aug 05 2002, Jan 19 2009 *)
PROG
(PARI)
B(n, k)={ if(n==0, return(1)); GCD = gcd(n, k); S = 0;
for(d = 1, GCD, if((k%d==0)&&(n%d==0), S+=eulerphi(d)*binomial(n/d, k/d)));
return (binomial(floor(n/2)- k%2*(1-n%2), floor(k/2))/2 + S/(2*n)); }
n=0; k=0; for(L=0, 8645, print(L, " ", B(n, k)); k++; if(k>n, k=0; n++))
(Python)
from sympy import binomial as C, totient, divisors, gcd
def T(n, k): return 1 if n==0 else C((n//2) - k%2 * (1 - n%2), (k//2))/2 + sum(totient(d)*C(n//d, k//d) for d in divisors(gcd(n, k)))/(2*n)
for n in range(11): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Apr 23 2017
CROSSREFS
Row sums: A000029. Columns 0-12: A000012, A000012, A008619, A001399, A005232, A032279, A005513, A032280, A005514, A032281, A005515, A032282, A005516.
Number of equivalence classes of binary sequences of period n.
(Formerly M0538 N0191)
+10
22
1, 2, 3, 4, 6, 6, 13, 10, 24, 22, 45, 30, 158, 74, 245, 368, 693, 522, 2637, 1610, 7386, 8868, 19401, 16770, 94484, 67562, 216275, 277534, 815558, 662370, 4500267, 2311470, 8466189, 13045108, 31593285, 40937606, 159772176, 103197490, 401913697
COMMENTS
From Pab Ter (pabrlos2(AT)yahoo.com), Jan 24 2006: (Start)
The number of equivalence classes of sequences of period p, taking values in a set with b elements, is given by:
N(p) = (1/(p*phi(p)))*Sum_{t=0..p-1} Sum_{k=1..p-1 & gcd(p,k)=1} b^C(k,t) where C(k,t), the number of disjoint cycles of the permutations considered, is C(k,t) = Sum_{u=0..p-1} 1/M(k,p/gcd(p,u(k-1)+t)).
If gcd(k,L)=1, M(k,L) denotes the least positive integer M such that 1+k+...+k^(M-1) == 0 (mod L). Also if gcd(k,L)=1 and Ek(L) denotes the exponent of k mod L: M(k,L)=L*Ek(L)/gcd(L,1+k+...+k^(Ek(L)-1)).
(End)
Number of two-colored necklaces of length n, where similar necklaces are counted only once. Two necklaces of length n, given by color functions c and d from {0, ..., n-1} to N (set of natural numbers) are considered similar iff there is a factor f, 0 < f < n, satisfying gcd(f,n) = 1, such that, for all k from {0, ..., n-1}, d(f * k mod n) = c(k). I.e., the bead at position k is moved to f * k mod n. In other words: the sequence counts the orbits of the action of the multiplicative group {f | 0 < f < n, gcd(f,n) = 1} on the set of two-colored necklaces where f maps c to d with the formula above. - Matthias EngelhardtCounts the same necklaces as A000029 but some of the necklaces viewed as distinct in A000029 are now viewed as equal. In particular, this implies that a(n) <= A000029(n) for every n.
REFERENCES
D. Z. Dokovic, I. Kotsireas, D. Recoskie, J. Sawada, Charm bracelets and their application to the construction of periodic Golay pairs, Discrete Applied Mathematics, Volume 188, 19 June 2015, Pages 32-40.
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).
MAPLE
with(numtheory): M:=proc(k, L) local e, s: s:=1: for e from 1 do if(s mod L = 0) then RETURN(e) else s:=s+k^e fi od: end; C:=proc(k, t, p) local u: RETURN(add(M(k, p/igcd(p, u*(k-1)+t))^(-1), u=0..p-1)) :end; N:=proc(p) options remember: local s, t, k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 do for k from 1 to p-1 do if igcd(p, k)=1 then s:=s+2^C(k, t, p) fi od od: RETURN(s/(p*phi(p))):end; seq(N(p), p=1..51); # first M expression
with(numtheory): E:=proc(k, L) if(L=1) then RETURN(1) else RETURN(order(k, L)) fi end; M:=proc(k, L) local s, EkL: EkL:=E(k, L): if(k>1) then s:=(k^EkL-1)/(k-1): RETURN(L*EkL/igcd(L, s)) else RETURN(L*EkL/igcd(L, EkL)) fi end; C:=proc(k, t, p) local u: RETURN(add(M(k, p/igcd(p, u*(k-1)+t))^(-1), u=0..p-1)) :end; N:=proc(p) options remember: local s, t, k: if(p=1) then RETURN(2) fi: s:=0: for t from 0 to p-1 do for k from 1 to p-1 do if igcd(p, k)=1 then s:=s+2^C(k, t, p) fi od od: RETURN(s/(p*phi(p))):end; seq(N(p), p=1..51); # second M expression (Pab Ter)
MATHEMATICA
max = 38; m[k_, n_] := (s = 1; Do[ If[ Mod[s, n] == 0, Return[e], s = s + k^e ] , {e, 1, max}]); c[k_, t_, n_] := Sum[ m[k, n/GCD[n, u*(k-1) + t]]^(-1), {u, 0, n-1}]; a[n_] := (s = 0; Do[ If[ GCD[n, k] == 1 , s = s + 2^c[k, t, n]] , {k, 1, n-1}, {t, 0, n-1}]; s/(n*EulerPhi[n])); a[0] = 1; a[1] = 2; Table[a[n], {n, 0, max}] (* Jean-François Alcover, Dec 06 2011, after Maple *)
EXTENSIONS
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 22 2005
Triangle T(n,k) read by rows, giving number of bracelets (turnover necklaces) with n beads of k colors (n >= 1, 1 <= k <= n).
+10
19
1, 1, 3, 1, 4, 10, 1, 6, 21, 55, 1, 8, 39, 136, 377, 1, 13, 92, 430, 1505, 4291, 1, 18, 198, 1300, 5895, 20646, 60028, 1, 30, 498, 4435, 25395, 107331, 365260, 1058058, 1, 46, 1219, 15084, 110085, 563786, 2250311, 7472984, 21552969, 1, 78, 3210, 53764, 493131, 3037314
COMMENTS
The formula given below is clear from the programs given in the Maple and Mathematica sections, while the g.f. for column k can be obtained using standard techniques.
If we differentiate the column k g.f. m times, then we can get a formula for row m. (For this sequence, we only need to use this row m formula for 1 <= k <= m, but it is valid even for k>m.) For example, to get the formula for row 8, we have T(n=8,k) = d^8/dx^8 (column k g.f.)/8! evaluated at x=0. Here, "d^8/dx^8" means "8th derivative w.r.t. x" of the column k g.f. Doing so, we get T(n=8, k) = (k^6 - k^5 + k^4 + 3*k^3 + 2*k^2 - 2*k + 4)*(k + 1)*k/16, which is the formula given for sequence A060560. (Here, we use this formula only for 1 <= k <= 8.) (End)
REFERENCES
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.
FORMULA
See Maple code.
T(n,k) = ((1+k)*k^{n/2}/2 + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is even, and = (k^{(n+1)/2} + (1/n)*Sum_{d|n} phi(n/d)*k^d)/2, if n is odd.
G.f. for column k: (1/2)*((k*x+k*(k+1)*x^2/2)/(1-k*x^2) - Sum_{n>=1} (phi(n)/n)*log(1-k*x^n)) provided we chop off the Taylor expansion starting at x^k (and ignore all the terms x^n with n<k).
(End)
EXAMPLE
1, 13, 92, 430, 1505, 4291; ( A027670) 1, 18, 198, 1300, 5895, 20646, 60028; ( A060532) 1, 30, 498, 4435, 25395, 107331, 365260, 1058058; ( A060560) ...
For example, when n=k=3, we have the following T(3,3)=10 bracelets of 3 beads using up to 3 colors: 000, 001, 002, 011, 012, 022, 111, 112, 122, and 222. (Note that 012 = 120 = 201 = 210 = 102 = 021.) Petros Hadjicostas, Nov 29 2017
MAPLE
local d, t1;
t1 := 0;
if n mod 2 = 0 then
for d from 1 to n do
if n mod d = 0 then
t1 := t1+numtheory[phi](d)*k^(n/d);
end if;
end do:
(t1+(n/2)*(1+k)*k^(n/2)) /(2*n) ;
else
for d from 1 to n do
if n mod d = 0 then
t1 := t1+numtheory[phi](d)*k^(n/d);
end if;
end do;
(t1+n*k^((n+1)/2)) /(2*n) ;
end if;
end proc:
seq(seq( A081720(n, k), k=1..n), n=1..10) ;
MATHEMATICA
t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n + 1)/2))/(2*n)]); Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 13 2012, after Maple, updated Nov 02 2017 *) Needs["Combinatorica`"]; Table[Table[NumberOfNecklaces[n, k, Dihedral], {k, 1, n}], {n, 1, 8}]//Grid (* Geoffrey Critzer, Oct 07 2012, after code by T. D. Noe in A027671 *)
CROSSREFS
Cf. A321791 (extension to n >= 0, k >= 0).
Search completed in 0.110 seconds
|