cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A000170 Number of ways of placing n nonattacking queens on an n X n board.

Original entry on oeis.org

1, 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, 234907967154122528
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n > 3, a(n) is the number of maximum independent vertex sets in the n X n queen graph. - Eric W. Weisstein, Jun 20 2017
Number of nodes on level n of the backtrack tree for the n queens problem (a(n) = A319284(n, n)). - Peter Luschny, Sep 18 2018
Number of permutations of [1...n] such that |p(j)-p(i)| != j-i for iXiangyu Chen, Dec 24 2020
M. Simkin shows that the number of ways to place n mutually nonattacking queens on an n X n chessboard is ((1 +/- o(1))*n*exp(-c))^n, where c = 1.942 +/- 0.003. These are approximately (0.143*n)^n configurations. - Peter Luschny, Oct 07 2021

Examples

			a(2) = a(3) = 0, since on 2 X 2 and 3 X 3 chessboards there are no solutions.
.
a(4) = 2:
  +---------+ +---------+
  | . . Q . | | . Q . . |
  | Q . . . | | . . . Q |
  | . . . Q | | Q . . . |
  | . Q . . | | . . Q . |
  +---------+ +---------+
a(5) = 10:
  +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
  | . . . Q . | | . . Q . . | | . . . . Q | | . . . Q . | | . . . . Q |
  | . Q . . . | | . . . . Q | | . . Q . . | | Q . . . . | | . Q . . . |
  | . . . . Q | | . Q . . . | | Q . . . . | | . . Q . . | | . . . Q . |
  | . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | Q . . . . |
  | Q . . . . | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
  +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
  +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
  | Q . . . . | | . Q . . . | | Q . . . . | | . . Q . . | | . Q . . . |
  | . . . Q . | | . . . . Q | | . . Q . . | | Q . . . . | | . . . Q . |
  | . Q . . . | | . . Q . . | | . . . . Q | | . . . Q . | | Q . . . . |
  | . . . . Q | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
  | . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | . . . . Q |
  +-----------+ +-----------+ +-----------+ +-----------+ +-----------+
a(6) = 4:
  +-------------+ +-------------+ +-------------+ +-------------+
  | . . . . Q . | | . . . Q . . | | . . Q . . . | | . Q . . . . |
  | . . Q . . . | | Q . . . . . | | . . . . . Q | | . . . Q . . |
  | Q . . . . . | | . . . . Q . | | . Q . . . . | | . . . . . Q |
  | . . . . . Q | | . Q . . . . | | . . . . Q . | | Q . . . . . |
  | . . . Q . . | | . . . . . Q | | Q . . . . . | | . . Q . . . |
  | . Q . . . . | | . . Q . . . | | . . . Q . . | | . . . . Q . |
  +-------------+ +-------------+ +-------------+ +-------------+
- _Hugo Pfoertner_, Mar 17 2019

References

  • 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.
  • D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.
  • M. Kraitchik, The Problem of The Queens, Mathematical Recreations, 2nd ed., New York, Dover, 1953, pp. 247-256.
  • Massimo Nocentini, "An algebraic and combinatorial study of some infinite sequences of numbers supported by symbolic and logic computation", PhD Thesis, University of Florence, 2019. See Ex. 67.
  • W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed., New York, Dover, 1987, pp. 166-172 (The Eight Queens Problem).
  • M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 47.
  • 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. 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

Crossrefs

