|
Search: reingold
|
|
|
| A072403 |
|
Numerator of the Reingold-Tarjan sequence, denominator=A072404. |
|
+20 2
|
|
| 1, 2, 5, 4, 11, 10, 1, 8, 23, 22, 7, 20, 19, 2, 17, 16, 47, 46, 5, 44, 43, 14, 41, 40, 13, 38, 37, 4, 35, 34, 11, 32, 95, 94, 31, 92, 91, 10, 89, 88, 29, 86, 85, 28, 83, 82, 1, 80, 79, 26, 77, 76, 25, 74, 73, 8, 71, 70, 23, 68, 67, 22, 65, 64, 191, 190, 7
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
The the Reingold-Tarjan sequence is based on the following function defined on even positive integers and range of the rational numbers:
f(2*n) = if n is even then 2*f(n)/3 else (f(n+1)+f(n-1))/3 for n>1, f(2*1)=1.
f(2*n) = a(n)/A072404(n) for n>1, a(1)=1 and A072404(1)=1.
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences (Example 33), Theoretical Computer Science, 98 (1992), 163-197.
E. M. Reingold and R. E. Tarjan, On a greedy heuristic for complete matching, SIAM J. Computing 10 (1981), 676-681.
|
|
LINKS
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
|
|
CROSSREFS
|
Sequence in context: A114393 A100710 A069913 this_sequence A010078 A074639 A002314
Adjacent sequences: A072400 A072401 A072402 this_sequence A072404 A072405 A072406
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jun 16 2002
|
|
|
|
|
| A072404 |
|
Denominator of the Reingold-Tarjan sequence, numerator=A072403. |
|
+20 2
|
|
| 1, 3, 9, 9, 27, 27, 3, 27, 81, 81, 27, 81, 81, 9, 81, 81, 243, 243, 27, 243, 243, 81, 243, 243, 81, 243, 243, 27, 243, 243, 81, 243, 729, 729, 243, 729, 729, 81, 729, 729, 243, 729, 729, 243, 729, 729, 9, 729, 729, 243, 729, 729, 243, 729, 729, 81
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
The the Reingold-Tarjan sequence is based on the following function defined on even positive integers and range of the rational numbers:
f(2*n) = if n is even then 2*f(n)/3 else (f(n+1)+f(n-1))/3 for n>1, f(2*1)=1.
f(2*n) = A072403(n)/a(n) for n>1, A072403(1)=1 and a(1)=1.
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences (Example 33), Theoretical Computer Science, 98 (1992), 163-197.
E. M. Reingold and R. E. Tarjan, On a greedy heuristic for complete matching, SIAM J. Computing 10 (1981), 676-681.
|
|
LINKS
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
|
|
CROSSREFS
|
Sequence in context: A143225 A099720 A162349 this_sequence A125824 A038227 A080292
Adjacent sequences: A072401 A072402 A072403 this_sequence A072405 A072406 A072407
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jun 16 2002
|
|
|
|
|
| A005187 |
|
a(n)=a([n/2])+n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n. (Formerly M2330)
|
|
+10 60
|
|
| 0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31, 32, 34, 35, 38, 39, 41, 42, 46, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98, 101, 102, 104, 105, 109, 110, 112, 113, 116, 117, 119, 120, 127, 128
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Also the power of 2 in (2n)!.
Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Aug 27 2003
Also numbers having a partition into distinct Mersenne numbers >0; A079559(a(n))=1; complement of A055938. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Mar 18 2009]
|
|
REFERENCES
|
Laurent Alonso; Edward M. Reingold; Ren\`e Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
Laurent Alonso; Edward M. Reingold; Ren\`e Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
Michael E. Saks; Michael Werman, On computing majority by comparisons. Combinatorica 11 (1991), no. 4, 383-387.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..1000
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
|
|
FORMULA
|
For m>0, let q=[ log_2(m) ]; a(2m+1)=2^q+3m+sum([ (m-2^q)/2^k ], k=1..infinity); a(2m)=a(2m+1)-1 - Len Smiley (smiley(AT)math.uaa.alaska.edu)
a(n) = Sum{k >= 0}[ n/2^k ] = n+A011371(n). - Henry Bottomley (se16(AT)btinternet.com), Jul 03 2001
G.f.: A(x) = Sum(k=0, infinity, x^(2^k)/((1-x)*(1-x^(2^k)))). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Dec 24 2002
a(n) = Sum(k = 1 through n) A001511(k) - number of 1's in binary representation of n. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 15 2003
Conjecture : a(n)=2n+O(log(n)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Oct 07 2003
Sum_{n, 2^k<=n<2^(k+1)} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 19 2004
a(n)= A011371(n)+n, n>=0.
Recurrence: a(n)=n+a(floor(n/2)); a(2n)=2n+a(n); a(n*2^m)=2*n*(2^m-1)+a(n). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
a(2^m)=2^(m+1)-1, m>=0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
Asymptotic behavior: a(n)=2n+O(log(n)), a(n+1)-a(n)=O(log(n)); this follows from the inequalities below. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
a(n)<=2n-1; equality holds for powers of 2. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
a(n)>=2n-1-floor(log_2(n)); equality holds for n=2^m-1, m>0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
lim inf (2n-a(n))=1, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
lim sup (2n-log_2(n)-a(n))=0, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
lim sup (a(n+1)-a(n)-log_2(n))=1, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
a(n)=2n-A000120(n); - Paul Barry (pbarry(AT)wit.ie), Oct 26 2007
PURRS demo results: Bounds for a(n) = n+a(1/2*n) with initial conditions a(1) = 1: a(n) >= -2+2*n-log(n)*log(2)^(-1), a(n) <= 1+2*n for each n >= 1 - Alexander R. Povolotsky (pevnev(AT)juno.com), Apr 06 2008
If n = 2^a_1 + 2^a_2 + ... + 2^a_k, then a(n) = n-k. This can be used to prove that 2^n maximally divides (2n!)/n!. [From Jon Perry (johnandruth(AT)jrperry.orangehome.co.uk), Jul 16 2009]
|
|
MATHEMATICA
|
a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *)
Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (from Robert G. Wilson v (rgwv(at)rgwv.com), Apr 19 2006).
|
|
PROGRAM
|
(PARI) a(n)=if(n<0, 0, valuation((2*n)!, 2))
(PARI) a(n)=if(n<0, 0, sum(k=1, n, (2*n)\2^k))
(PARI) {a(n) = if( n < 0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) } /* Michael Somos Aug 28 2007 */
|
|
CROSSREFS
|
Cf. A001790, A011371, A001511(n) = a(n+1)-a(n), A046161(n)=2^a(n).
a(n)=A011371(2n+1)
Partial sums of A001511.
Cf. A067080, A098844, A132027, A004128, A054899.
Sequence in context: A075752 A046541 A047344 this_sequence A091934 A024515 A138971
Adjacent sequences: A005184 A005185 A005186 this_sequence A005188 A005189 A005190
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Allan Wilks (allan(AT)research.att.com)
|
|
EXTENSIONS
|
More terms from Jud McCranie (j.mccranie(AT)comcast.net), Jul 04 2000
|
|
|
|
|
| A011371 |
|
n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!. |
|
+10 46
|
|
| 0, 0, 1, 1, 3, 3, 4, 4, 7, 7, 8, 8, 10, 10, 11, 11, 15, 15, 16, 16, 18, 18, 19, 19, 22, 22, 23, 23, 25, 25, 26, 26, 31, 31, 32, 32, 34, 34, 35, 35, 38, 38, 39, 39, 41, 41, 42, 42, 46, 46, 47, 47, 49, 49, 50, 50, 53, 53, 54, 54, 56, 56, 57, 57, 63, 63, 64, 64, 66, 66, 67, 67, 70
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
a(n) = A007814(A000142(n)). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 09 2004
Entries of A005187 appearing twice. - Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 06 2004
This sequence shows why in binary 0 and 1 are the only two numbers n such that n equals the sum of its digits raised to the consecutive powers (equivalent to the base 10 sequence A032799). 1 raised to any consecutive power is still 1 and thus any the sum of digits raised to consecutive powers for any n > 1 falls short of equaling the value of n by the n-th number of this sequence. - Alonso Delarte (alonso.delarte(AT)gmail.com), Jul 27 2004
Also the number of trailing zeros in the base-2 representation of n!. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 18 2007
|
|
REFERENCES
|
Laurent Alonso, Edward M. Reingold and Ren\`e Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
Laurent Alonso, Edward M. Reingold and Ren\`e Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
K. Atanassov, On Some of Smarandache's Problems, section 7, on the 61-st problem, page 42, American Research Press, 1999, 16-21.
G. Bachman, Introduction to p-Adic Numbers and Valuation Theory, Academic Press, 1964; see Lemma 3.1.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 305.
Michael E. Saks and Michael Werman, On computing majority by comparisons. Combinatorica 11 (1991), no. 4, 383-387.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..1000
K. Atanassov, On Some of Smarandache's Problems
K. Matthews, Computing the prime-power factorization of n!
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
|
|
FORMULA
|
a(n) =a([n/2])+[n/2] =[n/2]+[n/4]+[n/8]+[n/16]+... - Henry Bottomley (se16(AT)btinternet.com), Apr 24 2001
G.f.: A(x) = 1/(1-x)*Sum(k=1, infinity, x^(2^k)/(1-x^(2^k))). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 11 2002
a(n) = n - A000120(n). - Lekraj Beedassy (blekraj(AT)yahoo.com), Sep 01 2003
a(n)=A005187(n)-n, n>=0.
a(n)=sum{2<=k<=n, sum{j|k,j>=2, floor(log_2(j))-floor(log_2(j-1))}}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 18 2007
The g.f. can be expressed in terms of a Lambert series, in that g(x)=L[b(k)](x)/(1-x) where L[b(k)](x)=sum{k>=0, b(k)*x^k/(1-x^k)} is a Lambert series with b(k)=1, if k is a power of 2, else b(k)=0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 25 2007
G.f.: g(x)=sum{k>0, c(k)*x^k}/(1-x), where c(k)=sum{j>1,j|k, floor(log_2(j))-floor(log_2(j-1))}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 25 2007
Recurrence: a(n)=floor(n/2)+a(floor(n/2)); a(2*n)=n+a(n); a(n*2^m)=n*(2^m-1)+a(n). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(2^m)=2^m-1, m>=0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
Asymptotic behavior: a(n)=n+O(log(n)), a(n+1)-a(n)=O(log(n)), which follows from the inequalities below. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(n)<=n-1; equality holds for powers of 2. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(n)>=n-1-floor(log_2(n)); equality holds for n=2^m-1, m>0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
lim inf (n-a(n))=1, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
lim sup (n-log_2(n)-a(n))=0, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
lim sup (a(n+1)-a(n)-log_2(n))=0, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
|
|
MAPLE
|
a(n) = RETURN(((2^(l))-1)+sum('(j*floor((n-(2^l)+2^j)/(2^(j+1))))', 'j'=1..l)); # after K. Atanassov. Here l is [ log2(n) ].
a := n -> n - add(i, i=convert(n, base, 2)) [From Peter Luschny (peter(AT)luschny.de), May 02 2009]
|
|
MATHEMATICA
|
-1+Length[ Last[ Split[ IntegerDigits[ 2(n!), 2 ] ] ] ], FoldList[ Plus, 0, Fold[ Flatten[ {#1, #2, #1} ]&, 0, Range[ 6 ] ] ]
Table[IntegerExponent[n!, 2], {n, 0, 127}]; Table[n-DigitCount[n, 2, 1], {n, 0, 127}]
Table[t = 0; p = 2; While[s = Floor[n/p]; t = t + s; s > 0, p *= 2]; t, {n, 0, 100} ]
|
|
PROGRAM
|
(PARI) a(n)=if(n<0, 0, valuation(n!, 2))
(PARI) a(n)=if(n<0, 0, sum(k=1, n, n\2^k))
(PARI) {a(n) = if( n < 0, 0, n - subst( Pol( binary( n ) ), x, 1) ) } /* Michael Somos Aug 28 2007 */
|
|
CROSSREFS
|
Cf. A000120, A005187, A054861.
a(n)=sum(A007814(k), k=1..n), n >= 1, a(0)=0.
Cf. A032799.
Cf. A067080, A098844, A132027.
Sequence in context: A025561 A145814 A007768 this_sequence A097355 A003860 A108216
Adjacent sequences: A011368 A011369 A011370 this_sequence A011372 A011373 A011374
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Oct 02 2001
|
|
|
|
|
| A000788 |
|
Total number of 1's in binary expansions of 0, ..., n. (Formerly M0964 N0360)
|
|
+10 23
|
|
| 0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
J.-P. Allouche & J. Shallit, Automatic sequences, Cambrige University Press, 2003, p. 94
E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.
Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
B. Lindstrom, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..1000
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle (arXiv:0802.2654)
P. J. Grabner, H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary
Index entries for sequences related to binary expansion of n
|
|
FORMULA
|
a(n)=sum(k=1, n, A000120(k)). - Benoit Cloitre, Dec 19, 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Sep 13 2003
a(n)=(1/2)*log2(n)*n + O(n); a(2^n)=n*2^(n-1)+1 - Benoit Cloitre (benoit7848c(AT)orange.fr), Sep 25 2003
a(n)=(1/2)*n*log(n)/log(2)+n*F(log(n)/log(2)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit) - Benoit Cloitre (benoit7848c(AT)orange.fr), Jun 08 2004
G.f.: 1/(1-x)^2 * Sum(k>=0, x^2^k/(1+x^2^k)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 19 2003
|
|
CROSSREFS
|
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Cf. A005183.
Sequence in context: A140206 A007818 A158618 this_sequence A053039 A027861 A062428
Adjacent sequences: A000785 A000786 A000787 this_sequence A000789 A000790 A000791
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001
|
|
|
|
| |
|
| 0, 0, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 17, 18, 18, 19, 20, 21, 21, 22, 23, 24, 24, 25, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 38, 39, 39, 40, 41, 42, 42, 43, 44, 45, 45, 46, 47, 48, 48, 49, 50, 51, 51, 52, 53, 54
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
The cyclic pattern (and numerator of the gf) is computed using Euclid's algorithm for GCD.
|
|
REFERENCES
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations, Cambridge University Press, 1997.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, NY, 1994.
|
|
LINKS
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations Web Site
Index entries for sequences related to Beatty sequences
|
|
FORMULA
|
G.f.: (1+x+x^2)*x^2/((1-x)*(1-x^4)) - Bruce Corrigan (scentman(AT)myfamily.com), Jul 03 2002
For all m>=0 a(4m)=0 mod 3; a(4m+1)=0 mod 3; a(4m+2)= 1 mod 3; a(4m+3) = 2 mod 3
a(n)=-1+Sum{k=0..n}{(1/8)*((k mod 4)+((k+1) mod 4)-((k+2) mod 4)+3*((k+3) mod 4)} [From Paolo P. Lava (ppl(AT)spl.at), Nov 17 2008]
|
|
CROSSREFS
|
Floors of other ratios: A004526, A002264, A002265, A004523, A057353, A057354, A057355, A057356, A057357, A057358, A057359, A057360, A057361, A057362, A057363, A057364, A057365, A057366, A057367.
Sequence in context: A086525 A120503 A083544 this_sequence A076539 A074184 A093700
Adjacent sequences: A057350 A057351 A057352 this_sequence A057354 A057355 A057356
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu)
|
|
|
|
|
| A000170 |
|
Number of ways of placing n nonattacking queens on n X n board. (Formerly M1958 N0775)
|
|
+10 17
|
|
| 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644, 24233937684440, 227514171973736, 2207893435808352, 22317699616364044
(list; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
J. R. Bitner and E. M. Reingold, Backtrack programming techniques, Commun. ACM, 18 (1975), 651-656.
J. Freeman, A neural network solution to the n-queens problem, The Mathematica J., 3 (No. 3, 1993), 52-56.
M. Gardner, The Unexpected Hanging, pp. 190-2, Simon & Shuster NY 1969
Jieh Hsiang, Yuh-Pyng Shieh and Yao-Chiang Chen, The cyclic complete mappings counting problems, in Problems and Problem Sets for ATP, volume 02-10 of DIKU technical reports, G. Sutcliffe, J. Pelletier and C. Suttner, eds., 2002.
Kenji Kise, Takahiro Katagiri, Hiroki Honda and Toshitsugu Yuba: Solving the 24-queens Problem using MPI on a PC Cluster, Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communications (2004)
I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), 629-639.
M. A. Sainte-Lagu\"{e}, Les R\'{e}seaux (ou Graphes), M\'{e}morial des Sciences Math\'{e}matiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 47.
R. J. Walker, An enumerative technique for a class of combinatorial problems, pp. 91-94 of Proc. Sympos. Applied Math., vol. 10, Amer. Math. Soc., 1960.
M. B. Wells, Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 238.
|
|
LINKS
|
Amazing Mathematical Object Factory, Information on the n Queens problem [Link corrected by Gerry Myerson, Apr 08 2009]
Anonymous, N Queens Problem
D. Bill, Durango Bill's The N-Queens Problem [Broken link?]
Patrick GUILLEMIN, N-Queens Challenge [Broken link?]
Patrick GUILLEMIN, N-Queens Challenge [Broken link?]
Patrick GUILLEMIN, N-Queens Challenge [Broken link?]
Kenji KISE, 24-queens.
W. Kosters, n-Queens (Extensive Bibliography)
NQuens@home, Home Page
Objectweb ProActive INRIA Team, Home Page
Objectweb ProActive INRIA Team, Solve the N Queens challenge with ProActive !
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Queens(AT)TUD project website. [From Thomas B. Preusser (thomas.preusser(AT)tu-dresden.de), Jul 11 2009]
|
|
FORMULA
|
Strong conjecture : there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n; weak conjecture : lim n -> infinity (1/n) * ln(n!/a(n)) = constant =0.90.... - Benoit Cloitre (benoit7848c(AT)orange.fr), Nov 10 2002
|
|
EXAMPLE
|
a(2) = a(3) = 0, since on 2 X 2 and 3 X 3 chessboards there are no solutions.
|
|
CROSSREFS
|
See A140393 for another version. Cf. A002562, A065256.
Sequence in context: A029673 A054790 A140393 this_sequence A038216 A145911 A027626
Adjacent sequences: A000167 A000168 A000169 this_sequence A000171 A000172 A000173
|
|
KEYWORD
|
nonn,hard,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
Terms for n=21-23 computed by Sylvain PION (Sylvain.Pion(AT)sophia.inria.fr) and Joel-Yann FOURRE (Joel-Yann.Fourre(AT)ens.fr).
a(24) from Kenji KISE (kis(AT)is.uec.ac.jp), Sep 01 2004
a(25) from Objectweb ProActive INRIA Team (proactive(AT)objectweb.org), Jun 11 2005 [Communicated by Alexandre Di Costanzo (Alexandre.Di_Costanzo(AT)sophia.inria.fr)]. This calculation took about 53 years of CPU time.
a(25) has been confirmed by the NTU 25Queen Project at National Taiwan University and Ming Chuan University, led by Yuh-Pyng (Arping) Shieh, Jul 26 2005. This computation took 26613 days CPU time.
Some of the links may be broken. I would appreciate receiving updates to them. - N. J. A. Sloane (njas(AT)research.att.com), May 01 2006
The NQueens-at-Home web site gives a different value for a(24), 226732487925864. Thanks to Goran Fagerstrom for pointing this out. I do not know which value is correct. I have therefore created a new entry, A140393, which gives the NQueens-at-home version of the sequence. - N. J. A. Sloane (njas(AT)research.att.com), Jun 18 2008
It now appears that this sequence (A000170) is correct and A140393 is wrong. - N. J. A. Sloane (njas(AT)research.att.com), Nov 08 2008
Added a(26) as calculated by Queens(AT)TUD [http://queens.inf.tu-dresden.de/]. Thomas B. Preusser (thomas.preusser(AT)tu-dresden.de), Jul 11 2009
|
|
|
|
| |
|
| 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 14, 14, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 20, 20, 20, 21, 21, 22, 22, 22, 23, 23, 24, 24, 24, 25, 25, 26, 26, 26, 27, 27, 28, 28, 28, 29, 29, 30, 30
(list; graph; listen)
|
|
|
OFFSET
|
0,6
|
|
|
COMMENT
|
The cyclic pattern (and numerator of the gf) is computed using Euclid's algorithm for GCD.
|
|
REFERENCES
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations, Cambridge University Press, 1997.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, NY, 1994.
|
|
LINKS
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations Web Site
|
|
FORMULA
|
G.f.: x^3(1 + x^3)/((1 - x)(1 - x^5)).
|
|
CROSSREFS
|
Floors of other ratios: A004526, A002264, A002265, A004523, A057353, A057354, A057355, A057356, A057357, A057358, A057359, A057360, A057361, A057362, A057363, A057364, A057365, A057366, A057367.
Sequence in context: A061375 A029920 A100719 this_sequence A097508 A109964 A025778
Adjacent sequences: A057351 A057352 A057353 this_sequence A057355 A057356 A057357
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu)
|
|
|
|
| |
|
| 0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, 16, 17, 18, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 28, 29, 30, 30, 31, 31, 32, 33, 33, 34, 34, 35, 36, 36, 37, 37, 38, 39, 39, 40, 40, 41, 42, 42, 43, 43
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
The cyclic pattern (and numerator of the gf) is computed using Euclid's algorithm for GCD.
|
|
REFERENCES
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations, Cambridge University Press, 1997.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, NY, 1994.
|
|
LINKS
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations Web Site
|
|
FORMULA
|
G.f.: (1+x^2+x^3)*x^2/((1-x)*(1-x^5)) - Bruce Corrigan (scentman(AT)myfamily.com), Jul 03 2002
for all m>=0 a(5m)=0 mod 3; a(5m+1)=0 mod 3; a(5m+2)= 1 mod 3; a(5m+3) = 1 mod 3; a(5m+4) = 2 mod 3
a(n)=-1+Sum{k=0..n}{(1/50)*(3*(k mod 5)-7*((k+1) mod 5)+13*((k+2) mod 5)-7*((k+3) mod 5)+13*((k+4) mod 5)} [From Paolo P. Lava (ppl(AT)spl.at), Nov 17 2008]
|
|
CROSSREFS
|
Floors of other ratios: A004526, A002264, A002265, A004523, A057353, A057354, A057355, A057356, A057357, A057358, A057359, A057360, A057361, A057362, A057363, A057364, A057365, A057366, A057367.
Sequence in context: A156261 A071823 A139338 this_sequence A160511 A055930 A079952
Adjacent sequences: A057352 A057353 A057354 this_sequence A057356 A057357 A057358
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu)
|
|
|
|
| |
|
| 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22
(list; graph; listen)
|
|
|
OFFSET
|
0,8
|
|
|
COMMENT
|
The cyclic pattern (and numerator of the gf) is computed using Euclid's algorithm for GCD.
|
|
REFERENCES
|
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, NY, 1994.
N. Dershowitz and E. M. Reingold, Calendrical Calculations, Cambridge University Press, 1997.
|
|
LINKS
|
N. Dershowitz and E. M. Reingold, Calendrical Calculations Web Site
|
|
FORMULA
|
G.f.: x^4(1 + x^4)/((1 - x)(1 - x^7)).
|
|
CROSSREFS
|
Floors of other ratios: A004526, A002264, A002265, A004523, A057353, A057354, A057355, A057356, A057357, A057358, A057359, A057360, A057361, A057362, A057363, A057364, A057365, A057366, A057367.
Sequence in context: A034973 A066927 A060065 this_sequence A020913 A025787 A057810
Adjacent sequences: A057353 A057354 A057355 this_sequence A057357 A057358 A057359
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu)
|
|
|
Search completed in 0.014 seconds
|