Cf. A002562, A065256.
Cf. A036464 (2Q), A047659 (3Q), A061994 (4Q), A108792 (5Q), A176186 (6Q).
Cf. A099152, A006717, A051906, A319284 (backtrack trees).
Cf. A260318, A260319, A260320.
Main diagonal of A348129.

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) * log(n!/a(n)) = constant = 0.90.... - Benoit Cloitre, Nov 10 2002
Lim_{n->infinity} a(n)^(1/n)/n = exp(-A359441) = 0.1431301... [Simkin 2021]. - Vaclav Kotesovec, Jan 01 2023
a(n) = 8 * A260320(n) + 4 * A260319(n) + 2 * A260318(n) for n >= 2 (see Kraitchik reference). - Jason Bard, Aug 12 2025

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.
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, Jun 18 2008
It now appears that this sequence (A000170) is correct and A140393 is wrong. - N. J. A. Sloane, Nov 08 2008
Added a(26) as calculated by Queens(AT)TUD [http://queens.inf.tu-dresden.de/]. - Thomas B. Preußer, Jul 11 2009
Added a(27) as calculated by the Q27 Project [https://github.com/preusser/q27]. - Thomas B. Preußer, Sep 23 2016
a(0) = 1 prepended by Joerg Arndt, Sep 16 2018

A048647 Write n in base 4, then replace each digit '1' with '3' and vice versa and convert back to decimal.

Original entry on oeis.org

0, 3, 2, 1, 12, 15, 14, 13, 8, 11, 10, 9, 4, 7, 6, 5, 48, 51, 50, 49, 60, 63, 62, 61, 56, 59, 58, 57, 52, 55, 54, 53, 32, 35, 34, 33, 44, 47, 46, 45, 40, 43, 42, 41, 36, 39, 38, 37, 16, 19, 18, 17, 28, 31, 30, 29, 24, 27, 26, 25, 20, 23, 22, 21, 192, 195, 194, 193, 204, 207, 206
Offset: 0

Views

Author

John W. Layman, Jul 05 1999

Keywords

Comments

The graph of a(n) on [ 1..4^k ] resembles a plane fractal of fractal dimension 1.
Self-inverse considered as a permutation of the integers.
First 4^n terms of the sequence form a permutation s(n) of 0..4^n-1, n>=1; the number of inversions of s(n) is A115490(n). - Gheorghe Coserea, Apr 23 2018

Examples

			a(15)=5, since 15 = 33_4 -> 11_4 = 5.

Links

Crossrefs

Cf. A065256, A007090.
Column k=4 of A248813.

Programs

  • C
    uint32_t a(uint32_t n) { return n ^ ((n & 0x55555555) << 1); } // Falk Hüffner, Jan 22 2022
  • Haskell
    a048647 0 = 0
a048647 n = 4 * a048647 n' + if m == 0 then 0 else 4 - m
            where (n', m) = divMod n 4
-- Reinhard Zumkeller, Apr 08 2013
  • Maple
    f:= proc(n)
option remember;
local m, r;
m:= n mod 4;
r:= 4*procname((n-m)/4);
if m = 0 then r else r + 4-m fi;
end proc:
f(0):= 0:
seq(f(n),n=0..100); # Robert Israel, Nov 03 2014
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 0,
      a(iquo(n, 4, 'r'))*4+[0, 3, 2, 1][r+1])
    end:
seq(a(n), n=0..70);  # Alois P. Heinz, Jan 25 2022
  • Mathematica
    Table[FromDigits[If[#==0,0,4-#]&/@IntegerDigits[n,4],4],{n,0,70}] (* Harvey P. Dale, Jul 23 2012 *)
  • PARI
    a(n)=fromdigits(apply(d->if(d,4-d),digits(n,4)),4) \\ Charles R Greathouse IV, Jun 23 2017
  • Python
    from sympy.ntheory.factor_ import digits
def a(n):
    return int("".join(str(4 - d) if d!=0 else '0' for d in digits(n, 4)[1:]), 4)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 26 2017
  • Python
    def A048647(n): return n^((n&((1<<(m:=n.bit_length())+(m&1))-1)//3)<<1) # Chai Wah Wu, Jan 29 2023

Formula

a(n) = if n = 0 then 0 else 4*a(floor(n/4)) + if m = 0 then 0 else 4 - m, where m = n mod 4. - Reinhard Zumkeller, Apr 08 2013
G.f. g(x) satisfies: g(x) = 4*(1+x+x^2+x^3)*g(x^4) + (3*x+2*x^2+x^3)/(1-x^4). - Robert Israel, Nov 03 2014

A065257 Quintal Queens permutation of N: double (mod 5) each digit (0->0, 1->2, 2->4, 3->1, 4->3) of the base-5 representation of n-1, add one.

Original entry on oeis.org

1, 3, 5, 2, 4, 11, 13, 15, 12, 14, 21, 23, 25, 22, 24, 6, 8, 10, 7, 9, 16, 18, 20, 17, 19, 51, 53, 55, 52, 54, 61, 63, 65, 62, 64, 71, 73, 75, 72, 74, 56, 58, 60, 57, 59, 66, 68, 70, 67, 69, 101, 103, 105, 102, 104, 111, 113, 115, 112, 114, 121, 123, 125, 122, 124, 106
Offset: 1

Views

Author

Antti Karttunen, Oct 26 2001

Keywords

Comments

See comment at A065256.

Links

Crossrefs

Inverse permutation: A065258. A065257[n] = A004515[n-1]+1. Cf. also A065186, A065188.

Programs

  • Maple
    [seq(QuintalQueens1(j),j=1..125)]; QuintalQueens0 := n -> DoubleDigits(n,5); QuintalQueens1 := n -> 1+QuintalQueens0(n-1);
DoubleDigits := proc(n,b) local i; add((b^i)*((2*floor(n/(b^i))) mod b),i=0..floor(evalf(log[b](n+1)))+1); end;

A004515 Generalized nim sum n + n in base 5.

Original entry on oeis.org

0, 2, 4, 1, 3, 10, 12, 14, 11, 13, 20, 22, 24, 21, 23, 5, 7, 9, 6, 8, 15, 17, 19, 16, 18, 50, 52, 54, 51, 53, 60, 62, 64, 61, 63, 70, 72, 74, 71, 73, 55, 57, 59, 56, 58, 65, 67, 69, 66, 68, 100, 102, 104, 101, 103, 110
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

I.e., double (mod 5) each digit (0->0, 1->2, 2->4, 3->1, 4->3) of the base-5 representation of n.
First 5^n terms of the sequence form a permutation s(n) of 0..5^n-1, n >= 1; the number of inversions of s(n) is 3*(25^n-5^n)/20 (i.e., 3, 90, 2325, 58500, 1464375, ...). - Gheorghe Coserea, Apr 23 2018

Links

Crossrefs

Inverse permutation: A065256.
a(n) = A065257(n+1)-1 ("Quintal Queens" permutation).

Programs

  • Mathematica
    Array[FromDigits[IntegerDigits[#, 5] /. k_ :> Mod[2 k, 5], 5] &, 56, 0] (* Michael De Vlieger, Apr 27 2018 *)
  • PARI
    a(n) = my(v=[0,2,4,1,3],b=#v); fromdigits(apply(d->v[d+1], digits(n, b)), b);
vector(56, n, a(n-1)) \\ Gheorghe Coserea, Apr 23 2018

Formula

Generalized nim sum m + n in base q: write m and n in base q and add mod q with no carries, e.g., 5 + 8 in base 3 = "21" + "22" = "10" = 1.

A065258 Quintal Queens permutation of N: halve or multiply by 3 (mod 5) each digit (0->0, 1->3, 2->1, 3->4, 4->2) of the base 5 representation of n-1, add one.

Original entry on oeis.org

1, 4, 2, 5, 3, 16, 19, 17, 20, 18, 6, 9, 7, 10, 8, 21, 24, 22, 25, 23, 11, 14, 12, 15, 13, 76, 79, 77, 80, 78, 91, 94, 92, 95, 93, 81, 84, 82, 85, 83, 96, 99, 97, 100, 98, 86, 89, 87, 90, 88, 26, 29, 27, 30, 28, 41, 44, 42, 45, 43, 31, 34, 32, 35, 33, 46, 49, 47, 50, 48, 36, 39
Offset: 1

Views

Author

Antti Karttunen, Oct 26 2001

Keywords

Comments

See comment at A065256.

Links

Crossrefs

Inverse permutation: A065257. A065258[n] = A065256[n-1]+1. Cf. also A065187, A065189.

A269133 Number of ways to place m nonattacking queens on an m X n board, 1 <= m <= n (triangular array).

Original entry on oeis.org

1, 2, 0, 3, 2, 0, 4, 6, 4, 2, 5, 12, 14, 12, 10, 6, 20, 36, 46, 40, 4, 7, 30, 76, 140, 164, 94, 40, 8, 42, 140, 344, 568, 550, 312, 92, 9, 56, 234, 732, 1614, 2292, 2038, 1066, 352, 10, 72, 364, 1400, 3916, 7552, 9632, 7828, 4040, 724, 11, 90, 536, 2468, 8492, 21362, 37248, 44148, 34774, 15116, 2680, 12, 110, 756, 4080, 16852, 52856, 120104, 195270, 222720, 160964, 68264, 14200
Offset: 1

Views

Author

Marko Riedel, Feb 19 2016

Keywords

Examples

			The triangular array begins:
   n\m  1   2   3    4     5     6      7      8      9     10    11    12
   1    1
   2    2   0
   3    3   2   0
   4    4   6   4    2
   5    5  12  14   12    10
   6    6  20  36   46    40     4
   7    7  30  76  140   164    94     40
   8    8  42 140  344   568   550    312     92
   9    9  56 234  732  1614  2292   2038   1066    352
  10   10  72 364 1400  3916  7552   9632   7828   4040    724
  11   11  90 536 2468  8492 21362  37248  44148  34774  15116  2680
  12   12 110 756 4080 16852 52856 120104 195270 222720 160964 68264 14200
...

Links

Crossrefs

Cf. A000170 (m=n), A002562, A065256, A348129.
Cf. A000027 (m=1), A002378 (m=2), A061989 (m=3), A061990 (m=4), A061991 (m=5), A061992 (m=6), A061993 (m=7), A172449 (m=8).
Cf. A036464 (2Q), A047659 (3Q), A061994 (4Q), A108792 (5Q), A176186 (6Q).
Cf. A006717, A051906, A319284 (backtrack trees).

Programs

  • PARI
    {A269133(m, n, B=[], t=if(#B, setminus(n, Set(concat(B+t=[-#B..-1], B-t))), n=[1..n]))= if(#B < m-1, vecsum([A269133(m, setminus(n, [t]), concat(B,t)) | t<-t]), #t)} \\ M. F. Hasler, Jan 11 2022
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.